График ладей - Rooks graph

График ладьи
График ладьи 8x8
Вершины	нм
Края	нм(п + м)/2 − нм
Диаметр	2
Обхват	3 (если Максимум(п, м) ≥ 3)
Хроматическое число	Максимум(п, м)
Характеристики	обычный, вершинно-транзитивный, идеально хорошо покрытый
Таблица графиков и параметров

В теория графов, а график ладьи это график, который представляет все разрешенные ходы ладья шахматы кусок на шахматная доска. Каждая вершина града ладьи представляет собой квадрат на шахматной доске, а каждое ребро представляет собой допустимый ход с одной клетки на другую. Те же графики можно определить математически как Декартовы произведения из двух полные графики или как линейные графики из полные двудольные графы.

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

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

Определение

An п × м График ладьи представляет ходы ладьи на п × м шахматная доска.^[1]Его вершинам можно дать координаты (Икс, у), куда 1 ≤ Икс ≤ п и 1 ≤ у ≤ м. Две вершины (Икс₁, у₁) и (Икс₂,у₂) смежны тогда и только тогда, когда либо Икс₁ = Икс₂ или же у₁ = у₂; то есть, если они принадлежат к одному и тому же рангу или одной вертикали шахматной доски.^[1]

Для п × м граф ладьи общее количество вершин просто нм. Для п × п граф ладьи общее количество вершин просто п² а общее количество ребер равно п³ − п²; в этом случае граф также известен как двумерный Граф Хэмминга^[2] или Латинский квадрат график.^[3]

График ладьи для п × м шахматную доску также можно определить как Декартово произведение из двух полные графики K_п и K_м, выраженный одной формулой как K_п ◻ K_м. В дополнительный граф из 2 × п График ладьи - это граф короны.

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

Луна (1963) и Хоффман (1964) обратите внимание, что ${\displaystyle m\times n}$ График ладьи обладает всеми следующими свойствами:

• Она имеет ${\displaystyle mn}$ вершины, каждая из которых смежна с ${\displaystyle m+n-2}$ края.
• Когда ${\displaystyle m\neq n}$, точно ${\displaystyle n{\tbinom {m}{2}}}$ края принадлежат ${\displaystyle m-2}$ треугольники и остальные ${\displaystyle m{\tbinom {n}{2}}}$ края принадлежат ${\displaystyle n-2}$ треугольники. Когда ${\displaystyle m=n}$, каждое ребро принадлежит ${\displaystyle m-2=n-2}$ треугольники.
• Каждые две вершины, не смежные друг с другом, принадлежат единственному ${\displaystyle 4}$-вертекс цикл.

Как они показывают, кроме случая ${\displaystyle m=n=4}$, эти свойства однозначно характеризуют график ладьи. То есть графы ладьи - единственные графы, подчиняющиеся всем этим свойствам.^[4][5]

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

В Граф Шриханде вложен в тор. Это не ладейный график, но строго регулярный с теми же параметрами, что и у ${\displaystyle 4\times 4}$ График ладьи.

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

Симметрия

Графики Ладьи вершинно-транзитивный и ${\displaystyle (m+n-2)}$-обычный; это единственные регулярные графы, сформированные таким образом из ходов стандартных шахматных фигур.^[8] Когда ${\displaystyle m\neq n}$, симметрии графа ладьи формируются путем независимой перестановки строк и столбцов графа, так что группа автоморфизмов графика имеет ${\displaystyle m!n!}$ элементы. Когда ${\displaystyle m=n}$, граф обладает дополнительными симметриями, которые меняют местами строки и столбцы, поэтому количество автоморфизмов равно ${\displaystyle 2n!^{2}}$.^[9]

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

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

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

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

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

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

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

