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

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

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

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

Примеры

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

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

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

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

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

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

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

• Граф ${\displaystyle C_{n}^{s_{1},\ldots ,s_{k}}}$ связан тогда и только тогда, когда НОД ${\displaystyle (n,s_{1},\ldots ,s_{k})=1}$ .

• Если ${\displaystyle 1\leq s_{1}<\cdots <s_{k}}$ фиксировнные целые, то число остовных деревьев ${\displaystyle t(C_{n}^{s_{1},\ldots ,s_{k}})=na_{n}^{2}}$ , где ${\displaystyle a_{n}}$ удовлетворяет рекуррентному соотношению порядка ${\displaystyle 2^{s_{k}-1}}$ .
  • В частности, ${\displaystyle t(C_{n}^{1,2})=nF_{n}^{2}}$ , где ${\displaystyle F_{n}}$ — n -ое число Фибоначчи .

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

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

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

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

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

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

Примечания

Ссылки

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