Циклічний граф або граф-цикл — у теорії графів, це граф, який складається з єдиного циклу, або, іншими словами, деякого числа вершин, з'єднаних замкнутим ланцюгом. Граф-цикл з n вершинами позначають як Cn. Число вершин у Cn дорівнює числу ребер і кожна вершина має ступінь 2, тобто будь-яка вершина інцидентна рівно двом ребрам.
Цикл | |
---|---|
Циклічний граф довжини 6 | |
Вершин | n |
Ребер | n |
Обхват | n |
Автоморфізм | 2n (Dn) |
Хроматичне число | 3 якщо n непарне і 2, якщо парне |
Хроматичний індекс | 3 якщо n непарне і 2, якщо парне |
Спектр | {2 cos(2 kπ / n), k=1, ... , n} |
Властивості | 2-регулярний з постійною відстанню одиниця гамільтонів |
Позначення |
Термінологія
Граф-цикл має багато синонімів. Використовують терміни простий граф-цикл і циклічний граф, хоча останній термін вживається не часто, оскільки він може стосуватися графів, що не є ациклічними. Іноді вживаються терміни цикл, багатокутник або n-кутник. Цикл з парним числом вершин називають парним циклом, а з непарним числом вершин — непарним циклом.
Властивості
Граф-цикл:
- пов'язаний
- 2-регулярний
- ейлерів
- гамільтонів
- з постійною відстанню одиниця
- розфарбовуваний у два кольори, якщо і тільки якщо має парне число вершин. Граф є двочасткових якщо і тільки якщо він не має непарних циклів (як подграфов).
- реберно-2-розфарбовуваний, якщо і тільки якщо має парне число вершин.
Додатково:
- Оскільки графи-цикли можна намалювати як правильний багатокутник, симетрії циклу з n вершинами ті ж самі, що й у правильного багатокутника з n сторонами, тобто діедральна група порядку 2n. Зокрема, існують симетрії, що переводять будь-яку вершину в будь-яку іншу вершину і будь-яке ребро будь-яке інше ребро, так що n-цикл є симетричним графом.
Подібно до платонових графів, циклічні графи утворюють кістяки (двогранників). Двоїстими їм є [en], які утворюють кістяки осоедрів.
Орієнтований граф-цикл
Орієнтованим графом-циклом називається орієнтована версія графа-циклу, в якому всі дуги спрямовані в одному і тому ж напрямку. У орієнтованому графі множина дуг, які містять хоча б одну дугу з кожного орієнтованого циклу, називається [en]. Подібним чином, множина вершин, що містять щонайменше одну вершину з кожного орієнтованого циклу, називається [en].
Орієнтований граф-цикл має постійну полуступень заходу 1 і постійну полуступень результату 1.
Орієнтовані графи-цикли є графами Келі циклічних груп (див., наприклад, Тревізана).
Див. також
Примітки
- Some simple graph spectra. win.tue.nl
Посилання
- Weisstein, Eric W. Cycle Graph(англ.) на сайті Wolfram MathWorld. (обговорення обох 2-регулярних цикл-графів і теоретико-груповий концепції циклічного графа).
- [en], Characters and Expansion.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет