Loading AI tools
З Вікіпедії, вільної енциклопедії
Циклічний граф або граф-цикл — у теорії графів, це граф, який складається з єдиного циклу, або, іншими словами, деякого числа вершин, з'єднаних замкнутим ланцюгом. Граф-цикл з n вершинами позначають як Cn. Число вершин у Cn дорівнює числу ребер і кожна вершина має ступінь 2, тобто будь-яка вершина інцидентна рівно двом ребрам.
Цикл | |
---|---|
![]() Циклічний граф довжини 6 | |
Вершин | n |
Ребер | n |
Обхват | n |
Автоморфізм | 2n (Dn) |
Хроматичне число | 3 якщо n непарне і 2, якщо парне |
Хроматичний індекс | 3 якщо n непарне і 2, якщо парне |
Спектр | {2 cos(2 kπ / n), k=1, ... , n}[1] |
Властивості | 2-регулярний з постійною відстанню одиниця гамільтонів |
Позначення |
Граф-цикл має багато синонімів. Використовують терміни простий граф-цикл і циклічний граф, хоча останній термін вживається не часто, оскільки він може стосуватися графів, що не є ациклічними. Іноді вживаються терміни цикл, багатокутник або n-кутник. Цикл з парним числом вершин називають парним циклом, а з непарним числом вершин — непарним циклом.
Граф-цикл:
Додатково:
Подібно до платонових графів, циклічні графи утворюють кістяки двогранників. Двоїстими їм є дипольні графи[en], які утворюють кістяки осоедрів.
Орієнтованим графом-циклом називається орієнтована версія графа-циклу, в якому всі дуги спрямовані в одному і тому ж напрямку. У орієнтованому графі множина дуг, які містять хоча б одну дугу з кожного орієнтованого циклу, називається розриваючую множиною дуг[en]. Подібним чином, множина вершин, що містять щонайменше одну вершину з кожного орієнтованого циклу, називається розриваючую множиною вершин[en].
Орієнтований граф-цикл має постійну полуступень заходу 1 і постійну полуступень результату 1.
Орієнтовані графи-цикли є графами Келі циклічних груп (див., наприклад, Тревізана).
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.