Туровий граф

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
Туровий граф
Туровий граф 8x8
Вершин
Ребер
Діаметр 2
Обхват 3 (якщо )
Хроматичне число
Властивості регулярний
вершинно-транзитивний
досконалий
добре покритий

У теорії графів туровий граф — граф, що представляє всі допустимі ходи тури на шахівниці: кожна вершина представляє клітинку на дошці, а ребра — можливі ходи. Турові графи є вкрай симетричними досконалими графами — їх можна описати в термінах числа трикутників, яким належить ребро, та існування циклу довжини 4, що включає будь-які дві несуміжні вершини.

Визначення[ред. | ред. код]

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

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

Туровий граф на дошці можна визначити як прямий добуток двох повних графів . Доповнення турового графа є короною.

Симетрія[ред. | ред. код]

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

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

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

Досконалість[ред. | ред. код]

3×3 туровий граф, розфарбований трьома кольорами, в якому показано кліку, яка має три вершини. У цьому графі і в усіх його породжених підграфах хроматичне число дорівнює кліковому числу, тому він є досконалим.

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

Будь-який двочастковий граф є підграфом повного двочасткового графа, отже будь-який реберний граф двочасткового графа є породженим підграфом турового графа. Реберний граф двочасткового графа досконалий — в ньому і в будь-якому його породженому підграфі число кольорів, необхідних для будь-якого розфарбування вершин, дорівнює кількості вершин у найбільшій кліці. Реберні графи двочасткових графів утворюють важливе сімейство досконалих графів, одне з небагатьох сімейств, використаних Чудновською зі співавторами[2] для опису досконалих графів і для того, щоб показати, що будь-який граф без непарних дір і антидір досконалий. Зокрема, досконалими є турові графи.

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

abcdefgh
8
d8 біла тура
g7 біла тура
c6 біла тура
a5 біла тура
b4 біла тура
h3 біла тура
e2 біла тура
f1 біла тура
8
77
66
55
44
33
22
11
abcdefgh
Розташування восьми тур на шахівниці так, що вони не б'ють одна одну. Ці тури утворюють найбільшу незалежну множину у відповідному туровому графі

Незалежна множина в туровому графі — це множина вершин, жодні дві з яких не належать одному рядку або стовпцю графа. У термінах шахів це відповідає розташуванню тур, жодні дві з яких не атакують одна одну. Досконалі графи можна також описати як графи, в яких для будь-якого породженого підграфа розмір найбільшої незалежної множини дорівнює числу клік у розкладі вершин графа на найменше число клік. У туровому графі множина рядків або стовпців (менша з них) утворює такий оптимальний розклад. Отже, розмір найбільшої незалежної множини дорівнює . Будь-яке оптимальне розфарбування в туровому графі є найбільшою незалежною множиною.

Опис[ред. | ред. код]

Мун[3] описує туровий граф як єдиний граф, що має такі властивості:

  • він має вершин, кожна з яких інцидентна ребрам;
  • ребер належать трикутникам, а решта ребер належать трикутникам;
  • будь-які дві несуміжні вершини належать єдиному циклу із 4 вершин.

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

Домінування[ред. | ред. код]

Число домінування графа — це найменший розмір множини серед усіх домінівних множин. У туровому графі множина вершин є домінівною множиною тоді й лише тоді, коли будь-яка клітинка дошки або належать до множини, або за один хід від елемента множини. Для дошки число домінування дорівнює [4].

Для турового графа -домінівна множина — це множина вершин, відповідні клітинки яких атакують усі інші клітинки (ходом тури) принаймні разів. -кратна домінівна множина для турового графа — це множина вершин, відповідні клітинки яких атакують усі інші клітинки (ходом тури) принаймні разів і атакують свої клітинки не менше разів. Найменший розмір серед усіх -домінівних множин і -кратних домінівних множин — це -домінівне число і -кратне домінівне число відповідно. На квадратній дошці для парних -домінівне число дорівнює при та . Аналогічно -кратне домінівне число дорівнює коли непарне і менше ніж [5].

Див. також[ред. | ред. код]

Примітки[ред. | ред. код]

Література[ред. | ред. код]

Посилання[ред. | ред. код]