График Бишопа

Математический график, относящийся к шахматам

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

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

Тот факт, что шахматная доска имеет квадраты двух цветов, скажем, красного и черного, так что квадраты, которые являются соседними по горизонтали или вертикали, имеют противоположные цвета, подразумевает, что граф слона имеет две связные компоненты, вершинными множествами которых являются красные и черные квадраты соответственно. Причина в том, что диагональные ходы слона не позволяют ему менять цвета, но одним или несколькими ходами слон может попасть с любого квадрата на любой другой того же цвета. ^[1] Два компонента изоморфны, если доска имеет сторону четной длины, но не если обе стороны нечетные.

Компонент графа слона можно рассматривать как граф ладьи на ромбе, если исходная доска квадратная и имеет стороны нечетной длины, потому что если красные квадраты (скажем) повернуть на 45 градусов, ходы слона станут горизонтальными и вертикальными, как и у ладьи . [ ^2]

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

Говорят, что поле атаковано слоном, если слон может добраться до этого поля ровно за один ход. Доминирующий набор — это расположение слонов таким образом, что каждое поле атаковано или занято одним из этих слонов. Независимый доминирующий набор — это доминирующий набор, в котором ни один слон не атакует другой. Минимальное количество слонов, необходимое для доминирования над квадратной доской со стороной n , равно n , и это также наименьшее количество слонов, которые могут образовать независимый доминирующий набор. Напротив, полный доминирующий набор, который является доминирующим набором, для которого каждый квадрат, включая занятые слонами, атакован одним из слонов, требует большего количества слонов; на квадратной доске со стороной n ≥ 3 минимальный размер полного доминирующего набора примерно на 1/3 больше минимального доминирующего набора. ^{[3] [4]} ${\displaystyle 2\lceil 2(n-1)/3\rceil ,}$

Ссылки

1. Бергхаммер, Рудольф (2012). «Реляционно-алгебраическое моделирование и решение проблем независимости и доминирования на шахматной доске». Журнал логического и алгебраического программирования . 81 (6): 625–642. doi : 10.1016/J.JLAP.2012.05.001 .
2. Хедетниеми, Джейсон Т.; Хедетниеми, Стивен Т. (сентябрь 2020 г.). «Доминирование на шахматных досках». В Haynes, Тереза ​​В.; Хедетниеми, Стивен Т.; Хеннинг, Майкл А. (ред.). Структуры доминирования в графах . Развитие математики. Том 66. Springer International Publishing. стр. 341–386. doi :10.1007/978-3-030-58892-2_12. ISBN 9783030588922.
3. Кокейн, Э. Дж.; Гэмбл, Б.; Шеперд, Б. (1986). «Параметры доминирования для графа епископов». Дискретная математика . 58 : 221–227. doi : 10.1016/0012-365X(86)90139-1 .
4. Кокейн, Э. Дж. (1990). «Проблемы доминирования на шахматной доске». Дискретная математика . 86 : 13–20. doi :10.1016/0012-365X(90)90344-H. hdl : 1828/2415 .