График цикла

Эта статья о связных 2-регулярных графах. Чтобы узнать о других значениях, см. Циклический график .

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

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

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

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

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

Характеристики

График цикла – это:

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

Кроме того:

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

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

Граф направленного цикла

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

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

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

Граф ориентированных циклов имеет равномерную входную степень 1 и равномерную выходную степень 1.

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

См. также

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

Источники

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

Внешние ссылки

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