Туровий граф
Туровий граф | |
---|---|
Туровий граф 8x8 | |
Вершин | |
Ребер | |
Діаметр | 2 |
Обхват | 3 (якщо ) |
Хроматичне число | |
Властивості |
регулярний вершинно-транзитивний досконалий добре покритий |
У теорії графів туровий граф — граф, що представляє всі допустимі ходи тури на шахівниці: кожна вершина представляє клітинку на дошці, а ребра — можливі ходи. Турові графи є вкрай симетричними досконалими графами — їх можна описати в термінах числа трикутників, яким належить ребро, та існування циклу довжини 4, що включає будь-які дві несуміжні вершини.
Визначення[ред. | ред. код]
Туровий граф представляє допустимі ходи тури на дошці . Вершинам графа можна задати координати , де та . Дві вершини та суміжні тоді і лише тоді, коли або або . Тобто якщо вони лежать в одному рядку клітин (горизонтальному або вертикальному).
Для турового графа загальна кількість вершин дорівнює . Для квадратної дошки число вершин турового графа дорівнює і число ребер дорівнює . В останньому разі граф відомий як двовимірний граф Геммінга.
Туровий граф на дошці можна визначити як прямий добуток двох повних графів . Доповнення турового графа є короною.
Симетрія[ред. | ред. код]
Турові графи вершинно-транзитивні та -регулярні. Це єдиний клас регулярних графів, який можна побудувати на основі ходів стандартних шахових фігур[1]. Якщо , симетрії турових графів утворено незалежними перестановками рядків та стовпців графа. Якщо , у графа з'являються додаткові симетрії, які обмінюють рядки та стовпці. Туровий граф для квадратної шахівниці є симетричним.
Відстань між будь-якими двома вершинами турового графа дорівнює одиниці або двом, залежно від того, суміжні вони чи ні. Будь-які дві несуміжні вершини можна перевести в будь-які інші несуміжні вершини за допомогою симетрії графа. Якщо туровий граф не квадратний, пари суміжних вершин розпадаються на дві орбіти групи симетрій відповідно до їх суміжності — по горизонталі або по вертикалі, але в разі квадратного графа будь-які дві суміжні вершини можна перевести з однієї в іншу за допомогою симетрії і, таким чином, граф дистанційно-транзитивний.
Якщо і взаємно прості, група симетрій турового графа містить як підгрупу циклічну групу , яка діє шляхом перестановки вершин циклічно. Отже, в цьому випадку туровий граф є циркулянтним.
Досконалість[ред. | ред. код]
Туровий граф можна розглядати як реберний граф повного двочасткового графа . Тобто, він має по вершині для кожного ребра і дві вершини турового графа суміжні тоді й лише тоді, коли відповідні ребра повного двочасткового графа мають спільну вершину. З цього погляду ребро двочасткового графа, що з'єднує вершину однієї сторони з вершиною іншої сторони, відповідає клітинці шахівниці з координатами .
Будь-який двочастковий граф є підграфом повного двочасткового графа, отже будь-який реберний граф двочасткового графа є породженим підграфом турового графа. Реберний граф двочасткового графа досконалий — в ньому і в будь-якому його породженому підграфі число кольорів, необхідних для будь-якого розфарбування вершин, дорівнює кількості вершин у найбільшій кліці. Реберні графи двочасткових графів утворюють важливе сімейство досконалих графів, одне з небагатьох сімейств, використаних Чудновською зі співавторами[2] для опису досконалих графів і для того, щоб показати, що будь-який граф без непарних дір і антидір досконалий. Зокрема, досконалими є турові графи.
Оскільки турові графи досконалі, кількість кольорів, які потрібні для розфарбвання графа, дорівнює розміру найбільшої кліки. Кліки турового графа є підмножинами його рядків і стовпців і найбільша має розмір , отже, це число є хроматичним числом графа. -колірне розфарбування турового графа можна розглядати як латинський квадрат — він описує спосіб заповнення рядків і стовпців -ґратки різними значеннями, за якого жодне значення не з'являється двічі в рядках і стовпцях.
Незалежна множина в туровому графі — це множина вершин, жодні дві з яких не належать одному рядку або стовпцю графа. У термінах шахів це відповідає розташуванню тур, жодні дві з яких не атакують одна одну. Досконалі графи можна також описати як графи, в яких для будь-якого породженого підграфа розмір найбільшої незалежної множини дорівнює числу клік у розкладі вершин графа на найменше число клік. У туровому графі множина рядків або стовпців (менша з них) утворює такий оптимальний розклад. Отже, розмір найбільшої незалежної множини дорівнює . Будь-яке оптимальне розфарбування в туровому графі є найбільшою незалежною множиною.
Опис[ред. | ред. код]
Мун[3] описує туровий граф як єдиний граф, що має такі властивості:
- він має вершин, кожна з яких інцидентна ребрам;
- ребер належать трикутникам, а решта ребер належать трикутникам;
- будь-які дві несуміжні вершини належать єдиному циклу із 4 вершин.
Якщо , ці умови можна спростити до твердження, що граф є сильно регулярним графом з параметрами , і що будь-який сильно регулярний граф з такими параметрами має бути туровим графом якщо . Якщо , існує ще один регулярний граф, а саме, граф Шрікханде, який має такі ж параметри, що й туровий граф . Граф Шрікханде відрізняється від турового графа тим, що окіл будь-якої вершини графа Шрікханде пов'язаний у цикл довжини 6, тоді як у туровому графі він належить двом трикутникам.
Домінування[ред. | ред. код]
Число домінування графа — це найменший розмір множини серед усіх домінівних множин. У туровому графі множина вершин є домінівною множиною тоді й лише тоді, коли будь-яка клітинка дошки або належать до множини, або за один хід від елемента множини. Для дошки число домінування дорівнює [4].
Для турового графа -домінівна множина — це множина вершин, відповідні клітинки яких атакують усі інші клітинки (ходом тури) принаймні разів. -кратна домінівна множина для турового графа — це множина вершин, відповідні клітинки яких атакують усі інші клітинки (ходом тури) принаймні разів і атакують свої клітинки не менше разів. Найменший розмір серед усіх -домінівних множин і -кратних домінівних множин — це -домінівне число і -кратне домінівне число відповідно. На квадратній дошці для парних -домінівне число дорівнює при та . Аналогічно -кратне домінівне число дорівнює коли непарне і менше ніж [5].
Див. також[ред. | ред. код]
Примітки[ред. | ред. код]
Література[ред. | ред. код]
- Ján Beka. Kn-decomposition of the line graphs of complete bipartite graphs // Octogon Mathematical Magazine. — 2001. — Т. 9, вип. 1A. — С. 135–139.
- Bekmetjev, Airat & Hurlbert, Glenn (2004), The pebbling threshold of the square of cliques, arΧiv: math.CO/0406157 [math.CO].
- Berger-Wolf, Tanya Y. & Harris, Mitchell A. (2003), Sharp bounds for bandwidth of clique products, arΧiv: cs.DM/0305051 [cs.DM].
- Paul Burchett, David Lane, Jason Lachniet. K-domination and k-tuple domination on the rook's graph and other results // Congressus Numerantium. — 2009. — Т. 199. — С. 187—204.
- Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas. The strong perfect graph theorem // Annals of Mathematics. — 2006. — Т. 164, вип. 1. — С. 51—229. — DOI: .
- Elkies, Noam[en]. Graph theory glossary. — 2004.
- A. J. Hoffman. On the line graph of the complete bipartite graph // Annals of Mathematical Statistics. — 1964. — Т. 35, вип. 2. — С. 883—885. — DOI: .
- van der Hofstad, Remco & Luczak, Malwina J. (2008), Random subgraphs of the 2D Hamming graph: the supercritical phase, arΧiv:0801.1607 [math.PR].
- Renu Laskar, Charles Wallis. Chessboard graphs, related designs, and domination parameters // Journal of Statistical Planning and Inference. — 1999. — Т. 76, вип. 1—2. — С. 285—294. — DOI: .
- van der Hofstad, Remco; Luczak, Malwina J. & Spencer, Joel (2008), The second largest component in the supercritical 2D Hamming graph, arΧiv:0801.1608 [math.PR].
- G. MacGillivray, K. Seyffarth. Classes of line graphs with small cycle double covers // Australasian Journal of Combinatorics. — 2001. — Т. 24. — С. 91—114.
- J. W. Moon. On the line-graph of the complete bigraph // Annals of Mathematical Statistics. — 1963. — Т. 34, вип. 2. — С. 664—667. — DOI: .
- D. de Werra, A. Hertz. On perfectness of sums of graphs // Discrete Mathematics. — 1999. — Т. 195, вип. 1—3. — С. 93—101. — DOI: .
- Яглом А. М., Яглом И. М. Неэлементарные задачи в элементарном изложении. — Dover, 1987.
Посилання[ред. | ред. код]
- Weisstein, Eric W. Граф решітки(англ.) на сайті Wolfram MathWorld.