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

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

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

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

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

Властивості

Граф-цикл:

• пов'язаний
• 2-регулярний
• ейлерів
• гамільтонів
• з постійною відстанню одиниця
• розфарбовуваний у два кольори, якщо і тільки якщо має парне число вершин. Граф є двочасткових якщо і тільки якщо він не має непарних циклів (як подграфов).
• реберно-2-розфарбовуваний, якщо і тільки якщо має парне число вершин.

Додатково:

• Оскільки графи-цикли можна намалювати як правильний багатокутник, симетрії циклу з n вершинами ті ж самі, що й у правильного багатокутника з n сторонами, тобто діедральна група порядку 2n. Зокрема, існують симетрії, що переводять будь-яку вершину в будь-яку іншу вершину і будь-яке ребро будь-яке інше ребро, так що n-цикл є симетричним графом.

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

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

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

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

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

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

Див. також

• Повний двочастковий граф
• Шлях (теорія графів)
• Повний граф

Примітки

1. Some simple graph spectra. win.tue.nl

Посилання

• Weisstein, Eric W. Cycle Graph(англ.) на сайті Wolfram MathWorld. (обговорення обох 2-регулярних цикл-графів і теоретико-груповий концепції циклічного графа).
• Люк Тревізана^[en], Characters and Expansion.