Циклічний граф
У теорії графів графом-цикла називається граф, що складається з єдиного циклу, або, іншими словами, деякого числа вершин, з'єднаних замкнутим ланцюгом. Граф-цикл з n вершинами позначають як Cn. Число вершин у Cn дорівнює числу ребер і кожна вершина має ступінь 2, тобто будь-яка вершина инцидентна рівно двом ребрам.
| Цикл | |
|---|---|
 Циклічний граф довжини 6 | |
| Вершин | n |
| Ребер | n |
| Обхват | n |
| Автоморфізм | 2n (Dn) |
| Хроматичне число | 3 якщо n непарна і 2, якщо парна |
| Хроматичний індекс | 3 якщо n непарна і 2, якщо парна |
| Властивості |
2-регулярний з постійною відстанню одиниця гамільтонів |
| Позначення | |
Термінологія
Граф-цикл має багато синонімів. Використовують терміни простий граф-цикл і циклічний граф, хоча останній термін вживається не часто, оскільки він може ставитися до графів, що не є ациклічні. Іноді вживаються терміни цикл, багатокутник або n-кутник. Цикл з парним числом вершин називають парним циклом, а з непарним числом вершин — непарним циклом.
Властивості
Граф-цикл:
- пов'язаний
- 2-регулярний
- ейлерів
- гамільтонів
- з постійною відстанню одиниця
- розфарбовуємо у два кольори, якщо і тільки якщо має парне число вершин. Граф є двочасткових якщо і тільки якщо він не має непарних циклів (як подграфов).
- реберно-2-розфарбовуємо, якщо і тільки якщо має парне число вершин.
Додатково:
- Оскільки графи-цикли можна намалювати як правильний багатокутник, симетрії циклу з n вершинами ті ж самі, що й у правильного багатокутника з n сторонами, тобто діедральна група порядку 2n. Зокрема, існують симетрії,що переводять будь-яку вершину в будь-яку іншу вершину і будь-яке ребро будь-яке інше ребро, так що n-цикл є симетричним графом.
Орієнтований граф-цикл
Орієнтованим графом-циклом називається орієнтована версія графу-циклу, в якому всі дуги спрямовані в одному і тому ж напрямку. У орієнтованому графі множина дуг, які містять хоча б одну дугу з кожного орієнтованого циклу, називається розриваючую множиною дуг . Подібним чином, множина вершин, що містять щонайменше одну вершину з кожного орієнтованого циклу, називається розриваючую множиною вершин .
Орієнтований граф-цикл має постійну полуступень заходу 1 і постійну полуступень результату 1.
Орієнтовані графи-цикли є графами Келі циклічних груп (див., наприклад, Тревізана).
Примітки
- Weisstein, Eric W. Cycle Graph(англ.) на сайті Wolfram MathWorld. (обговорення обох 2-регулярних цикл-графів і теоретико-груповий концепції циклічного графу).
- Люк Тревізана, Characters and Expansion.