Туровий граф

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

Визначення

Туровий граф $n\times m$ представляє допустимі ходи тури на дошці $n\times m$. Вершинам графа можна задати координати $(x,y)$, де $1\le x\le n$ та $1\le y\le 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◻K_m$_. Доповнення турового графа $2\times n$ є короною.

Симетрія

Турові графи вершинно-транзитивні та $(n+m-2)$-регулярні. Це єдиний клас регулярних графів, який можна побудувати на основі ходів стандартних шахових фігурШаблон:Sfn. Якщо $m\ne 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)$.

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

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

Опис

МунШаблон:Sfn описує туровий граф $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\ne 4$. Якщо $n=4$, існує ще один регулярний граф, а саме, граф Шрікханде, який має такі ж параметри, що й туровий граф $4\times 4$. Граф Шрікханде відрізняється від турового графа $4\times 4$ тим, що окіл будь-якої вершини графа Шрікханде пов'язаний у цикл довжини 6, тоді як у туровому графі він належить двом трикутникам.

Домінування

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

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

Див. також

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

Література

• Шаблон:Стаття
• 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]. 
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• van der Hofstad, Remco & Luczak, Malwina J. (2008), Random subgraphs of the 2D Hamming graph: the supercritical phase, arΧiv:0801.1607 [math.PR]. 
• Шаблон:Стаття
• 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]. 
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Книга

Посилання

• Шаблон:Mathworld