Туровий граф

Туровий граф
Туровий граф 8x8
Вершин	${\displaystyle nm}$
Ребер	${\displaystyle nm(n+m)/2-nm}$
Діаметр	2
Обхват	3 (якщо ${\displaystyle max(n,m)\geq 3}$)
Хроматичне число	${\displaystyle max(n,m)}$
Властивості	регулярний вершинно-транзитивний досконалий добре покритий

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

Визначення

Туровий граф ${\displaystyle n\times m}$ представляє допустимі ходи тури на дошці ${\displaystyle n\times m}$. Вершинам графа можна задати координати ${\displaystyle (x,y)}$, де ${\displaystyle 1\leq x\leq n}$ та ${\displaystyle 1\leq y\leq m}$. Дві вершини ${\displaystyle (x_{1},y_{1})}$ та ${\displaystyle (x_{2},y_{2})}$ суміжні тоді і лише тоді, коли або ${\displaystyle x_{1}=x_{2}}$ або ${\displaystyle y_{1}=y_{2}}$. Тобто якщо вони лежать в одному рядку клітин (горизонтальному або вертикальному).

Для турового графа ${\displaystyle n\times m}$ загальна кількість вершин дорівнює ${\displaystyle nm}$. Для квадратної дошки ${\displaystyle n\times n}$ число вершин турового графа дорівнює ${\displaystyle n^{2}}$ і число ребер дорівнює ${\displaystyle n^{3}-n^{2}}$. В останньому разі граф відомий як двовимірний граф Геммінга.

Туровий граф на дошці ${\displaystyle n\times m}$ можна визначити як прямий добуток двох повних графів ${\displaystyle K_{n}\square K_{m}}$_. Доповнення турового графа ${\displaystyle 2\times n}$ є короною.

Симетрія

Турові графи вершинно-транзитивні та ${\displaystyle (n+m-2)}$-регулярні. Це єдиний клас регулярних графів, який можна побудувати на основі ходів стандартних шахових фігур^[1]. Якщо ${\displaystyle m\neq n}$, симетрії турових графів утворено незалежними перестановками рядків та стовпців графа. Якщо ${\displaystyle n=m}$, у графа з'являються додаткові симетрії, які обмінюють рядки та стовпці. Туровий граф для квадратної шахівниці є симетричним.

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

Якщо ${\displaystyle m}$ і ${\displaystyle n}$ взаємно прості, група симетрій ${\displaystyle S_{m}\times S_{n}}$ турового графа містить як підгрупу циклічну групу ${\displaystyle C_{mn}=C_{m}\times C_{n}}$, яка діє шляхом перестановки ${\displaystyle mn}$ вершин циклічно. Отже, в цьому випадку туровий граф є циркулянтним.

Досконалість

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

Туровий граф можна розглядати як реберний граф повного двочасткового графа ${\displaystyle K_{n,m}}$. Тобто, він має по вершині для кожного ребра ${\displaystyle K_{n,m}}$ і дві вершини турового графа суміжні тоді й лише тоді, коли відповідні ребра повного двочасткового графа мають спільну вершину. З цього погляду ребро двочасткового графа, що з'єднує вершину ${\displaystyle i}$ однієї сторони з вершиною ${\displaystyle j}$ іншої сторони, відповідає клітинці шахівниці з координатами ${\displaystyle (i,j)}$.

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

Оскільки турові графи досконалі, кількість кольорів, які потрібні для розфарбвання графа, дорівнює розміру найбільшої кліки. Кліки турового графа є підмножинами його рядків і стовпців і найбільша має розмір ${\displaystyle max(m,n)}$, отже, це число є хроматичним числом графа. ${\displaystyle n}$-колірне розфарбування ${\displaystyle n\times n}$ турового графа можна розглядати як латинський квадрат — він описує спосіб заповнення рядків і стовпців ${\displaystyle n\times n}$-ґратки ${\displaystyle n}$різними значеннями, за якого жодне значення не з'являється двічі в рядках і стовпцях.

	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

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

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

Опис

