В теории графов , A циркулянт график представляет собой неориентированный граф действовал с помощью циклической группы из симметрии , которая принимает любую вершину в любую другую вершину . Это иногда называется циклическим графиком , [1] , но этот термин имеет другие значения.
Эквивалентные определения
Циркулянтные графы можно описать несколькими эквивалентными способами: [2]
- Группа автоморфизмов графа включает циклическую подгруппу, которая действует транзитивно на вершинах графа. Другими словами, граф имеет автоморфизм графа , который представляет собой циклическую перестановку его вершин.
- Граф имеет матрицу смежности, которая является циркулянтной матрицей .
- В п вершины графа могут быть пронумерованы от 0 до п - 1 таким образом , что, если какие - то две вершины пронумерованы х и ( х + д ) по модулю п являются смежными, а затем через каждые две вершины пронумерованы г и ( г + д ) mod n смежны.
- Граф можно нарисовать (возможно, с пересечениями) так, чтобы его вершины лежали в углах правильного многоугольника, и каждая вращательная симметрия многоугольника также является симметрией чертежа.
- Граф является графом Кэли из циклической группы . [3]
Примеры
Каждый граф циклов является циркулянтным графом, как и любой граф короны с 2 по модулю 4 вершинами.
В Пэли графы порядка п (где п является простым числом конгруэнтны 1 по модулю 4 ) представляет собой график , в котором вершины являются числами от 0 до п - 1 и две вершины смежны , если их разность является квадратичный вычет по модулю п . Поскольку наличие или отсутствие ребра зависит только от разности по модулю n двух номеров вершин, любой граф Пэли является циркулянтным графом.
Каждая лестница Мёбиуса является циркулянтным графом, как и любой полный граф . Полный двудольный граф является циркулянт графом , если он имеет такое же число вершин с обеих сторон его двудольности.
Если два числа т и п является взаимно простым , то м × п Ладейного графа (график , который имеет вершину для каждого квадрата с т × п шахматной доски и ребра для каждых двух квадратов , что шахматы ладья может перемещаться между в одном move) - циркулянтный граф. Это потому, что его симметрии включают в качестве подгруппы циклическую группу C mn С м × С н . В более общем смысле, в этом случае тензорное произведение графов между любыми циркулянтами с m и n вершинами само является циркулянтом. [2]
Многие из известных нижних оценок по числам Рамсея приходят из примеров циркулянтных графов , которые имеют небольшие максимальные клики и небольшие максимальные независимые множества . [1]
Конкретный пример
Циркулянтный граф с прыжками определяется как граф с узлы помечены где каждый узел i соседствует с 2 k узлами.
- График связано тогда и только тогда, когда .
- Если фиксированные целые числа, то количество остовных деревьев где удовлетворяет рекуррентному отношению порядка.
- В частности, где является п -го числа Фибоначчи .
Самокомплементарные циркулянты
Самодополнительный граф представляет собой график , в котором каждое ребро замены , не относящейся к краю и наоборот производит изоморфный граф. Например, циклический граф с пятью вершинами самодополняемый, а также циркулянтный граф. В более общем смысле каждый граф Пэли простого порядка является самодополняющим циркулянтным графом. [4] Хорст Сакс показал, что если число n обладает тем свойством, что каждый простой делитель числа n сравним с 1 по модулю 4 , то существует самодополняющий циркулянт с n вершинами. Он предположил, что это условие также необходимо: никакие другие значения n не допускают существования самодополняемого циркулянта. [2] [4] Гипотеза была доказана 40 лет спустя Вильфредом. [2]
Гипотеза Адама
Определим циркулянтную нумерацию циркулянтного графа как разметку вершин графа числами от 0 до n - 1 таким образом, что если некоторые две вершины с номерами x и y смежны, то каждые две вершины с номерами z и ( z - x + y ) mod n смежны. Эквивалентно циркулянтная нумерация - это нумерация вершин, для которых матрица смежности графа является циркулянтной матрицей.
Пусть a будет целым числом, взаимно простым с n , и пусть b будет любым целым числом. Затем линейная функция, которая переводит число x в ax + b, преобразует циркулянтную нумерацию в другую циркулянтную нумерацию. Андраш Адам предположил, что эти линейные отображения являются единственными способами перенумерации циркулянтного графа при сохранении циркулянтного свойства: то есть, если G и H являются изоморфными циркулянтными графами с разными нумерациями, то существует линейное отображение, которое преобразует нумерацию для G в нумерации для H . Однако теперь известно, что гипотеза Адама неверна. Контрпример - графы G и H с 16 вершинами в каждом; вершина x в G соединена с шестью соседями x ± 1 , x ± 2 и x ± 7 по модулю 16, в то время как в H шесть соседей - это x ± 2 , x ± 3 и x ± 5 по модулю 16. Эти два графы изоморфны, но их изоморфизм не может быть реализован линейным отображением. [2]
Гипотеза Тойды уточняет гипотезу Адама, рассматривая только специальный класс циркулянтных графов, в котором все различия между соседними вершинами графа взаимно просты с числом вершин. Согласно этой уточненной гипотезе, эти специальные циркулянтные графы должны обладать тем свойством, что все их симметрии происходят из симметрий основной аддитивной группы чисел по модулю n . Это было доказано двумя группами в 2001 и 2002 годах. [5] [6]
Алгоритмические вопросы
Существует алгоритм распознавания циркулянтных графов за полиномиальное время , и проблема изоморфизма циркулянтных графов может быть решена за полиномиальное время. [7] [8]
Рекомендации
- ^ a b Малые числа Рамсея , Станислав П. Радзишовский, Electronic J. Combinatorics , динамический обзор 1, обновлено в 2014 г.
- ^ a b c d e Вильфред, В. (2004), «О циркулянтных графах», в Балакришнане, Р.; Sethuraman, G .; Уилсон, Робин Дж. (Ред.), Теория графов и ее приложения (Университет Анна, Ченнаи, 14–16 марта 2001 г.) , Alpha Science, стр. 34–36.
- ^ Альспах, Брайан (1997), "Изоморфизм и графы Кэли на абелевых группах", Симметрия графов (Монреаль, PQ, 1996) , NATO Adv. Sci. Inst. Сер. C Math. Phys. Sci., 497 , Dordrecht: Kluwer Acad. Publ., Pp. 1–22, MR 1468786..
- ^ а б Сакс, Хорст (1962). "Über selbstkomplementäre Graphen". Publicationes Mathematicae Debrecen . 9 : 270–288. Руководство по ремонту 0151953 ..
- ^ Музычук Михаил; Клин, Михаил; Pöschel, Reinhard (2001), "Проблема изоморфизма для циркулянтных графов с помощью теории колец Шура", Коды и схемы ассоциации (Piscataway, NJ, 1999) , DIMACS Ser. Дискретная математика. Теорет. Comput. Sci., 56 , Провиденс, Род-Айленд: Американское математическое общество, стр. 241–264, MR 1816402
- ^ Добсон, Эдвард; Моррис, Джой (2002), «Гипотеза Тойды верна» , Электронный журнал комбинаторики , 9 (1): R35: 1 – R35: 14, MR 1928787
- ^ Музычук, Михаил (2004). «Решение проблемы изоморфизма циркулянтных графов». Proc. Лондонская математика. Soc . 88 : 1–41. DOI : 10.1112 / s0024611503014412 . MR 2018956 .
- ^ Евдокимов, Сергей; Пономаренко, Илья (2004). «Распознавание и проверка изоморфизма циркулянтных графов за полиномиальное время» . Санкт-Петербургская математика. Дж . 15 : 813–835. DOI : 10,1090 / s1061-0022-04-00833-7 . Руководство по ремонту 2044629 .
Внешние ссылки
- Вайсштейн, Эрик В. «Циркулянтный график» . MathWorld .