Туровий граф

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

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

Визначення

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

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

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

Симетрія

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

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

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

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

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

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

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

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

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

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

Опис

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

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

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

Домінування

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

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

Див. також

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

Література

• 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. 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.