Дополнительный граф

Cтраница 1

Дополнительный граф к графу G определяется как граф G с множеством вершин V ( G) V ( G), в котором две вершины соединены ребром тогда и только тогда, когда они не соединены ребром в графе G. Разбиение V ( G) на k подмножеств, каждое из которых независимо, называется k - раскрашиванием графа G. Отметим, что это соответствует покрытию k кликами вершин дополнительного графа. Наименьшее k, для которого граф G допускает - раскрашивание, называется его хроматическим числом. [1]

Графы схемы к примеру. [2]

Из рассмотренных примеров видно, что дополнительный граф размещения приходится анализировать лишь тогда, когда в основном графе существует пара цепей, соответствующих дифференциалам, у которых имеется одна и только одна общая вершина, отображающая общее водило этих дифференциалов. [3]

Если Оп обладает требуемым свойством, то дополнительный граф Gn, очевидно, обладает тем свойством, что всякий его ft - вер шинный собственный подграф имеет изолированную вершину. [4]

Рид [6] показал, как можно подсчитать число само дополнительных графов, первым применив теорему де Брейна [2] к подсчету графов с точностью до их взаимной дополнительности. Чтобы описать метод Рида, будем называть два графа эквивалентными относительно дополнительности, если они изоморфны или один из них изоморфен дополнению другого. Выразим теперь эту эквивалентность на языке степенной группы. [5]

Эти обозначения очень удобны для обсуждения понятий дополнения и дополнительного графа. [6]

Заметим, что если Я ц - 2, то в дополнительном графе выполнено равенство Я ц и симметрическая схема является дополнительной к схеме, получаемой, исходя из дополнительного графа. [7]

Заметим, что если Я ц - 2, то в дополнительном графе 9 выполнено равенство Я ц и симметрическая схема является дополнительной к схеме, получаемой, исходя из дополнительного графа. [8]

Диаграмма взаимосвязей между задачами. [9]

Связь между наибольшими независимыми множествами вершин и наибольшими кликами устанавливается с помощью дополнительных графов, а между наибольшими независимыми множествами вершин и наибольшими паросочетаниями - с помощью реберных графов. [10]

Теорема 4.16. Если G - граф с п вершинами и G - его дополнительный граф, то: ( 1) при л8, по крайней мере, один из них плоский, ( 2) при п 8, по крайней мере, один из них неплоский, и ( 3) при п8 первый или второй или сразу оба могут быть как плоскими, так и неплоскими. [11]

Так как проверка внешнепланарности графа значительно проще, чем определение его планарности, а построение дополнительного графа размещения приходится делать довольно редко, то исследование геометрической совместности механизмов с двумя степенями свободы занимает гораздо меньшее время, чем для механизмов с большим числом степеней свободы. [12]

Сделаем теперь простое замечание, касающееся самообратных графов и подобное тому, которое было сделано Ридом относительно само дополнительных графов. Именно, многочлен 2ср ( х) подсчитывает каждый самообратный орграф дважды, а каждый несамообратный - только один раз. Следовательно, многочлен 2ср ( х) - dp ( х) подсчитывает каждый самообратный орграф в точности один раз. [13]

Во всякой достаточной конструкции при четном k такая вершина всегда существует, действительно, предполагая противное, видим, что дополнительный граф Gn не имеет изолированных вершин, и, согласно лемме, содержит ft - вершинный подграф без изолированных вершин, значит, исходный граф не может содержать даже звезды на этих ft вершинах, что противоречит достаточности конструкции. [14]

Страницы: 1 2