График цикла - Cycle graph
| График цикла | |
|---|---|
 Граф цикла длины 6
| |
| Вершины | п |
| Края | п |
| Обхват | п |
| Автоморфизмы | 2 н ( Д н ) |
| Хроматическое число | 3, если n нечетно 2, иначе |
| Хроматический индекс | 3, если n нечетно 2, иначе |
| Спектр | {2 cos (2 k π / n ); k = 1, ..., n } |
| Свойства |
2-регулярный Вершинно-транзитивный Edge-транзитивный Гамильтониан Эйлерова расстояния Единичное расстояние |
| Обозначение | |
| Таблица графиков и параметров | |
В теории графов , A цикл графа или круговая диаграмма представляет собой график , который состоит из одного цикла , или, другими словами, некоторое число вершин (по крайней мере 3, если граф является простым ) соединены в замкнутой цепи. Граф циклов с n вершинами называется C n . Количество вершин в C n равно количеству ребер , и каждая вершина имеет степень 2; то есть каждая вершина имеет ровно два инцидентных ей ребра.
Терминология
У слова «график цикла» много синонимов . К ним относятся простой циклический граф и циклический граф , хотя последний термин используется реже, поскольку он также может относиться к графам, которые просто не являются ациклическими . Среди теоретиков графов также часто используются цикл , многоугольник или n -угольник . Термин n -цикл иногда используется в других условиях.
Цикл с четным числом вершин называется четным циклом ; цикл с нечетным числом вершин называется нечетным циклом .
Свойства
График цикла:
- 2-ребро раскрашивается тогда и только тогда, когда оно имеет четное число вершин
- 2-регулярный
- 2-вершина раскрашивается тогда и только тогда, когда у нее четное число вершин. В более общем смысле граф является двудольным тогда и только тогда, когда он не имеет нечетных циклов ( Kőnig , 1936).
- Связано
- Эйлеров
- Гамильтониан
- Единицы измерения расстояния график
К тому же:
- В графиках цикла может быть обращены в правильных многоугольниках , то симметрии А. Н. п - цикла являются такими же , как у правильного многоугольника с п стороны, в группу диэдра порядка 2 п . В частности, существуют симметрии, переводящие любую вершину в любую другую вершину, а любое ребро - в любое другое ребро, поэтому n -цикл является симметричным графом .
Подобно платоновым графам , циклические графы образуют каркас диэдров . Их двойники - дипольные графы , которые образуют каркас хозоэдров .
График направленного цикла
Направлено цикл граф представляет собой ориентированный вариант графа цикла, причем все ребра ориентированы в том же направлении.
В ориентированном графе набор ребер, который содержит по крайней мере одно ребро (или дугу ) из каждого ориентированного цикла, называется набором дуг обратной связи . Точно так же набор вершин, содержащий хотя бы одну вершину из каждого направленного цикла, называется набором вершин обратной связи .
Ориентированный граф циклов имеет равномерную входную степень 1 и равномерную выходную степень 1.
Графы ориентированных циклов - это графы Кэли для циклических групп (см., Например, Тревизан).
Смотрите также
Ссылки
внешние ссылки
- Вайсштейн, Эрик В. "Цикл граф" . MathWorld .(обсуждение как 2-регулярных цикловых графов, так и теоретико-групповой концепции циклических диаграмм )
- Лука Тревизан , Персонажи и расширение .