WikiSort.ru - Не сортированное

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

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

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

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

Свойства

Граф-цикл:

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

Вдобавок:

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

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

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

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

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

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

См. также

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

Примечания

Ссылки

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

Для улучшения этой статьи желательно: Проверить качество перевода с иностранного языка.