Граф Рука

В теории графов граф ладьи — это неориентированный граф , который представляет все допустимые ходы ладейной шахматной фигуры на шахматной доске . Каждая вершина ладейного графа представляет собой клетку на шахматной доске, и между любыми двумя клетками, разделяющими одну строку (ранг) или столбец (веревку), есть ребро, между которыми может перемещаться ладья . Эти графы можно построить для шахматных досок любой прямоугольной формы. Хотя ладейные графики имеют лишь незначительное значение в шахматной науке, они более важны в абстрактной математике графов благодаря своим альтернативным конструкциям: ладейные графики представляют собой декартово произведение двух полных графов и являются линейными графами полных двудольных графов . Графы квадратной ладьи представляют собой двумерные графы Хэмминга .

Графы Рука очень симметричны: они имеют симметрию, переводящую каждую вершину в любую другую вершину. В ладейных графах, определенных на квадратных шахматных досках, более строго, каждые два ребра симметричны, и каждая пара вершин симметрична каждой другой паре на том же расстоянии в ходах (что делает граф дистанционно-транзитивным ). Для прямоугольных шахматных досок, ширина и высота которых относительно простые , ладейные графы являются циркулянтными графами . За одним исключением, ладейные графы можно отличить от всех остальных графов только по двум свойствам: количеству треугольников, которым принадлежит каждое ребро, и существованию уникального $4$ - цикла , соединяющего каждую несмежную пару вершин.

Графы Рука — совершенные графы . Другими словами, каждое подмножество клеток шахматной доски можно раскрасить так, чтобы никакие два квадрата в строке или столбце не имели одинакового цвета, используя количество цветов, равное максимальному количеству клеток из подмножества в любой отдельной строке или столбце ( кликовое число индуцированного подграфа ). Этот класс индуцированных подграфов является ключевым компонентом разложения совершенных графов, используемого для доказательства сильной теоремы о совершенных графах , которая характеризует все совершенные графы. Число независимости и число доминирования ладейного графа равны наименьшему из значений ширины и высоты шахматной доски. С точки зрения шахмат, число независимости — это максимальное количество ладей, которые можно разместить, не атакуя друг друга; число доминирования — это минимальное число, необходимое для атаки на все незанятые клетки доски. Графы ладей представляют собой хорошо покрытые графы , а это означает, что размещение неатакующих ладей по одной никогда не застрянет, пока не будет достигнут набор максимального размера.

Определение и математические конструкции

