У теорії графів туровий граф — граф, що представляє всі допустимі ходи тури на шахівниці: кожна вершина представляє клітинку на дошці, а ребра — можливі ходи. Турові графи є вкрай симетричними досконалими графами — їх можна описати в термінах числа трикутників, яким належить ребро, та існування циклу довжини 4, що включає будь-які дві несуміжні вершини.
Туровий граф | |
---|---|
Вершин | |
Ребер | |
Діаметр | 2 |
Обхват | 3 (якщо ) |
Хроматичне число | |
Властивості | регулярний вершинно-транзитивний досконалий |
Визначення
Туровий граф представляє допустимі ходи тури на дошці . Вершинам графа можна задати координати , де та . Дві вершини та суміжні тоді і лише тоді, коли або або . Тобто якщо вони лежать в одному рядку клітин (горизонтальному або вертикальному).
Для турового графа загальна кількість вершин дорівнює . Для квадратної дошки число вершин турового графа дорівнює і число ребер дорівнює . В останньому разі граф відомий як двовимірний (граф Геммінга).
Туровий граф на дошці можна визначити як прямий добуток двох повних графів . Доповнення турового графа є короною.
Симетрія
Турові графи вершинно-транзитивні та -регулярні. Це єдиний клас регулярних графів, який можна побудувати на основі ходів стандартних шахових фігур. Якщо , симетрії турових графів утворено незалежними перестановками рядків та стовпців графа. Якщо , у графа з'являються додаткові симетрії, які обмінюють рядки та стовпці. Туровий граф для квадратної шахівниці є симетричним.
Відстань між будь-якими двома вершинами турового графа дорівнює одиниці або двом, залежно від того, суміжні вони чи ні. Будь-які дві несуміжні вершини можна перевести в будь-які інші несуміжні вершини за допомогою симетрії графа. Якщо туровий граф не квадратний, пари суміжних вершин розпадаються на дві орбіти групи симетрій відповідно до їх суміжності — по горизонталі або по вертикалі, але в разі квадратного графа будь-які дві суміжні вершини можна перевести з однієї в іншу за допомогою симетрії і, таким чином, граф дистанційно-транзитивний.
Якщо і взаємно прості, група симетрій турового графа містить як підгрупу циклічну групу , яка діє шляхом перестановки вершин циклічно. Отже, в цьому випадку туровий граф є циркулянтним.
Досконалість
Туровий граф можна розглядати як реберний граф повного двочасткового графа . Тобто, він має по вершині для кожного ребра і дві вершини турового графа суміжні тоді й лише тоді, коли відповідні ребра повного двочасткового графа мають спільну вершину. З цього погляду ребро двочасткового графа, що з'єднує вершину однієї сторони з вершиною іншої сторони, відповідає клітинці шахівниці з координатами .
Будь-який двочастковий граф є підграфом повного двочасткового графа, отже будь-який реберний граф двочасткового графа є породженим підграфом турового графа. Реберний граф двочасткового графа досконалий — в ньому і в будь-якому його породженому підграфі число кольорів, необхідних для будь-якого розфарбування вершин, дорівнює кількості вершин у найбільшій кліці. Реберні графи двочасткових графів утворюють важливе сімейство досконалих графів, одне з небагатьох сімейств, використаних Чудновською зі співавторами для опису досконалих графів і для того, щоб показати, що будь-який граф без непарних дір і антидір досконалий. Зокрема, досконалими є турові графи.
Оскільки турові графи досконалі, кількість кольорів, які потрібні для розфарбвання графа, дорівнює розміру найбільшої кліки. Кліки турового графа є підмножинами його рядків і стовпців і найбільша має розмір , отже, це число є хроматичним числом графа. -колірне розфарбування турового графа можна розглядати як латинський квадрат — він описує спосіб заповнення рядків і стовпців -ґратки різними значеннями, за якого жодне значення не з'являється двічі в рядках і стовпцях.
a | b | c | d | e | f | g | h | ||
8 | 8 | ||||||||
7 | 7 | ||||||||
6 | 6 | ||||||||
5 | 5 | ||||||||
4 | 4 | ||||||||
3 | 3 | ||||||||
2 | 2 | ||||||||
1 | 1 | ||||||||
a | b | c | d | e | f | g | h |
Незалежна множина в туровому графі — це множина вершин, жодні дві з яких не належать одному рядку або стовпцю графа. У термінах шахів це відповідає розташуванню тур, жодні дві з яких не атакують одна одну. Досконалі графи можна також описати як графи, в яких для будь-якого породженого підграфа розмір найбільшої незалежної множини дорівнює числу клік у розкладі вершин графа на найменше число клік. У туровому графі множина рядків або стовпців (менша з них) утворює такий оптимальний розклад. Отже, розмір найбільшої незалежної множини дорівнює . Будь-яке оптимальне розфарбування в туровому графі є найбільшою незалежною множиною.
Опис
Мун описує туровий граф як єдиний граф, що має такі властивості:
- він має вершин, кожна з яких інцидентна ребрам;
- ребер належать трикутникам, а решта ребер належать трикутникам;
- будь-які дві несуміжні вершини належать єдиному циклу із 4 вершин.
Якщо , ці умови можна спростити до твердження, що граф є сильно регулярним графом з параметрами , і що будь-який сильно регулярний граф з такими параметрами має бути туровим графом якщо . Якщо , існує ще один регулярний граф, а саме, граф Шрікханде, який має такі ж параметри, що й туровий граф . Граф Шрікханде відрізняється від турового графа тим, що окіл будь-якої вершини графа Шрікханде пов'язаний у цикл довжини 6, тоді як у туровому графі він належить двом трикутникам.
Домінування
Число домінування графа — це найменший розмір множини серед усіх домінівних множин. У туровому графі множина вершин є домінівною множиною тоді й лише тоді, коли будь-яка клітинка дошки або належать до множини, або за один хід від елемента множини. Для дошки число домінування дорівнює .
Для турового графа -домінівна множина — це множина вершин, відповідні клітинки яких атакують усі інші клітинки (ходом тури) принаймні разів. -кратна домінівна множина для турового графа — це множина вершин, відповідні клітинки яких атакують усі інші клітинки (ходом тури) принаймні разів і атакують свої клітинки не менше разів. Найменший розмір серед усіх -домінівних множин і -кратних домінівних множин — це -домінівне число і -кратне домінівне число відповідно. На квадратній дошці для парних -домінівне число дорівнює при та . Аналогічно -кратне домінівне число дорівнює коли непарне і менше ніж .
Див. також
- (Граф ходів короля)
- Граф ходів коня
- Решітка
- (Граф Геймса)
Примітки
Література
- 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 // . — 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: .
- [en]. Graph theory glossary. — 2004.
- A. J. Hoffman. On the line graph of the complete bipartite graph // . — 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 // . — 1963. — Т. 34, вип. 2. — С. 664—667. — DOI: .
- D. de Werra, A. Hertz. On perfectness of sums of graphs // . — 1999. — Т. 195, вип. 1—3. — С. 93—101. — DOI: .
- Яглом А. М., Яглом И. М. Неэлементарные задачи в элементарном изложении. — Dover, 1987.
Посилання
- Weisstein, Eric W. Граф решітки(англ.) на сайті Wolfram MathWorld.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет