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

Цикл
Undirected 6 cycle.svg
Вершин n
Рёбер n
Обхват n
Автоморфизмы 2n (Dn)
Хроматическое число 3 если n нечётно и 2, если чётно
Хроматический индекс 3 если n нечётно и 2, если чётно
Спектр {2 cos(2 k π / n), k=1, ... ,n}[1]
Свойства

2-регулярный
вершинно транзитивен
рёберно транзитивен
с постоянным расстоянием единица
гамильтонов


эйлеров
Commons-logo.svg Медиафайлы на Викискладе

ТерминологияПравить

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

СвойстваПравить

Граф-цикл:

Вдобавок:

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

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

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

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

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

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

См. такжеПравить

ПримечанияПравить

СсылкиПравить