| График цикла | |
|---|---|
 График цикла длины 6 | |
| Вершины | п |
| Края | п |
| Обхват | п |
| Автоморфизмы | 2 n ( D n ) |
| Хроматическое число | 3, если n нечетно 2, иначе |
| Хроматический индекс | 3, если n нечетно 2, иначе |
| Спектр | {2 cos (2 k π / n ); k = 1, ..., n } [1] |
| Характеристики | 2-регулярный Вершинно-транзитивный Edge-транзитивный Гамильтониан Эйлерова расстояния |
| Обозначение | |
| Таблица графиков и параметров | |
В теории графов , A цикл графа или круговая диаграмма представляет собой график , который состоит из одного цикла , или, другими словами, некоторое число вершин (по крайней мере 3, если граф является простым ) соединены в замкнутой цепи. Граф циклов с n вершинами называется C n . Количество вершин в C n равно количеству ребер , и каждая вершина имеет степень 2; то есть каждая вершина имеет ровно два инцидентных ей ребра.
Терминология [ править ]
У слова «график цикла» много синонимов . К ним относятся простой циклический граф и циклический граф , хотя последний термин используется реже, поскольку он также может относиться к графам, которые просто не являются ациклическими . Среди теоретиков графов также часто используются цикл , многоугольник или n -угольник . Термин n -цикл иногда используется в других условиях. [2]
Цикл с четным числом вершин называется четным циклом ; цикл с нечетным числом вершин называется нечетным циклом .
Свойства [ править ]
График цикла:
- 2-ребро раскрашиваем тогда и только тогда, когда оно имеет четное число вершин
- 2-регулярный
- 2-вершина раскрашивается тогда и только тогда, когда у нее четное число вершин. В более общем смысле граф двудольный тогда и только тогда, когда он не имеет нечетных циклов ( Kőnig , 1936).
- Связаны
- Эйлеров
- Гамильтониан
- Единицы измерения расстояния график
Кроме того:
- В графиках цикла может быть обращены в правильных многоугольниках , то симметрии А. Н. п - цикла являются такими же , как у правильного многоугольника с п стороны, в группу диэдра порядка 2 п . В частности, существуют симметрии, переводящие любую вершину в любую другую вершину, а любое ребро - в любое другое ребро, поэтому n -цикл является симметричным графом .
Подобно платоновым графам , циклические графы образуют каркас диэдров . Их двойники - это дипольные графы , которые образуют каркас хозоэдров .
График направленного цикла [ править ]
Направлено цикл граф представляет собой ориентированный вариант графа цикла, причем все ребра ориентированы в том же направлении.
В ориентированном графе набор ребер, который содержит по крайней мере одно ребро (или дугу ) из каждого ориентированного цикла, называется набором дуг обратной связи . Точно так же набор вершин, содержащий хотя бы одну вершину из каждого направленного цикла, называется набором вершин обратной связи .
Ориентированный граф циклов имеет равномерную входную степень 1 и равномерную исходящую степень 1.
Графы ориентированных циклов - это графы Кэли для циклических групп (см., Например, Тревизан).
См. Также [ править ]
 | Викискладе есть медиафайлы, связанные с графиками цикла . |
- Полный двудольный граф
- Полный график
- Нулевой график
- График пути
Ссылки [ править ]
- ^ Некоторые простые графические спектры . win.tue.nl
- ^ "Проблема 11707". Амер. Математика. Ежемесячно . 120 (5): 469–476. Май 2013 г. doi : 10.4169 / amer.math.monthly.120.05.469 . JSTOR 10.4169 / amer.math.monthly.120.05.469 .
Внешние ссылки [ править ]
- Вайсштейн, Эрик В. "Цикл граф" . MathWorld .(обсуждение как 2-регулярных цикловых графов, так и теоретико-групповой концепции циклических диаграмм )
- Лука Тревизан , Персонажи и расширение .