Поскольку граф ладьи идеален, количество цветов, необходимых для любой раскраски графа, равно размеру его самой большой клики. Клики в графе ладьи - это подмножества его строк и столбцов, и самые большие из них имеют размер Максимум(м, п), так что это также хроматическое число графа. An п-раскрашивание п × п график ладьи можно интерпретировать как Латинский квадрат: описывает способ заполнения строк и столбцов п × п сетка с п разные значения таким образом, чтобы одно и то же значение не появлялось дважды ни в одной строке или столбце.^[16] Хотя найти оптимальную окраску графика ладьи несложно, это НП-полный чтобы определить, можно ли распространить частичную раскраску до раскраски всего графа (эта задача называется расширение предварительной окраски ). Эквивалентно, NP-полный, чтобы определить, может ли частичный латинский квадрат быть завершен до полного латинского квадрата.^[17]

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

	а	б	c	d	е	ж	грамм	час
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	а	б	c	d	е	ж	грамм	час

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

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

Графики Ладьи хорошо покрытые графики: каждый независимый набор в графе ладьи может быть расширен до максимально независимого множества, и каждый максимальное независимое множество в ладейной графе такой же размер, мин (м, п).^[18]

Господство

В число господства графа - это минимальная мощность среди всех доминирующих множеств. На графе ладьи набор вершин является доминирующим множеством тогда и только тогда, когда соответствующие им поля либо занимают, либо находятся на удалении ладьи от всех полей на графе. м × п доска. Для м × п доска номер доминирования мин (м, п).^[19]

На графе ладьи k-доминантное множество - это набор вершин, соответствующие клетки которых атакуют все остальные клетки (ходом ладьи) как минимум k раз. А k-набор доминирующего множества на графе ладьи - это множество вершин, соответствующие квадраты которых атакуют все остальные клетки как минимум k раз и сами подвергаются нападению по крайней мере k − 1 раз. Минимальная мощность среди всех k-доминантное и k-набора доминирующих множеств являются k-число доминирования и kчисло доминирования пары соответственно. На квадратной доске и даже на k, то k- номер доминирования нк/2 когда п ≥ (k² − 2k)/4 и k < 2п. Аналогичным образом kчисло доминирования пары п(k + 1)/2 когда k странно и меньше 2п.^[20]

Смотрите также

3-3 дуопризма

• 3-3 дуопризма, 4-мерный многогранник, имеющий ${\displaystyle 3\times 3}$ граф ладьи как граф его вершин и ребер
• Граф короля и Граф рыцаря, два других графа, определенные по ходам шахматных фигур
• Решетчатый граф, график горизонтального и вертикального примыкания квадратов на шахматной доске
• Судоку граф, суперграф графа Ладьи, соединяющий квадраты головоломки Судоку, которые должны иметь неравные значения

Рекомендации

