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