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

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

Приклади Будь-який цикл є циркулянтним графом, як і будь-яка корона.

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

Будь-які драбини Мебіуса є циркулянтним графом, як і будь-який повний граф. Повний двочастковий граф є циркулянтним, якщо обидві його частини мають однакову кількість вершин.

Якщо два числа та взаємно прості, то туровий граф (граф, що має вершину в кожній клітині шахової дошки та ребра між будь-якими двома клітинами, якщо тура може перейти з однієї клітини на іншу за один хід) є циркулянтним графом. Це є наслідком того, що його симетрії містять як підгрупу циклічну групу . Як узагальнення цього випадку, декартів добуток графів між будь-якими циркулянтними графами з та вершинами дає внаслідок циркулянтний граф.

Багато з відомих нижніх меж чисел Ремзі з'являються з прикладів циркулянтних графів, що мають маленькі максимальні кліки та маленькі максимальні незалежні множини.Small Ramsey Numbers , Stanisław P. Radziszowski, Electronic J. Combinatorics, dynamic survey updated 2009.

Конкретний приклад

Циркулянтний граф з межами визначається як граф з вузлами, пронумерованими числами та кожний вузел суміжний з 2k вузлами по модулю .

Граф пов'язаний тоді і лише тоді, коли НСД.

Якщо фіксовані цілі, то число остовних дерев , де задовольняє рекурентне співвідношення порядку . Зокрема, , де  — n-е число Фібоначчі.

Самодоповняльні циркулянти

Самодоповняльний граф — це граф, в якому видалення наявних ребер та додавання відсутніх дає граф, ізоморфний вихідному. Наприклад, циклічний граф з п'ятьма вершинами самодоповняльний і є також циркулянтним. У більш загальному вигляді, будь-який граф Пелі є самодоповняльним циркулянтним графом.. показав, що якщо число має властивість, що будь-який простий дільник порівнюваний з 1 по модулю 4, то існує самодоповняльний циркулянтний граф з вершинами. Він висловив гіпотезу, що ця умова необхідна, тобто при інших значеннях самодоповняльні циркулянтні графи не існують. Гіпотезу через 40 років довів Вілфред (Vilfred).

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

Нехай  — ціле, взаємно просте з , і нехай  — будь-яке ціле число. Тоді лінійна функція перетворить циркулянтну нумерацію в іншу циркулянтну нумерацію. Андраш Адам (András Ádám) висловив гіпотезу, що лінійне відображення — єдиний спосіб перенумерації вершин графа, що зберігає властивість циркулянтності. Тобто, якщо та  — два ізоморфних циркулянтних графи з різною нумерацією, то існує лінійне перетворення, що переводить нумерацію для в нумерацію для . Однак, як з'ясувалося, гіпотеза Адама не вірна. Контрприкладом служать графи та з 16-тьма вершинами в кожному; вершина в з'єднана з шістьма сусідами , , і (по модулю 16), в той час як в шість сусідів — це , , і (по модулю 16). Ці два графи ізоморфні, але їх ізоморфізм не можна отримати за допомогою лінійного перетворення.

Примітки

Посилання