Введение

Неориентированный граф, на который действует транзитивно циклическая группа симметрий, – это квадратные матрицы.

В теории графов циркулянтный граф – это неориентированный граф, на который действует циклическая группа симметрий, переставляющая любые две вершины. Иногда его называют циклическим графом. Автоморфическая группа графа включает циклическую подгруппу, действующую транзитивно на вершинах графа. Иными словами, граф имеет автоморфизм, являющийся циклической перестановкой его вершин. Граф имеет матрицу смежности, которая является циркулянтной матрицей. Вершины графа можно пронумеровать от 0 до n − 1 таким образом, что если две вершины с номерами x и (x + d) mod n смежны, то любые две вершины с номерами z и (z + d) mod n также смежны. Граф можно изобразить (возможно, с пересечениями) так, чтобы его вершины лежали на вершинах правильного многоугольника, и каждая вращательная симметрия многоугольника также являлась симметрией изображения. Граф является графом Кэли циклической группы.

Примеры

Каждый циклический граф является циркулянтным графом, как и каждый граф-корона с числом вершин, кратным 2 по модулю 4. Графы Пейли порядка n (где n – простое число, сравнимое с 1 по модулю 4) – это графы, вершины которых соответствуют числам от 0 до n–1, и две вершины смежны, если их разность является квадратичным вычетом по модулю n. Поскольку наличие или отсутствие ребра зависит только от разности номеров вершин по модулю n, любой граф Пейли является циркулянтным графом. Каждая лестница Мёбиуса является циркулянтным графом, как и каждый полный граф. Полный двудольный граф является циркулянтным графом, если он имеет одинаковое число вершин в каждой доле. Если два числа m и n взаимно просты, то граф m × n ладей (граф, имеющий вершину для каждой клетки шахматной доски размера m × n и ребро для каждой пары клеток, между которыми шахматная ладья может переместиться за один ход) является циркулянтным графом. Это связано с тем, что его симметрии включают в себя циклическую группу Cmn как подгруппу. В более общем случае, в этом случае тензорное произведение графов между любыми циркулянтными графами с m и n вершинами само является циркулянтным графом.

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

Циркулянтный граф с шагами определяется как граф с узлами, пронумерованными от 0 до n-1, где каждая вершина i соединена с 2k вершинами. Граф связен тогда и только тогда, когда gcd(k, n) = 1. Если k и n – фиксированные целые числа, то количество остовных деревьев τ(n) удовлетворяет рекуррентному соотношению порядка 2k. В частности, τ(n) = F(n), где F(n) – n-е число Фибоначчи.

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

Самодополняющийся граф — это граф, в котором замена каждого ребра на неребро и наоборот приводит к изоморфному графу. Например, пятивершинный цикл является самодополняющимся и также является циркулянтным графом. В более общем случае, любой граф Пейли простого порядка является самодополняющимся циркулянтным графом. Хорст Сакс показал, что если число n обладает свойством, что каждый простой делитель n сравнимо с 1 по модулю 4, то существует самодополняющийся циркулянт с n вершинами. Он предположил, что это условие также необходимо: что никакие другие значения n не допускают существования самодополняющегося циркулянта.

Алгоритмические вопросы

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