Циркулянтный граф

Граф Пэли 13-го порядка как пример циркулянтного графа.

Корона с шестью, восемью и десятью вершинами.

В теории графов циркулянтным графом называется неориентированный граф, имеющий циклическую группу симметрий, которая включает симметрию, переводящую любую вершину в любую другую вершину.

Эквивалентные определения

Циркулянтные графы могут быть определены несколькими эквивалентными способами:

• Автоморфизм группы графа содержит циклическую подгруппу, которая действует транзитивно на вершинах графа.
• Граф имеет матрицу смежности, являющуюся циркулянтом.
• [math]\displaystyle{ n }[/math] вершин графа можно пронумеровать числами от 0 до n − 1 таким образом, что если две вершины с номерами [math]\displaystyle{ x }[/math] и [math]\displaystyle{ y }[/math] смежны, то любые две вершины с номерами [math]\displaystyle{ z }[/math] и (z − x + y) mod n тоже смежны.
• Граф можно нарисовать (с возможными пересечениями рёбер) так, что его вершины лежат в углах правильного многоугольника и любой поворот многоугольника в себя является симметрией рисунка (получаем тот же рисунок).

Примеры

Любой цикл является циркулянтным графом, как и любая корона.

Графы Пэли порядка [math]\displaystyle{ n }[/math] (где [math]\displaystyle{ n }[/math] — простое число, сравнимое с 1 по модулю 4) — это графы, в которых вершины являются числами от 0 до n − 1 и две вершины смежны, если разность соответствующих чисел является квадратичным вычетом по модулю [math]\displaystyle{ n }[/math]. Вследствие того, что присутствие или отсутствие ребра зависит только от разности номеров вершин по модулю [math]\displaystyle{ n }[/math], любой граф Пэли является циркулянтным графом.

Любая лестница Мёбиуса является циркулянтным графом, как и любой полный граф. Полный двудольный граф является циркулянтным, если обе его части имеют одинаковое число вершин.

Если два числа [math]\displaystyle{ m }[/math] и [math]\displaystyle{ n }[/math] взаимно просты, то m × n ладейный граф (граф, имеющий вершину в каждой клетке шахматной доски m × n и рёбра между любыми двумя клетками, если ладья может перейти с одной клетки на другую за один ход) является циркулянтным графом. Это является следствием того, что его симметрии содержат в качестве подгруппы циклическую группу {{{1}}}. Как обобщение этого случая, прямое произведение графов между любыми циркулянтными графами с [math]\displaystyle{ m }[/math] и [math]\displaystyle{ n }[/math] вершинами даёт в результате циркулянтный граф.

Многие из известных нижних границ чисел Рамсея появляются из примеров циркулянтных графов, имеющих маленькие максимальные клики и маленькие максимальные независимые множества.

Конкретный пример

Циркулянтный граф [math]\displaystyle{ C_n^{s_1,\ldots,s_k} }[/math] (или [math]\displaystyle{ C_n(s_1,\ldots,s_k) }[/math], или [math]\displaystyle{ circ(n:s_1,\ldots,s_k) }[/math]) с прыжками [math]\displaystyle{ s_1, \ldots, s_k }[/math] определяется как граф с [math]\displaystyle{ n }[/math] узлами, пронумерованными числами [math]\displaystyle{ 0, 1, \ldots, n-1 }[/math] и каждый узел [math]\displaystyle{ i }[/math] смежен с 2k узлами [math]\displaystyle{ i \pm s_1, \ldots, i \pm s_k }[/math] по модулю [math]\displaystyle{ n }[/math].

• Граф [math]\displaystyle{ C_n^{s_1, \ldots, s_k} }[/math] связан тогда и только тогда, когда НОД[math]\displaystyle{ (n, s_1, \ldots, s_k) = 1 }[/math].

• Если [math]\displaystyle{ 1 \leq s_1 \lt \cdots \lt s_k }[/math] фиксировнные целые, то число остовных деревьев [math]\displaystyle{ t(C_n^{s_1,\ldots,s_k})=na_n^2 }[/math], где [math]\displaystyle{ a_n }[/math] удовлетворяет рекуррентному соотношению порядка [math]\displaystyle{ 2^{s_k-1} }[/math].
  • В частности, [math]\displaystyle{ t(C_n^{1,2}) = nF_n^2 }[/math], где [math]\displaystyle{ F_n }[/math] — n-ое число Фибоначчи.

Самодополнительные циркулянты

Самодополнительный граф — это граф, в котором удаление существующих рёбер и добавление отсутствующих даёт граф, изоморфный исходному.

Например, циклический граф с пятью вершинами самодополнителен и является также циркулянтным. В более общем виде, любой граф Пэли является самодополнительным циркулянтным графом. Хорст Сакс показал, что если число [math]\displaystyle{ n }[/math] обладает свойством, что любой простой делитель [math]\displaystyle{ n }[/math] сравним с 1 по модулю 4, то существует самодополнительный циркулянтный граф с [math]\displaystyle{ n }[/math] вершинами. Он высказал гипотезу, что это условие необходимо, то есть при других значениях [math]\displaystyle{ n }[/math] самодополнительные циркулянтные графы не существуют. Гипотеза доказана 40 лет позже Вилфредом (Vilfred).

Гипотеза Адамса

Определим циркулянтную нумерацию циркулянтного графа как маркировку вершин графа числами от 0 до n − 1 таким образом, что если две вершины [math]\displaystyle{ x }[/math] и [math]\displaystyle{ y }[/math] смежны, то любые две вершины с номерами [math]\displaystyle{ z }[/math] и (z − x + y) mod n тоже смежны. Эквивалентно, циркулянтная нумерация — это нумерация вершин при которой матрица смежности графа является циркулянтной матрицей.

Пусть [math]\displaystyle{ a }[/math] — целое, взаимно простое c [math]\displaystyle{ n }[/math], и пусть [math]\displaystyle{ b }[/math] — любое целое. Тогда линейная функция ax + b преобразует циркулянтную нумерацию в другую циркулянтную нумерацию. Андраш Адам (András Ádám) высказал гипотезу, что линейное отображение — единственный способ перенумерации вершин графа, сохраняющее свойство циркулянтности. То есть, если [math]\displaystyle{ G }[/math] и [math]\displaystyle{ H }[/math] — два изоморфных циркулянтных графа с различными нумерациями, то существует линейное преобразование, переводящее нумерацию для [math]\displaystyle{ G }[/math] в нумерацию для [math]\displaystyle{ H }[/math]. Однако, как выяснилось, гипотеза Адама не верна. Контрпримером служат графы [math]\displaystyle{ G }[/math] и [math]\displaystyle{ H }[/math] с 16-ю вершинами в каждом; вершина [math]\displaystyle{ x }[/math] в [math]\displaystyle{ G }[/math] соединена с шестью соседями x ± 1, x ± 2, и x ± 7 (по модулю 16), в то время как в [math]\displaystyle{ H }[/math] шесть соседей — это x ± 2, x ± 3, и x ± 5 (по модулю 16). Эти два графа изоморфны, но их изоморфизм нельзя получить посредством линейного преобразования.

Ссылки

• Weisstein, Eric W. Circulant Graph (англ.) на сайте Wolfram MathWorld.