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

Граф королевы
а б с г е ф г час 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1 а б с г е ф г час В графе ферзя каждая клетка шахматной доски выше является вершиной . Между любыми двумя вершинами есть ребро, между которыми может ходить ферзь; например, вершины, смежные с d4, отмечены белой точкой (т. е. есть ребро от d4 до каждой отмеченной вершины).${\displaystyle 8\times 8}$
Вершины	${\displaystyle mn}$
Хроматическое число	н если${\displaystyle m=n\equiv 1,5{\pmod {6}}}$
Характеристики	Двусвязный , гамильтонов
Таблица графиков и параметров

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

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

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

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

	а	б	с	г	е	ф	г	час
8									8
7									7
6									6
5									5
4									4
3									3
2									2
1									1
	а	б	с	г	е	ф	г	час

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

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

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

а б с г е ф г час 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 а б с г е ф г час Доминирующий набор на поддиагонали.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Граф короля
• Граф рыцаря
• Граф Рукса
• График Бишопа
• Шахматный портал