6.13. Игры на шахматной доске

Пусть задано множество клеток шахматной доски (рис. 6.28) и известно, что из клетки с четным номером можно сделать ход на соседнюю клетку по горизонтали и вертикали, а из клетки с нечетным номером можно сделать ход на соседнюю клетку по диагонали. Сопоставляя с каждой клеткой вершину графа, можно получить матрицу смежности вершин V для соответствующего графа.

(см. скан)

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

Вероятно, читатель сталкивался с различными головоломками, в которых конечная цель состоит в точном покрытии заданной плоской «доски» множеством плоских «фигур», общая площадь которых равна площади доски. В случае, когда каждая фигура имеет только конечное множество допустимых положений на доске, задача покрытия может быть сформулирована (по крайней мере, в принципе) и решена в терминах теории графов. Рассмотрим один из походов к решению таких задач — подход, основанный на работе Жульена [52а].

Рис. 6.28,

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

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

Обозначим число фигур через и пусть число допустимых положений фигуры. Рассмотрим граф имеющий вершин, соответствующих всем возможным положениям фигур. Будем считать, что в графе вершины являются смежными тогда и только тогда, когда соответствующие положения оказываются совместными в названном смысле. Легко видеть, что каждое решение исходной головоломки соответствует

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

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

На первом шаге удаляются все вершины, соответствующие фигурам (в качестве могут выбираться любые фигуры). Они заменяются вершинами типа при условии, что рассматриваемые комбинации А и В) являются совместимыми. Кроме того, соединяется со всеми положениями фигур которые оказываются совместимыми как с так и с Легко видеть, что существует взаимнооднозначное соответствие между полными подграфами с вершинами в исходном графе и полными подграфами с вершинами в новом графе.

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