Мун^[3] описує туровий граф ${\displaystyle m\times n}$ як єдиний граф, що має такі властивості:

• він має ${\displaystyle mn}$ вершин, кожна з яких інцидентна ${\displaystyle n+m-2}$ ребрам;
• ${\displaystyle mn(m-1)/2}$ ребер належать ${\displaystyle m-2}$трикутникам, а решта ${\displaystyle mn(n-1)/2}$ ребер належать ${\displaystyle n-2}$ трикутникам;
• будь-які дві несуміжні вершини належать єдиному циклу із 4 вершин.

Якщо ${\displaystyle n=m}$, ці умови можна спростити до твердження, що граф ${\displaystyle n\times n}$ є сильно регулярним графом з параметрами ${\displaystyle srg(n^{2},2n-2,n-2,2)}$, і що будь-який сильно регулярний граф з такими параметрами має бути туровим графом ${\displaystyle n\times n}$ якщо ${\displaystyle n\neq 4}$. Якщо ${\displaystyle n=4}$, існує ще один регулярний граф, а саме, граф Шрікханде, який має такі ж параметри, що й туровий граф ${\displaystyle 4\times 4}$. Граф Шрікханде відрізняється від турового графа ${\displaystyle 4\times 4}$ тим, що окіл будь-якої вершини графа Шрікханде пов'язаний у цикл довжини 6, тоді як у туровому графі він належить двом трикутникам.

Домінування

Число домінування графа — це найменший розмір множини серед усіх домінівних множин. У туровому графі множина вершин є домінівною множиною тоді й лише тоді, коли будь-яка клітинка дошки або належать до множини, або за один хід від елемента множини. Для дошки ${\displaystyle m\times n}$ число домінування дорівнює ${\displaystyle min(m,n)}$^[4].

Для турового графа ${\displaystyle k}$-домінівна множина — це множина вершин, відповідні клітинки яких атакують усі інші клітинки (ходом тури) принаймні ${\displaystyle k}$ разів. ${\displaystyle k}$-кратна домінівна множина для турового графа — це множина вершин, відповідні клітинки яких атакують усі інші клітинки (ходом тури) принаймні ${\displaystyle k}$ разів і атакують свої клітинки не менше ${\displaystyle k-1}$ разів. Найменший розмір серед усіх ${\displaystyle k}$-домінівних множин і ${\displaystyle k}$-кратних домінівних множин — це ${\displaystyle k}$-домінівне число і ${\displaystyle k}$-кратне домінівне число відповідно. На квадратній дошці для парних ${\displaystyle k}$ ${\displaystyle k}$-домінівне число дорівнює ${\displaystyle nk/2}$ при ${\displaystyle n\geq (k^{2}-2k)/4}$ та ${\displaystyle k<2n}$. Аналогічно ${\displaystyle k}$-кратне домінівне число дорівнює ${\displaystyle n(k+1)/2}$ коли ${\displaystyle k}$ непарне і менше ніж ${\displaystyle 2n}$^[5].

Див. також

• Граф ходів короля
• Граф ходів коня
• Решітка
• Граф Геймса

Примітки

1. Elkies, 2004.
2. Chudnovsky, Robertson, Seymour, Thomas, 2006.
3. Moon, 1963.
4. Яглом и Яглом, 1987.
5. Burchett, Lane, Lachniet, 2009.

Література

• Ján Beka. K_n-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:10.4007/annals.2006.164.51.
• 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:10.1214/aoms/1177703593.
• 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:10.1016/S0378-3758(98)00132-3.
• 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:10.1214/aoms/1177704179.
• D. de Werra, A. Hertz. On perfectness of sums of graphs // Discrete Mathematics. — 1999. — Т. 195, вип. 1—3. — С. 93—101. — DOI:10.1016/S0012-365X(98)00168-X.
• Яглом А. М., Яглом И. М. Неэлементарные задачи в элементарном изложении. — Dover, 1987.

Посилання

• Weisstein, Eric W. Граф решітки(англ.) на сайті Wolfram MathWorld.