Самодополнительный граф

Cтраница 1

Граф и его дополнение.| Наименьшие нетривиальные самодополнительные графы. [1]

Самодополнительный граф - это граф, изоморфный своему дополнению. [2]

Самодополнительный граф изоморфен своему дополнению. Дополнение диграфа определяется аналогично, так же как и самодополнительный диграф. [3]

Каждый самодополнительный граф имеет 4 или 4я 1 вершин. [4]

Сильные орграфы третьего порядка. [5]

Число самодополнительных графов и орграфов было определено Ридом [6] ( см. гл. [6]

Показать, что самодополнительный граф связен. [7]

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

Затем Рид заметил, что 2ар есть число р-вершинных графов, если каждый самодополнительный граф считать дважды, а не-самодополнительный - только один раз. [9]

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

Самодополнительные графы с 4 и 5 вершинами показаны на рис. 2.13. Результат Рида [3] для числа sp самодополнительных графов с р вершинами можно вывести из теоремы перечисления степенной группы. [11]

Простой граф, изоморфный своему дополнению, называется самодополнительным. Докажите, что число вершин самодополнительного графа представимо в виде 4fe или 4fe 1, где k - целое, и найдите все самодополнительные графы с четырьмя и пятью вершинами. [12]

Если с ( х) - ряд, перечисляющий элементы множества У, и А - группа подстановок с множеством объектов X, то, как мы видели в гл. Существует обширный класс задач, для решения которых весьма важно уметь перечислять орбиты в множестве Vх степенной группы ВА, когда группа В не является единичной. По этой причине упомянутый результат де Брейна мы в дальнейшем предпочитаем называть теоремой перечисления степенной группы. В качестве приложений этой теоремы приводятся решения задач перечисления самодополнительных графов и орграфов, графов с раскрашенными ребрами, конечных автоматов и самообратных орграфов. [13]

Если с ( х) - ряд, перечисляющий элементы множества Y, и А - группа подстановок с множеством объектов X, то, как мы видели в гл. Существует обширный класс задач, для решения которых весьма важно уметь перечислять орбиты в множестве Yx степенной группы ВА, когда группа В не является единичной. По этой причине упомянутый результат де Брейна мы в дальнейшем предпочитаем называть теоремой перечисления степенной группы. В качестве приложений этой теоремы приводятся решения задач перечисления самодополнительных графов и орграфов, графов с раскрашенными ребрами, конечных автоматов и самообратных орграфов. [14]

Страницы: 1