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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Граф Пейли 13-го порядка как пример циркулянтного графа.
Корона с шестью, восемью, и десятью вершинами.

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


Эквивалентные определения[править | править вики-текст]

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

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

Примеры[править | править вики-текст]

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

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

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

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

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

Конкретный пример[править | править вики-текст]

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


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

Самодополнительные циркулянты[править | править вики-текст]

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

Гипотеза Адамса[править | править вики-текст]

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

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

Ссылки[править | править вики-текст]

  1. 1 2 3 4 5 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..
  2. Small Ramsey Numbers, Stanisław P. Radziszowski, Electronic J. Combinatorics, dynamic survey updated 2009.
  3. 1 2 Horst Sachs Über selbstkomplementäre Graphen // Publicationes Mathematicae Debrecen. — 1962. — Т. 9. — С. 270–288..

Ссылки[править | править вики-текст]