График цикла

График цикла
График цикла C 5
Обхват	н
Автоморфизмы	2 н ( Д н )
Хроматическое число	3, если n нечетное, 2 в противном случае
Хроматический индекс	3, если n нечетное, 2 в противном случае
Спектр	${\displaystyle \left\{2\cos \left({\frac {2k\pi }{n}}\right);k=1,\cdots ,n\right\}}$[1]
Характеристики	2-регулярный Вершинно-транзитивный Ребро-транзитивный Единичное расстояние Гамильтонов Эйлеров
Обозначение	С н
Таблица графиков и параметров

В теории графов циклический граф или круговой граф — это граф , состоящий из одного цикла , или, другими словами, некоторого числа вершин (не менее 3, если граф простой ), соединенных в замкнутую цепь. Циклический граф с n вершинами называется C _n . ^[2] Число вершин в C _n равно числу ребер , и каждая вершина имеет степень 2; то есть каждая вершина имеет ровно два инцидентных ей ребра.

Если , то это изолированный контур .${\displaystyle n=1}$

Существует много синонимов для «циклического графа». К ним относятся простой циклический граф и циклический граф , хотя последний термин используется реже, поскольку он может также относиться к графам, которые просто не являются ациклическими . Среди теоретиков графов также часто используются цикл , многоугольник или n -угольник . Термин n -цикл иногда используется в других ситуациях. ^[3]

Цикл с четным числом вершин называется четным циклом ; цикл с нечетным числом вершин называется нечетным циклом .

Циклический график — это:

• 2-реберно раскрашиваемо , тогда и только тогда, когда оно имеет четное число вершин
• 2-регулярный
• 2-вершинно раскрашиваемый , если и только если он имеет четное число вершин. В более общем случае граф является двудольным тогда и только тогда, когда он не имеет нечетных циклов ( Kőnig , 1936).
• Подключен
• Эйлеров
• Гамильтониан
• График единичных расстояний

Кроме того:

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

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

Ориентированный циклический граф — это направленная версия циклического графа, в которой все ребра ориентированы в одном направлении.

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

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

Направленные графы циклов — это графы Кэли для циклических групп (см., например, Тревизана).

На Викискладе есть медиафайлы по теме «Графики циклов» .

• Полный двудольный граф
• Полный график
• Циркулярный график
• Граф цикла (алгебра)
• Нулевой график
• Граф пути

• Дистель, Рейнхард (2017). Теория графов (5-е изд.). Springer . ISBN 978-3-662-53621-6.

• Вайсштейн, Эрик В. «Циклический график». MathWorld .(обсуждение как 2-регулярных циклических графов, так и групповой концепции циклических диаграмм )
• Лука Тревизан , Персонажи и расширение.