График королевы

График королевы
График королевы
7	7
6	6
5	5
4	4
3	3
2	2
1	1
Вершины
Хроматическое число	п, если
Характеристики	Двусвязный , гамильтониан
	Таблица графиков и параметров

В математике граф ферзя — это неориентированный граф , который представляет все допустимые ходы ферзя — шахматной фигуры — на шахматной доске . В графе каждая вершина представляет собой клетку на шахматной доске, а каждое ребро — это разрешенный ход, который может сделать ферзь, то есть ход по горизонтали, вертикали или диагонали на любое количество клеток. Если шахматная доска имеет размеры $m\times n$ , то индуцированный граф называется $m\times n$ граф королевы.

Независимые наборы графов соответствуют расположению нескольких ферзей, при котором никакие два ферзя не атакуют друг друга. Они изучаются в головоломке с восемью ферзями , где восемь не атакующих ферзей размещаются на штандарте. $8\times 8$ шахматная доска. Доминирующие наборы представляют собой расположение ферзей, в котором каждое поле атаковано или занято ферзем; пять королев, но не меньше, могут доминировать над $8\times 8$ шахматная доска.

Раскраски графов представляют собой способы раскрасить каждую клетку так, чтобы ферзь не мог перемещаться между двумя клетками одного цвета; как минимум n цветов для необходимо $n\times n$ шахматная доска, но для $8\times 8$ доска.

Характеристики

Для графа каждого ферзя существует гамильтонов цикл , и графы двусвязны (они остаются связными, если удалена любая единственная вершина). Особые случаи, $1\times n$ и $2\times 2$ графы ферзя полны . ^{[ 1 ]}

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

	а	б	с	д	и	ж	г	час
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	а	б	с	д	и	ж	г	час

Независимый набор размера 8 для

8\times 8

шахматная доска (такие наборы обязательно также являются доминирующими). ^{[ 2 ]}

Независимый набор графа соответствует такому расположению на шахматной доске нескольких ферзей, при котором никакие два ферзя не атакуют друг друга. В $n\times n$ На шахматной доске самый большой независимый набор содержит не более n вершин, поскольку никакие два ферзя не могут находиться в одной строке или столбце. ^{[ 2 ]} Эта верхняя граница может быть достигнута для всех n, кроме n =2 и n =3. ^{[ 3 ]} В случае n=8 это традиционная головоломка с восемью ферзями. ^{[ 2 ]}

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

Доминирующий набор графа ферзей соответствует такому расположению ферзей, при котором каждая клетка на шахматной доске либо атакована, либо занята ферзем. На $8\times 8$ на шахматной доске могут доминировать пять ферзей, и это минимально возможное число ^{[ 4 ]}^{: 113–114} (четыре ферзя оставляют не атакованными как минимум два поля). Таких расстановок пяти ферзей 4860, включая такие, где ферзи контролируют и все занятые поля, т.е. атакуют соответственно и защищают друг друга. В этой подгруппе также есть позиции, в которых ферзи занимают поля только на главной диагонали. ^{[ 4 ]}^{: 113–114} (например, от a1 до h8) или все на субдиагонали (например, от a2 до g8). ^{[ 5 ]}^{[ 6 ]}

	а	б	с	д	и	ж	г	час
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	а	б	с	д	и	ж	г	час

Доминирующий (и независимый) набор размера 5.

	а	б	с	д	и	ж	г	час
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	а	б	с	д	и	ж	г	час

Доминирующий набор на главной диагонали.

	а	б	с	д	и	ж	г	час
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	а	б	с	д	и	ж	г	час

Доминирующее множество на поддиагонали.

Изменение графика путем замены нециклического прямоугольника $8\times 8$ шахматная доска с тором или цилиндром уменьшает минимальный размер доминирующего набора до четырех. ^{[ 4 ]}^: 139

Пунктирные квадраты примыкают к центральному квадрату. 8 несмежных клеток являются соседними в соответствующем конском графе . ^{[ 4 ]}^: 117

The $3\times 3$ В графе ферзя доминирует единственная вершина в центре доски. Центральная вершина $5\times 5$ Граф ферзя смежн со всеми вершинами, кроме 8: теми вершинами, которые смежны с центральной вершиной графа ферзя. $5\times 5$ рыцарский граф . ^{[ 4 ]}^: 117

Числа доминирования

Определим число доминирования d ( n ) $n\times n$ граф ферзя равен размеру наименьшего доминирующего набора, а число диагонального доминирования dd ( n ) равно размеру наименьшего доминирующего набора, который является подмножеством длинной диагонали. Обратите внимание, что $d(n)\leq dd(n)$ для всех н . Граница достигается за $d(8)=dd(8)=5$ , но не для $d(11)=5,dd(11)=7$ . ^{[ 4 ]}^: 119

Число доминирования линейно по n с границами, заданными следующим образом: ^{[ 4 ]}^{: 119, 121}

{\frac {n-1}{2}}\leq d(n)\leq n-\left\lfloor {\frac {n}{3}}\right\rfloor .

Начальные значения d ( n ), для $n=1,2,3,\dots$ , равны 1, 1, 1, 2, 3, 3, 4, 5, 5, 5, 5 (последовательность A075458 в OEIS ).

Пусть K _n — максимальный размер подмножества $\{1,2,3,\dots ,n\}$ так, что все числа имеют одинаковую четность и никакие три числа не образуют арифметическую прогрессию (набор «без средней точки»). Число диагонального доминирования $n\times n$ граф ферзя это $n-K_{n}$ . ^{[ 4 ]}^: 116