График ладей размера $n \times m$ представляет ходы ладьи на шахматной доске размера $n \times m$ . ^[1] Его вершины представляют собой квадраты шахматной доски и могут иметь координаты $(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$ . (Если $x 1 = x 2$ , вершины имеют общую вертикаль и соединены вертикальным ходом ладьи; если $y 1 = y 2$ , они имеют общий ранг и соединены горизонтальным ходом ладьи.) ^[1]

Квадраты одного ранга или ряда напрямую связаны друг с другом, поэтому каждый ряд и ряд образуют клику — подмножество вершин, образующих полный граф . Полный ладейный граф для шахматной доски размера $n \times m$ может быть сформирован из этих двух видов клик как декартово произведение графов $K n ◻ K m$ . ^[2] Поскольку ладейный граф на квадратной шахматной доске представляет собой декартово произведение клик одинакового размера, он является примером графа Хэмминга . Его размерность как графа Хэмминга равна двум, и каждый двумерный граф Хэмминга является ладейным графом для квадратной шахматной доски. ^[3] Графы квадратных ладей также называются « графами латинских квадратов »; Применительно к латинскому квадрату его края описывают пары квадратов, которые не могут содержать одно и то же значение. ^[4] Графы судоку представляют собой ладейные графы с дополнительными ребрами, соединяющими квадраты головоломки судоку, которые должны иметь неравные значения. ^[5]

Геометрически ладейные графы могут быть образованы наборами вершин и ребер (скелетов ) семейства выпуклых многогранников , декартовых произведений пар соседних многогранников . ^[6] Например, дуопризма 3-3 представляет собой четырехмерную фигуру, образованную как декартово произведение двух треугольников , и в качестве скелета имеет ладейный граф $3 \times 3 .$ ^[7]

Регулярность и симметрия

Сильная регулярность

Мун (1963) и Хоффман (1964) отмечают, что ладейный граф (или, что то же самое, как они его описывают, линейный график полного двудольного графа ) обладает всеми следующими свойствами: $m\times n$ $K_{m,n}$

Он имеет вершины, по одной на каждую клетку шахматной доски. Каждая вершина примыкает к ребрам, соединяя ее с квадратами того же ранга и квадратами того же ряда. $мн$ $m\times n$ $m+n-2$ $м-1$ $n-1$
Треугольники в ладейном графе образованы тройками полей внутри одной шеренги или вертикали. При , треугольникам принадлежат ровно ребра (соединяющие квадраты одного ранга) ; остальные ребра (соединяющие квадраты в одном файле) принадлежат треугольникам. При , каждое ребро принадлежит треугольникам. $м\neq п$ $n{\tbinom {m}{2}}$ $м-2$ $m{\tbinom {n}{2}}$ $n-2$ $м = п$ $m-2=n-2$
Каждые две несмежные вершины принадлежат уникальному -вершинному циклу , а именно единственному прямоугольнику, использующему две вершины в качестве углов. $4$

Они показывают, что, за исключением случая , эти свойства однозначно характеризуют ладейный граф. То есть ладейные графы — единственные графы с таким количеством вершин, ребер, треугольников на ребро и с уникальным 4-циклом, проходящим через каждые две несмежные вершины. ^[8]^[9] $m=n=4$

При эти условия можно сократить, заявив, что ладейный граф представляет собой строго регулярный граф с параметрами . Эти параметры описывают количество вершин, количество ребер на вершину, количество треугольников на ребро и количество общих соседей для двух несмежных вершин соответственно. ^[1] И наоборот, каждый сильно регулярный граф с этими параметрами должен быть ладейным графом, если только . ^[8]^[9] $м = п$ $n\times n$ $\operatorname {srg} (n^{2},2n-2,n-2,2)$ $n\times n$ $n=4$

При существует другой сильно регулярный граф — граф Шрикханде с теми же параметрами, что и ладейный граф. ^[10] Граф Шрикханде подчиняется тем же свойствам, перечисленным Муном и Мозером. Его можно отличить от ладейного графа тем, что окрестность каждой вершины в графе Шрикханде соединена, образуя -цикл . Напротив, в ладейном графе окрестность каждой вершины образует два треугольника: один для ее ранга, другой для ее вертикали, без каких-либо ребер, ведущих из одной части окрестности в другую. ^[11] Другой способ отличить граф ладьи от графа Шрикханде использует числа покрытия клик : граф ладьи может быть покрыт четырьмя кликами (четырьмя рядами или четырьмя шеренгами шахматной доски), тогда как для покрытия графа Шрикханде необходимо шесть клик. . ^[10] $n=4$ $4\times 4$ $4\times 4$ $6$ $4\times 4$ $4\times 4$ $n=4$

Симметрия

Графы Рука вершинно-транзитивны , что означает, что они обладают симметрией, переводящей каждую вершину в любую другую вершину. Это означает, что каждая вершина имеет одинаковое количество ребер: они — правильные . Грады ладей — единственные регулярные графы, построенные таким образом из ходов стандартных шахматных фигур. ^[12] При , симметрии ладейного графа формируются путем независимой перестановки строк и столбцов графа, поэтому группа автоморфизмов графа имеет элементы. Когда граф имеет дополнительные симметрии, меняющие местами строки и столбцы, поэтому число автоморфизмов равно . ^[13] $(m+n-2)$ $м\neq п$ $м!п!$ $м = п$ $2n!^{2}$

Любые две вершины ладейного графа находятся на расстоянии одной или двух друг от друга в зависимости от того, являются ли они смежными или несмежными соответственно. Любые две несмежные вершины могут быть преобразованы в любые две другие несмежные вершины за счет симметрии графа. Когда ладейный граф неквадратный, пары соседних вершин попадают на две орбиты группы симметрии в зависимости от того, смежны ли они по горизонтали или по вертикали, но когда граф квадратный, любые две соседние вершины также могут быть отображены друг в друга с помощью симметрия, и поэтому граф дистанционно транзитивен . ^[14]

Когда и относительно просты , группа симметрии ладейного графа содержит в качестве подгруппы циклическую группу , которая действует путем циклической перестановки вершин. Следовательно, в данном случае ладейный граф является циркулянтным графом . ^[15] $м$ $п$ $S_{m}\times S_{n}$ $C_{mn}=C_{m}\times C_{n}$ $мн$

Графы квадратных ладей связно-однородны , а это означает, что каждый изоморфизм между двумя связными индуцированными подграфами может быть расширен до автоморфизма всего графа. ^[16]

Другие объекты недвижимости

Совершенство

Граф ладьи 3×3 (граф дуопризмы 3-3 ), раскрашенный тремя цветами и показывающий клику из трех вершин. В этом графе и каждом из его индуцированных подграфов хроматическое число равно кликовому числу, поэтому это совершенный граф.

Градный граф также можно рассматривать как линейный граф полного двудольного графа $Kn, m$ — то есть он имеет одну вершину для каждого ребра $Kn,$ $m$ $,$ $и$ две вершины ладейного графа смежны тогда и только тогда, $когда$ соответствующие ребра полного двудольного графа имеют общую конечную точку. ^[2]^[17] С этой точки зрения ребро в полном двудольном графе от $i$ -й вершины на одной стороне двудольного деления до $j$ -й вершины на другой стороне соответствует квадрату шахматной доски с координатами $(i, j)$ . ^[1]

Любой двудольный граф является подграфом полного двудольного графа и, соответственно, любой линейный граф двудольного графа является индуцированным подграфом ладейного графа. ^[18] Линейные графы двудольных графов совершенны : в них и в любом из их индуцированных подграфов количество цветов, необходимых для любой раскраски вершин , такое же, как количество вершин в наибольшем полном подграфе . Линейные графы двудольных графов образуют важное семейство совершенных графов: они являются одним из небольшого числа семейств, используемых Чудновским и др. (2006) охарактеризовать идеальные графы и показать, что каждый граф без нечетных дырок и нечетных антидырок совершенен. ^[19] В частности, ладейные графы сами по себе совершенны.

Поскольку ладейный граф идеален, количество цветов, необходимых для любой раскраски графа, равно размеру его наибольшей клики. Клики ладейного графа — это подмножества одной строки или одного столбца, и самые большие из них имеют размер $max(m, n)$ , поэтому это также хроматическое число графа. $n$ - раскраска ладейного графа размера n $\times n может$ интерпретироваться как латинский квадрат : она описывает способ заполнения строк и столбцов сетки $n \times n$ $n$ различными значениями таким образом, чтобы одно и то же значение не появлялось. дважды в любой строке или столбце. ^[20] Точно так же раскраска прямоугольного ладейного графа соответствует латинскому прямоугольнику . ^[21] Хотя найти оптимальную раскраску ладейного графа несложно, NP-полно определить, можно ли расширить частичную раскраску до раскраски всего графа (эта проблема называется расширением предварительной раскраски ). Аналогично, NP-полным является определение того, можно ли дополнить частичный латинский квадрат до полного латинского квадрата. ^[22]

Независимость

Неатакующее размещение восьми ладей на шахматной доске, образующее максимально независимый набор в соответствующем ладейном графе.

Независимым множеством в ладейном графе называется множество вершин, никакие две из которых не принадлежат одной строке или столбцу графа; в шахматных терминах это соответствует расстановке ладей, из которых никакие две не атакуют друг друга. Совершенные графы также можно описать как графы, в которых в каждом индуцированном подграфе размер наибольшего независимого множества равен числу клик в разбиении вершин графа на минимальное количество клик. В ладейном графе такое оптимальное разбиение образуют наборы строк или наборы столбцов (в зависимости от того, в каком из них меньше наборов). Таким образом, размер наибольшего независимого набора в графе равен $min(m, n)$ . ^[1]

Грачи ладей являются хорошо покрытыми графами : каждое независимое множество в ладейном графе может быть расширено до максимального независимого множества, и каждое максимальное независимое множество в ладейном графе имеет одинаковый размер $min(m, n)$ . ^[23]

Доминирование

Число доминирования графа — это минимальная мощность среди всех доминирующих множеств. На ладейном графе набор вершин является доминирующим множеством тогда и только тогда, когда соответствующие им клетки либо занимают, либо находятся на расстоянии хода ладьи от всех клеток на доске $m \times n$ . Для доски $m \times n$ число доминирования равно $min(m, n)$ . ^[24]

В ладейном графе $k$ -доминирующее множество — это множество вершин, соответствующие поля которого атакуют все остальные поля (посредством хода ладьи) не менее $k$ раз. Доминирующим набором $k$ -кортежа на ладейном графе является набор вершин, соответствующие поля которых атакуют все остальные поля не менее $k$ раз, а сами подвергаются атаке не менее $k - 1$ раз. Минимальная мощность среди всех $k$ -доминирующих и $k$ -кортежных доминантных наборов равна числу $k$ -доминирования и числу доминирования $k$ -кортежа соответственно. На квадратной доске и для четного $k число$ $k$ -доминирования равно $nk /2$ , когда $n \geq (k 2 - 2 k)/4$ и $k < 2 n$ . Аналогичным образом, число доминирования $k -кортежа равно$ $n (k + 1)/2,$ когда $k$ нечетно и меньше $2 n$ . ^[25]

гамильтоновость

Граф каждой ладьи содержит гамильтонов цикл . ^[26] Однако эти циклы могут включать ходы между клетками, расположенными далеко друг от друга в пределах одной строки или столбца шахматной доски. Вместо этого изучение «ходов ладьи» в шахматной математике обычно концентрируется на частном случае этих гамильтоновых циклов, когда ладья может перемещаться только на соседние поля. Эти одношаговые ладейные обходы существуют только на досках с четным числом полей. Они играют центральную роль в доказательстве теоремы Гомори о том, что если с стандартной шахматной доски удалить две клетки противоположных цветов, оставшиеся клетки всегда можно закрыть домино. ^[27] Они представлены наряду с рыцарскими турами в первой работе , посвященной шахматным турам, санскритской Кавьяланкаре 9-го века Рудраты . ^[28]

Спектр

Спектр ладейного графа ( собственные значения ее матрицы смежности ) состоит из четырех собственных значений , , , и . Поскольку все эти числа являются целыми числами, ладейные графы являются целочисленными . Существует только три класса графов (и конечное число исключительных графов), которые могут иметь четыре собственных значения, одно из которых равно ; один из трех классов — класс ладейных графов. Для большинства комбинаций и граф ладьи спектрально уникален: ни один другой граф не имеет такого же спектра. В частности, это верно, когда или , или когда сумма двух чисел равна не менее 18 и не имеет вида . ^[29] $m+n-2$ $м-2$ $n-2$ $-2$ $-2$ $м$ $п$ $m\times n$ $n=2$ $n=m-1$ $м$ $п$ $2t^{2}\pm t$

В других графиках

Графы, для которых соседи каждой вершины индуцируют ладейный граф, называются локально сеточными . Примеры включают графы Джонсона , для которых соседи каждой вершины образуют ладейный граф. Известны и другие примеры, а для некоторых ладейных графов известна полная классификация. Например, есть два графа, все окрестности которых являются ладейными графами: это граф Джонсона и граф дополнения ладейного графа. ^[30] ${\ displaystyle J (n, k)}$ $k\times (nk)$ $3\times 3$ $J(6,3)$ $4\times 4$

См. также

График Бишопа
Комплекс «Шахматная доска» , комплекс независимости ладейного графа.
график Кинга
Граф Найта
Решетчатый граф , граф горизонтальных и вертикальных смежностей квадратов на шахматной доске.
График королевы

Ссылки

^ abcde Ласкар, Рену ; Уоллис, Чарльз (1999), «Графики шахматной доски, связанные конструкции и параметры доминирования», Journal of Statistical Planning and Inference , 76 (1–2): 285–294, doi : 10.1016/S0378-3758(98)00132-3 , МР 1673351.
^ ab Stones, Дуглас С. (2010), «Многие формулы для числа латинских прямоугольников», Электронный журнал комбинаторики , 17 (1): Статья 1, 46, doi : 10.37236/487 , MR 2661404
^ Азизоглу, М. Джемиль; Эгечиоглу, Омер (2003), «Экстремальные множества, минимизирующие нормализованную по размерности границу в графах Хэмминга», SIAM Journal on Discrete Mathematics , 17 (2): 219–236, doi : 10.1137/S0895480100375053, MR 2032290.
^ Гетальс, Ж.-М.; Зайдель, Дж. Дж. (1970), «Строго регулярные графы, полученные на основе комбинаторных планов», Canadian Journal of Mathematics , 22 (3): 597–614, doi : 10.4153/CJM-1970-067-9 , MR 0282872, S2CID 199082328.
^ Герцберг, Агнес М .; Мурти, М. Рам (2007), «Квадраты судоку и хроматические многочлены» (PDF) , Уведомления Американского математического общества , 54 (6): 708–717, MR 2327972
^ Матшке, Бенджамин; Пфайфл, Джулиан; Пило, Винсент (2011), «Просимплициально-соседние многогранники», Дискретная и вычислительная геометрия , 46 (1): 100–131, arXiv : 0908.4177 , doi : 10.1007/s00454-010-9311-y, MR 2794360, S2CID 20703 10
^ Мур, Дуг (1992), «Понимание симплоидов», Кирк, Дэвид (редактор), Graphics Gems III , Academic Press , стр. 250–255, doi : 10.1016/b978-0-08-050755-2.50057-9
^ ab Moon, JW (1963), «О линейном графике полного биографа», Annals of Mathematical Статистика , 34 (2): 664–667, doi : 10.1214/aoms/1177704179.
^ Аб Хоффман, AJ (1964), «О линейном графике полного двудольного графа», Annals of Mathematical Статистика , 35 (2): 883–885, doi : 10.1214/aoms/1177703593 , MR 0161328.
^ аб Фиала, Ник С.; Хемерс, Виллем Х. (2006), «5-хроматические сильно регулярные графы», Discrete Mathematics , 306 (23): 3083–3096, doi : 10.1016/j.disc.2004.03.023 , MR 2273138.
^ Буриченко, Вице-президент; Махнев А.А. (2011), «Об автоморфизмах сильно регулярных локально циклических графов», Доклады Академии наук , 441 (2): 151–155, MR 2953786.. Переведено в Доклады Математики 84 (3): 778–782, 2011, doi :10.1134/S1064562411070076. С первой страницы перевода: «Граф Шрикханде — единственный сильно регулярный локально шестиугольный граф с параметрами (16, 6, 2, 2)».
^ Элкис, Ноам (осень 2004 г.), «Глоссарий теории графов», Семинар для первокурсников 23j: Шахматы и математика , факультет математики Гарвардского университета , получено 3 мая 2023 г..
^ Харари, Фрэнк (1958), «О количестве двухцветных графов», Pacific Journal of Mathematics , 8 (4): 743–755, doi : 10.2140/pjm.1958.8.743 , MR 0103834. См., в частности, уравнение (10), с. 748 для группы автоморфизмов ладейного графа и обсуждение выше уравнения порядка этой группы. $n\times n$
^ Биггс, Норман (1974), «Симметрия линейных графиков», Utilitas Mathematica , 5 : 113–121, MR 0347684.
^ Это следует из определения ладейного графа как декартова графа произведения вместе с предложением 4 Броэра, Изака; Хаттинг, Йоханнес Х. (1990), «Продукты циркулянтных графов», Quaestiones Mathematicae , 13 (2): 191–216, doi : 10.1080/16073606.1990.9631612, MR 1068710.
^ Грей, Р.; Макферсон, Д. (2010), «Счетные связно-однородные графы», Журнал комбинаторной теории , серия B, 100 (2): 97–118, doi : 10.1016/j.jctb.2009.04.002 , MR 2595694. См., в частности, теорему 1, которая идентифицирует эти графы как линейные графы полных двудольных графов.
^ Об эквивалентности декартовых произведений полных графов и линейных графов полных двудольных графов см. de Werra, D.; Герц, А. (1999), «О совершенстве сумм графов» (PDF) , Discrete Mathematics , 195 (1–3): 93–101, doi : 10.1016/S0012-365X(98)00168-X , MR 1663807.
^ де Верра и Герц (1999).
^ Чудновский, Мария ; Робертсон, Нил ; Сеймур, Пол ; Томас, Робин (2006), «Сильная теорема о совершенном графе» (PDF) , Annals of Mathematics , 164 (1): 51–229, arXiv : math/0212070 , doi : 10.4007/annals.2006.164.51, JSTOR 20159988, S2CID 119151552.
^ Об эквивалентности полных двудольных графов с раскраской ребер и латинских квадратов см., например, LeSaulnier, Timothy D.; Стокер, Кристофер; Венгер, Пол С.; Уэст, Дуглас Б. (2010), «Радужное сопоставление в графах с цветными ребрами», Electronic Journal of Combinatorics , 17 (1): Note 26, 5, doi : 10.37236/475 , MR 2651735.
^ Стоунз, Дуглас С. (2010), «Многие формулы для числа латинских прямоугольников», Electronic Journal of Combinatorics , 17 (1): A1:1 – A1:46, doi : 10.37236/487 , MR 2661404
^ Колборн, Чарльз Дж. (1984), «Сложность заполнения частичных латинских квадратов», Discrete Applied Mathematics , 8 (1): 25–30, doi : 10.1016/0166-218X(84)90075-1 , MR 0739595.
^ Эквивалентное утверждение хорошо изученного свойства ладейных графов в терминах паросочетаний в полных двудольных графах см. в Lesk, M.; Пламмер, доктор медицины; Пуллибланк, WR (1984), «Равносогласованные графы», в Боллобасе, Бела (редактор), Теория графов и комбинаторика: материалы Кембриджской комбинаторной конференции, в честь Пола Эрдеша , Лондон: Academic Press, стр. 239– 254, МР 0777180.
^ Яглом, А.М .; Яглом, И.М. (1987), «Решение проблемы 34b», Сложные математические задачи с элементарными решениями, Дувр, стр. 77, ISBN 9780486318578.
^ Берчетт, Пол; Лейн, Дэвид; Лачниет, Джейсон (2009), « $K$ -доминирование и $k$ -кортежное доминирование на ладейном графе и другие результаты», Congressus Numerantium , 199 : 187–204.
^ Херли, CB; Олдфорд, Р.В. (февраль 2011 г.), «Графы как навигационная инфраструктура для многомерных пространств данных», Computational Статистика , 26 (4): 585–612, doi : 10.1007/s00180-011-0228-6, S2CID 54220980
^ Уоткинс, Джон Дж. (2004), Через доску: Математика задач на шахматной доске , Princeton University Press, стр. 12, ISBN 9780691130620
^ Мюррей, HJR (январь 1902 г.), «Путешествие рыцаря: древнее и восточное», The British Chess Magazine , vol. 22, нет. 1, стр. 1–7
^ Дуб, Майкл (1970), «О характеристике некоторых графов с четырьмя собственными значениями по их спектрам», Линейная алгебра и ее приложения , 3 (4): 461–482, doi : 10.1016/0024-3795(70)90037-6 , МР 0285432
^ Коэн, Арье М. (1990), «Локальное распознавание графиков, зданий и связанных с ними геометрий» (PDF) , в Канторе, Уильям М.; Либлер, Роберт А.; Пейн, Стэнли Э.; Шульт, Эрнест Э. (ред.), Конечная геометрия, здания и смежные темы: материалы конференции по зданиям и связанным с ними геометриям, состоявшейся в Пингри-парке, штат Колорадо, 17–23 июля 1988 г. , Oxford Science Publications, Oxford University Press, стр. 85–94, МР 1072157.; см., в частности, стр. 89–90.

Внешние ссылки

Вайсштейн, Эрик В. , «Граф ладьи», MathWorld