1. Ласкар, Рену; Уоллис, Чарльз (1999), «Графики шахматной доски, связанные конструкции и параметры доминирования», Журнал статистического планирования и вывода, 76 (1–2): 285–294, Дои:10.1016 / S0378-3758 (98) 00132-3, МИСТЕР  1673351.
2. Азизоглу, М. Джемиль; Eğeciolu, Ömer (2003), "Экстремальные множества, минимизирующие нормированную размерностью границу в графах Хэмминга", Журнал SIAM по дискретной математике, 17 (2): 219–236, Дои:10.1137 / S0895480100375053, МИСТЕР  2032290.
3. Goethals, J.-M .; Зайдель, Дж. Дж. (1970), "Сильно регулярные графы, полученные из комбинаторных планов", Канадский математический журнал, 22 (3): 597–614, Дои:10.4153 / CJM-1970-067-9, МИСТЕР  0282872.
4. Мун, Дж. У. (1963), "На линейном графике полного биграфа", Анналы математической статистики, 34 (2): 664–667, Дои:10.1214 / aoms / 1177704179.
5. Хоффман, А. Дж. (1964), «О линейном графе полного двудольного графа», Анналы математической статистики, 35 (2): 883–885, Дои:10.1214 / aoms / 1177703593, МИСТЕР  0161328.
6. Фиала, Ник С .; Хемерс, Виллем Х. (2006), "5-хроматические сильно регулярные графы", Дискретная математика, 306 (23): 3083–3096, Дои:10.1016 / j.disc.2004.03.023, МИСТЕР  2273138.
7. Буриченко, В. П .; Махнев, А. А. (2011), «Об автоморфизмах сильно регулярных локально циклических графов», «Об автоморфизмах сильно регулярных локально циклических графов», Доклады Академии Наук (на русском), 441 (2): 151–155, МИСТЕР  2953786. Переведено на Доклады Математики 84 (3): 778–782, 2011, Дои:10.1134 / S1064562411070076. С первой страницы перевода: «Шрихандеграф - единственный сильно регулярный локально гексагональный граф с параметрами (16, 6, 2, 2)».
8. Лось, Ноам, Глоссарий теории графов.
9. Харари, Фрэнк (1958), «О количестве двухцветных графиков», Тихоокеанский математический журнал, 8 (4): 743–755, Дои:10.2140 / pjm.1958.8.743, МИСТЕР  0103834. См., В частности, уравнение (10), стр. 748 для группы автоморфизмов ${\displaystyle n\times n}$ график ладьи, и обсуждение выше уравнения для порядка этой группы.
10. Биггс, Норман (1974), "Симметрия линейных графиков", Utilitas Mathematica, 5: 113–121, МИСТЕР  0347684.
11. Это следует из определения графа ладьи как графа декартового произведения, а также предложения 4 Броэр, Изак; Хаттинг, Йоханнес Х. (1990), "Продукты циркулянтных графов", Quaestiones Mathematicae, 13 (2): 191–216, Дои:10.1080/16073606.1990.9631612, МИСТЕР  1068710.
12. Gray, R .; Макферсон, Д. (2010), "Счетные связно-однородные графы", Журнал комбинаторной теории, Серия B, 100 (2): 97–118, Дои:10.1016 / j.jctb.2009.04.002, МИСТЕР  2595694. См., В частности, теорему 1, которая идентифицирует эти графы как линейные графы полных двудольных графов.
13. Об эквивалентности декартовых произведений полных графов и линейных графов полных двудольных графов см. de Werra, D .; Герц, А. (1999), «О совершенстве сумм графиков» (PDF), Дискретная математика, 195 (1–3): 93–101, Дои:10.1016 / S0012-365X (98) 00168-X, МИСТЕР  1663807.
14. де Верра и Герц (1999).
15. Чудновский, Мария; Робертсон, Нил; Сеймур, Пол; Томас, Робин (2006), «Сильная теорема о совершенном графе» (PDF), Анналы математики, 164 (1): 51–229, arXiv:математика / 0212070, Дои:10.4007 / анналы.2006.164.51, JSTOR  20159988.
16. Об эквивалентности полных двудольных графов с раскраской ребер и латинских квадратов см., Например, LeSaulnier, Timothy D .; Стокер, Кристофер; Wenger, Paul S .; Запад, Дуглас Б. (2010), «Радужное сопоставление в графах с краями», Электронный журнал комбинаторики, 17 (1): Примечание 26, 5, Дои:10.37236/475, МИСТЕР  2651735.
17. Колборн, Чарльз Дж. (1984), "Сложность завершения частичных латинских квадратов", Дискретная прикладная математика, 8 (1): 25–30, Дои:10.1016 / 0166-218X (84) 90075-1, МИСТЕР  0739595.
18. Для эквивалентного утверждения о свойстве хорошо покрытых ладейных графов в терминах паросочетаний в полных двудольных графах см. Самнер, Дэвид П. (1979), "Случайно совпадающие графы", Журнал теории графов, 3 (2): 183–186, Дои:10.1002 / jgt.3190030209, HDL:10338.dmlcz / 102236, МИСТЕР  0530304.
19. Яглом, А.М.; Яглом, И.М. (1987), «Решение проблемы 34b», Сложные математические задачи с элементарными решениями, Дувр, стр. 77, ISBN  9780486318578.
20. Берчетт, Пол; Лейн, Дэвид; Лахниет, Джейсон (2009), "K-доминирование и k-водное доминирование на графе ладьи и другие результаты », Congressus Numerantium, 199: 187–204.

внешняя ссылка

• Вайсштейн, Эрик В. «Решетчатый граф». MathWorld.