Циркулянтний граф
В теорії графів циркулянтним графом називається неорієнтований граф, який має циклічну групу симетрій, яка включає симетрію, при якій граф переводить вершину в будь-яку іншу вершину.
Еквівалентні визначення
Циркулянтні графи можуть бути визначені кількома еквівалентними способами[1]:
- Автоморфізм групи графа містить циклічну підгрупу, яка діє транзитивно на вершини графа.
- Граф має матрицю суміжності, що є циркулянтною матрицею.
- вершин графа можна пронумерувати числами від 0 до n− 1 таким чином, що якщо дві вершини з номерами та суміжні, то будь-які дві вершини з номерами і (z−x+y) modn теж суміжні.
- Граф можна намалювати (з можливими перетинами ребер) так, що його вершини лежать в кутах правильного багатокутника та будь-який поворот багатокутника в себе є симетрією малюнка (отримуємо той же малюнок).
Приклади
Будь-який цикл є циркулянтних графом, як і будь-яка корона.
Графи Пелі порядку (де — просте число, порівнянне з 1 по модулю 4) — це графи, в яких вершини є числами від 0 до n− 1 і дві вершини суміжні, якщо різниця відповідних чисел є квадратичним відрахуванням по модулю . Внаслідок того, що присутність або відсутність ребра залежить лише від різниці номерів вершин по модулю , будь-який граф Пелі є циркулянтним графом.
Будь-які драбини Мебіуса є циркулянтним графом, як і будь-який повний граф. Повний дводольний граф є циркулянтним, якщо обидві його частини мають однакову кількість вершин.
Якщо два числа та взаємно прості, то m×n Туровий граф (граф, що має вершину в кожній клітині щахової дошки m×n та ребра між будь-якими двома клітинами, якщо тура може перейти з однієї клітини на іншу за один хід) є циркулянтним графом. Це є наслідком того, що його симетрії містять як підгрупу циклічну групу . Як узагальнення цього випадку, декартів добуток графів між будь-якими циркулянтними графами з та вершинами дає внаслідок циркулянтний граф.[1]
Багато з відомих нижніх меж чисел Рамсея з'являються з прикладів циркулянтних графів, що мають маленькі максимальні кліки та маленькі максимальні незалежні множини.[2]
Конкретний приклад
Циркулянтний граф з межами визначається як граф з вузлами, пронумерованими числами та кожний вузел суміжний з 2k вузлами по модулю .
- Граф пов'язаний тоді і лише тоді, коли НСД.
- Якщо фіксовані цілі, то число остовних дерев , де задовольняє рекурентне співвідношення порядку .
- Зокрема, , де — n-е число Фібоначчі.
Самодоповняльні циркулянти
Самодоповняльний граф — це граф, в якому видалення наявних ребер та додавання відсутніх дає граф, ізоморфний вихідному. Наприклад, циклічний граф з п'ятьма вершинами самодоповняльний і є також циркулянтним. У більш загальному вигляді, будь-який граф Пелі є самодоповняльним циркулянтним графом.[3] Хорст Сакс показав, що якщо число має властивість, що будь-який простий дільник порівнюваний з 1 по модулю 4, то існує самодоповняльний циркулянтний граф з вершинами. Він висловив гіпотезу, що ця умова необхідна, тобто при інших значеннях самодоповняльні циркулянтні графи не існують.[1][3] Гіпотезу через 40 років довів Вілфред (Vilfred).[1]
Гіпотеза Адамса
Визначимо циркулянтну нумерацію циркулянтних графів як маркування вершин графа числами від 0 до n− 1 таким чином, що якщо дві вершини та суміжні, то будь-які дві вершини з номерами і (z−x+y) modn теж суміжні. Еквівалентно, циркулянтна нумерація — це нумерація вершин, при якій матриця суміжності графа є циркулянтною матрицею.
Нехай — ціле, взаємно просте з , і нехай — будь-яке ціле число. Тоді лінійна функція ax+b перетворить циркулянтну нумерацію в іншу циркулянтну нумерацію. Андраш Адам (András Ádám) висловив гіпотезу, що лінійне відображення — єдиний спосіб перенумерації вершин графа, що зберігає властивість циркулянтності. Тобто, якщо та — два ізоморфних циркулянтних графи з різною нумерацією, то існує лінійне перетворення, що переводить нумерацію для в нумерацію для . Однак, як з'ясувалося, гіпотеза Адама не вірна. Контрприкладом служать графи та з 16-тьма вершинами в кожному; вершина в з'єднана з шістьма сусідами x± 1, x± 2, і x± 7 (по модулю 16), в той час як в шість сусідів — це x± 2, x± 3, і x ± 5 (по модулю 16). Ці два графи ізоморфні, але їх ізоморфізм не можна отримати за допомогою лінійного перетворення.[1]
Примітки
- V. Vilfred. ..
- Small Ramsey Numbers Архівовано 18 січня 2012 у Wayback Machine., Stanisław P. Radziszowski, Electronic J. Combinatorics, dynamic survey updated 2009.
- Horst Sachs. . — Т. 9..
Посилання
- Weisstein, Eric W. Circulant Graph(англ.) на сайті Wolfram MathWorld.