Цикл (граф)

Цикл
Вершин	n
Рёбер	n
Обхват	n
Автоморфизмы	2n (Dn)
Хроматическое число	3 если n нечётно и 2, если чётно
Хроматический индекс	3 если n нечётно и 2, если чётно
Спектр	{2 cos(2 k π / n), k=1, ... ,n}
Свойства	2-регулярный вершинно транзитивен рёберно транзитивен с постоянным расстоянием единица гамильтонов эйлеров

Цикл — граф, состоящий из единственного цикла, или, другими словами, некоторого числа вершин, соединённых замкнутой цепью. Граф-цикл с n вершинами обозначают как C_n. Число вершин в C_n равно числу рёбер и каждая вершина имеет степень 2, то есть любая вершина инцидентна ровно двум рёбрам.

Терминология

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

Свойства

Граф-цикл:

• связен
• 2-регулярен
• эйлеров
• гамильтонов
• раскрашиваем в два цвета тогда и только тогда, когда он имеет чётное число вершин. Граф является двудольным тогда и только тогда, когда он не имеет нечётных циклов (в качестве подграфов) (Кёниг, 1936).
• рёберно-2-раскрашиваем тогда и только тогда, когда он имеет чётное число вершин.
• Вершинно-раскрашиваем в 3 цвета и рёберно-3-раскрашиваем для любого числа вершин.
• с постоянным расстоянием единица

Вдобавок:

• Поскольку графы-циклы можно нарисовать в виде правильных многоугольников, симметрии цикла с n вершинами те же самые, что и у правильного многоугольника с n сторонами, то есть диэдрическая группа порядка 2n. В частности, существуют симметрии, переводящие любую вершину в любую другую вершину и любое ребро в любое другое ребро, так что n-цикл является симметричным графом.

Ориентированный граф-цикл

Ориентированный граф-цикл длины 8

Ориентированным графом-циклом называется ориентированная версия графа-цикла, в котором все дуги направлены в одном и том же направлении.

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

Ориентированный граф-цикл имеет постоянную полустепень захода 1 и постоянную полустепень исхода 1.

Ориентированные графы-циклы являются графами Кэли для циклических групп (см., например, Тревизана [Trevisan]).

См. также

• Полный двудольный граф
• Путь (теория графов)
• Полный граф

Ссылки

• Weisstein, Eric W. Cycle Graph (англ.) на сайте Wolfram MathWorld. (обсуждение как 2-регулярных графов-циклов, так и групповые концепции циклических диаграмм)
• Люк Тревизан, Characters and Expansion.