Граф-цикл
В теории графов графом-циклом называется граф, состоящий из единственного цикла, или, другими словами, некоторого числа вершин, соединённых замкнутой цепью. Граф-цикл с n вершинами обозначают как Cn. Число вершин в Cn равно числу рёбер и каждая вершина имеет степень 2, то есть любая вершина инцидентна ровно двум рёбрам.
| Цикл | |
|---|---|
 | |
| Вершин | n |
| Рёбер | n |
| Обхват | n |
| Автоморфизмы | 2n (Dn) |
| Хроматическое число | 3 если n нечётно и 2, если чётно |
| Хроматический индекс | 3 если n нечётно и 2, если чётно |
| Спектр | {2 cos(2 k π / n), k=1, ... ,n}[1] |
| Свойства |
2-регулярный
эйлеров |
 Медиафайлы на Викискладе | |
Терминология
Граф-цикл имеет много синонимов. Используют термины простой граф-цикл и циклический граф, хотя последний термин употребляется не часто, поскольку он может относиться к графам, не являющимся ациклическими. Иногда употребляются термины цикл, многоугольник или n-угольник. Цикл с чётным числом вершин называют чётным циклом, а с нечётным числом вершин — нечётным циклом.
Свойства
Граф-цикл:
- связен
- 2-регулярен
- эйлеров
- гамильтонов
- раскрашиваем в два цвета тогда и только тогда, когда он имеет чётное число вершин. Граф является двудольным тогда и только тогда, когда он не имеет нечётных циклов (в качестве подграфов) (Кёниг, 1936).
- рёберно-2-раскрашиваем тогда и только тогда, когда он имеет чётное число вершин.
- Вершинно-раскрашиваем в 3 цвета и рёберно-3-раскрашиваем для любого числа вершин.
- с постоянным расстоянием единица
Вдобавок:
- Поскольку графы-циклы можно нарисовать в виде правильных многоугольников, симметрии цикла с n вершинами те же самые, что и у правильного многоугольника с n сторонами, то есть диэдрическая группа порядка 2n. В частности, существуют симметрии, переводящие любую вершину в любую другую вершину и любое ребро в любое другое ребро, так что n-цикл является симметричным графом.
Ориентированный граф-цикл
Ориентированным графом-циклом называется ориентированная версия графа-цикла, в котором все дуги направлены в одном и том же направлении.
В ориентированном графе множество дуг, которые содержат хотя бы одну дугу из каждого ориентированного цикла, называется разрывающим множеством дуг. Подобным образом, множество вершин, содержащих по меньшей мере одну вершину из каждого ориентированного цикла, называется разрезающее циклы множество вершин.
Ориентированный граф-цикл имеет постоянную полустепень захода 1 и постоянную полустепень исхода 1.
Ориентированные графы-циклы являются графами Кэли для циклических групп (см., например, Тревизана [Trevisan]).
Примечания
- Some simple graph spectra. win.tue.nl
Ссылки
- Weisstein, Eric W. Cycle Graph (англ.) на сайте Wolfram MathWorld. (обсуждение как 2-регулярных графов-циклов, так и групповые концепции циклических диаграмм)
- Люк Тревизан, Characters and Expansion.