независимого числа доминирования Определите идентификатор ( n ) как размер наименьшего независимого доминирующего набора в $n\times n$ граф королевы. Известно, что $ID(n)<0.705n+0.895$ . ^{[ 7 ]}

Раскраска

Раскраска . графа ферзя — это присвоение цвета каждой вершине таким образом, чтобы никакие две соседние вершины не были окрашены в один и тот же цвет Например, если a8 окрашено в красный цвет, то никакое другое поле на вертикали a , восьмой горизонтали или длинной диагонали не может быть окрашено в красный цвет, поскольку ферзь может переместиться с a8 на любое из этих полей. Хроматическое число графа — это наименьшее количество цветов, которыми можно его раскрасить.

В случае $n\times n$ Для графа ферзя как минимум n требуется цветов, так как каждому квадрату в ряду или ряду нужен свой цвет (т. е. строки и столбцы представляют собой клики ). ^{[ 1 ]} Хроматическое число равно n, если $n\equiv 1,5{\pmod {6}}$ (т.е. n на единицу больше или на единицу меньше, чем кратное 6). ^{[ 9 ]}

Хроматическое число $8\times 8$ граф ферзя равен 9. ^{[ 10 ]}

Неизбыточность

Набор вершин является неизбыточным, если удаление какой-либо вершины из набора изменяет окрестность набора, т.е. для каждой вершины существует смежная вершина, которая не является смежной ни с одной другой вершиной в наборе. Это соответствует набору ферзей, каждый из которых однозначно контролирует хотя бы одно поле. Максимальный размер IR ( n ) неизбыточного набора на $n\times n$ граф ферзя трудно охарактеризовать; известные значения включают в себя $IR(5)=5,IR(6)=7,IR(7)=9,IR(8)=11.$ ^{[ 4 ]}^{: 206–207}

Игра «Преследование-уклонение»

Рассмотрим игру преследования-уклонения на $8\times 8$ Граф ферзя разыгрывается по следующим правилам: белый ферзь начинается в одном углу, а черный ферзь - в противоположном. Игроки чередуют ходы, которые заключаются в перемещении ферзя в соседнюю вершину, до которой можно добраться, не проходя мимо (по горизонтали, вертикали или диагонали), или в приземлении на вершину, смежную с противоположным ферзем. В этой игре белые могут выиграть с помощью парной стратегии . ^{[ 11 ]}

См. также

Ссылки

^ Перейти обратно: ^а ^б Вайсштейн, Эрик В. «Королева Граф» . Математический мир .
^ Перейти обратно: ^а ^б ^с Авербах, Бонни ; Чейн, Орин (2000). Решение задач с помощью занимательной математики . Дуврские публикации . стр. 211–212. ISBN 9780486131740 .
^ Бернхардссон, Бо (1991). «Явное решение проблемы N-ферзей для всех N». АСМ Сигарт . 2 (2): 7. дои : 10.1145/122319.122322 . S2CID 10644706 .
^ Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час ^я Уоткинс, Джон Дж. (2012). Через доску: Математика шахматных задач . Издательство Принстонского университета .
^ Доминирующие королевы - на сайте Researchgate.net.
^ 5 ферзей на шахматной доске
^ Кокейн, Э.Дж. (1990). «Проблемы доминирования на шахматной доске» . Дискретная математика . 86 (1–3): 13–20. дои : 10.1016/0012-365X(90)90344-H . hdl : 1828/2415 .
^ Айер, MR; Менон, В.В. (1966). «О раскрашивании $n\times n$ Шахматная доска». The American Mathematical Monthly . 72 (7): 723.
^ Хватал, Вацлав . «Раскраска графов ферзя» . Проверено 14 февраля 2022 г.
^ Белл, Джордан; Стивенс, Бретт (2009). «Обзор известных результатов и областей исследований n -ферзей» . Дискретная математика . 309 (1): 1–31. дои : 10.1016/j.disc.2007.12.043 .
^ Авербах и Чейн 2000 , стр. 257–258, 443.

[MathWorld-1] Перейти обратно: ^а ^б Вайсштейн, Эрик В. «Королева Граф» . Математический мир .

[Averbach-2] Перейти обратно: ^а ^б ^с Авербах, Бонни ; Чейн, Орин (2000). Решение задач с помощью занимательной математики . Дуврские публикации . стр. 211–212. ISBN 9780486131740 .

[3] Бернхардссон, Бо (1991). «Явное решение проблемы N-ферзей для всех N». АСМ Сигарт . 2 (2): 7. дои : 10.1145/122319.122322 . S2CID 10644706 .

[Watkins-4] Перейти обратно: ^а ^б ^с ^д ^и ^ж ^г ^час ^я Уоткинс, Джон Дж. (2012). Через доску: Математика шахматных задач . Издательство Принстонского университета .

[5] Доминирующие королевы - на сайте Researchgate.net.

[6] 5 ферзей на шахматной доске

[7] Кокейн, Э.Дж. (1990). «Проблемы доминирования на шахматной доске» . Дискретная математика . 86 (1–3): 13–20. дои : 10.1016/0012-365X(90)90344-H . hdl : 1828/2415 .

[8] Айер, MR; Менон, В.В. (1966). «О раскрашивании $n\times n$ Шахматная доска». The American Mathematical Monthly . 72 (7): 723.

[9] Хватал, Вацлав . «Раскраска графов ферзя» . Проверено 14 февраля 2022 г.

[10] Белл, Джордан; Стивенс, Бретт (2009). «Обзор известных результатов и областей исследований n -ферзей» . Дискретная математика . 309 (1): 1–31. дои : 10.1016/j.disc.2007.12.043 .

[FOOTNOTEAverbachChein2000257–258,_443-11] Авербах и Чейн 2000 , стр. 257–258, 443.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]