Циркулянтный граф
В теории графов циркулянтным графом называется неориентированный граф, имеющий циклическую группу симметрий, которая включает симметрию, переводящую любую вершину в любую другую вершину.
Эквивалентные определения
Циркулянтные графы могут быть определены несколькими эквивалентными способами[1]:
- Автоморфизм группы графа содержит циклическую подгруппу, которая действует транзитивно на вершинах графа.
- Граф имеет матрицу смежности, являющуюся циркулянтом.
- вершин графа можно пронумеровать числами от 0 до n − 1 таким образом, что если две вершины с номерами и смежны, то любые две вершины с номерами и (z − x + y) mod n тоже смежны.
- Граф можно нарисовать (с возможными пересечениями рёбер) так, что его вершины лежат в углах правильного многоугольника и любой поворот многоугольника в себя является симметрией рисунка (получаем тот же рисунок).
Примеры
Любой цикл является циркулянтным графом, как и любая корона.
Графы Пэли порядка (где — простое число, сравнимое с 1 по модулю 4) — это графы, в которых вершины являются числами от 0 до n − 1 и две вершины смежны, если разность соответствующих чисел является квадратичным вычетом по модулю . Вследствие того, что присутствие или отсутствие ребра зависит только от разности номеров вершин по модулю , любой граф Пэли является циркулянтным графом.
Любая лестница Мёбиуса является циркулянтным графом, как и любой полный граф. Полный двудольный граф является циркулянтным, если обе его части имеют одинаковое число вершин.
Если два числа и взаимно просты, то m × n ладейный граф (граф, имеющий вершину в каждой клетке шахматной доски m × n и рёбра между любыми двумя клетками, если ладья может перейти с одной клетки на другую за один ход) является циркулянтным графом. Это является следствием того, что его симметрии содержат в качестве подгруппы циклическую группу {{{1}}}. Как обобщение этого случая, прямое произведение графов между любыми циркулянтными графами с и вершинами даёт в результате циркулянтный граф[1].
Многие из известных нижних границ чисел Рамсея появляются из примеров циркулянтных графов, имеющих маленькие максимальные клики и маленькие максимальные независимые множества[2].
Конкретный пример
Циркулянтный граф (или , или ) с прыжками определяется как граф с узлами, пронумерованными числами и каждый узел смежен с 2k узлами по модулю .
- Граф связан тогда и только тогда, когда НОД.
- Если фиксировнные целые, то число остовных деревьев , где удовлетворяет рекуррентному соотношению порядка .
- В частности, , где — n-ое число Фибоначчи.
Самодополнительные циркулянты
Самодополнительный граф — это граф, в котором удаление существующих рёбер и добавление отсутствующих даёт граф, изоморфный исходному.
Например, циклический граф с пятью вершинами самодополнителен и является также циркулянтным. В более общем виде, любой граф Пэли является самодополнительным циркулянтным графом[3]. Хорст Сакс показал, что если число обладает свойством, что любой простой делитель сравним с 1 по модулю 4, то существует самодополнительный циркулянтный граф с вершинами. Он высказал гипотезу, что это условие необходимо, то есть при других значениях самодополнительные циркулянтные графы не существуют[1][3]. Гипотеза доказана 40 лет позже Вилфредом (Vilfred)[1].
Гипотеза Адамса
Определим циркулянтную нумерацию циркулянтного графа как маркировку вершин графа числами от 0 до n − 1 таким образом, что если две вершины и смежны, то любые две вершины с номерами и (z − x + y) mod n тоже смежны. Эквивалентно, циркулянтная нумерация — это нумерация вершин при которой матрица смежности графа является циркулянтной матрицей.
Пусть — целое, взаимно простое c , и пусть — любое целое. Тогда линейная функция ax + b преобразует циркулянтную нумерацию в другую циркулянтную нумерацию. Андраш Адам (András Ádám) высказал гипотезу, что линейное отображение — единственный способ перенумерации вершин графа, сохраняющее свойство циркулянтности. То есть, если и — два изоморфных циркулянтных графа с различными нумерациями, то существует линейное преобразование, переводящее нумерацию для в нумерацию для . Однако, как выяснилось, гипотеза Адама не верна. Контрпримером служат графы и с 16-ю вершинами в каждом; вершина в соединена с шестью соседями x ± 1, x ± 2, и x ± 7 (по модулю 16), в то время как в шесть соседей — это x ± 2, x ± 3, и x ± 5 (по модулю 16). Эти два графа изоморфны, но их изоморфизм нельзя получить посредством линейного преобразования.[1]
Примечания
- V. Vilfred. Graph Theory and its Applications (Anna University, Chennai, March 14–16, 2001) / editors: R. Balakrishnan, G. Sethuraman, Robin J. Wilson. — Alpha Science, 2004. — С. 34—36.
- Small Ramsey Numbers Архивная копия от 18 января 2012 на Wayback Machine, Stanisław P. Radziszowski, Electronic J. Combinatorics, dynamic survey updated 2009.
- Horst Sachs. Über selbstkomplementäre Graphen // Publicationes Mathematicae Debrecen. — 1962. — Т. 9. — С. 270—288.
Ссылки
- Weisstein, Eric W. Circulant Graph (англ.) на сайте Wolfram MathWorld.