Циклічний граф

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
Цикл
Циклічний граф довжини 6
Вершинn
Реберn
Обхватn
Автоморфізм2n (Dn)
Хроматичне число3 якщо n непарне і 2, якщо парне
Хроматичний індекс3 якщо n непарне і 2, якщо парне
Спектр{2 cos(2 kπ / n), k=1, ... , n}[1]
Властивості2-регулярний
з постійною відстанню одиниця
гамільтонів
Позначення

Циклічний граф або граф-цикл — у теорії графів, це граф, який складається з єдиного циклу, або, іншими словами, деякого числа вершин, з'єднаних замкнутим ланцюгом. Граф-цикл з n вершинами позначають як Cn. Число вершин у Cn дорівнює числу ребер і кожна вершина має ступінь 2, тобто будь-яка вершина інцидентна рівно двом ребрам.

Термінологія

[ред. | ред. код]

Граф-цикл має багато синонімів. Використовують терміни простий граф-цикл і циклічний граф, хоча останній термін вживається не часто, оскільки він може стосуватися графів, що не є ациклічними. Іноді вживаються терміни цикл, багатокутник або n-кутник. Цикл з парним числом вершин називають парним циклом, а з непарним числом вершин — непарним циклом.

Властивості

[ред. | ред. код]

Граф-цикл:

Додатково:

Подібно до платонових графів, циклічні графи утворюють кістяки двогранників. Двоїстими їм є дипольні графи[en], які утворюють кістяки осоедрів.

Орієнтований граф-цикл

[ред. | ред. код]
Орієнтований граф-цикл довжини 8

Орієнтованим графом-циклом називається орієнтована версія графа-циклу, в якому всі дуги спрямовані в одному і тому ж напрямку. У орієнтованому графі множина дуг, які містять хоча б одну дугу з кожного орієнтованого циклу, називається розриваючую множиною дуг[en]. Подібним чином, множина вершин, що містять щонайменше одну вершину з кожного орієнтованого циклу, називається розриваючую множиною вершин[en].

Орієнтований граф-цикл має постійну полуступень заходу 1 і постійну полуступень результату 1.

Орієнтовані графи-цикли є графами Келі циклічних груп (див., наприклад, Тревізана).

Див. також

[ред. | ред. код]

Примітки

[ред. | ред. код]

Посилання

[ред. | ред. код]