Клауди Альсина - Том 11. Карты метро и нейронные сети. Теория графов

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

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

* * *

МАРТИН ГАРДНЕР (1914–2010)

Среди звездных авторов научно-популярной литературы особенно ярко блистает звезда Мартина Гарднера. Он родился в городе Талса, штат Оклахома, США, изучал философию, но после окончания университета занялся журналистикой. Много лет, с 1956 по 1986 год, он был автором ежемесячной рубрики «Математические игры» в журнале Scientific American. В этой рубрике и в своих многочисленных книгах он рассказывал о математике, играх, алгоритмах, парадоксах и головоломках.

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

Обложка одной из многочисленных книг Мартина Гарднера.

* * *

Маршрут коня на шахматной доске

Шахматная доска используется во множестве математических задач. Классическими являются задачи о перемещении различных фигур (пешки, слона, ладьи, ферзя) по шахматной доске. Особый интерес представляет следующий вопрос: может ли шахматный конь пройти по всем 64 клеткам доски ровно один раз и вернуться в исходную клетку?

Эта задача имеет решение; более того, оно не является единственным. Эту головоломку, как и многие другие шахматные задачи, можно решить с помощью теории графов. Каждая клетка доски соответствует вершине графа, ход коня — ребру, соединяющему две вершины графа. Следовательно, задача сводится к нахождению гамильтонова цикла в этом графе.

Маршрут коня по шахматной доске.

Математики не стали ограничиваться стандартной доской размером 8 x 8 клеток и рассмотрели возможность обхода досок размерами 5 x 5, 6 x 6, 3 x 10 клеток и других. Эти задачи представляют собой задачи на поиск гамильтоновых цепей в графах, число вершин которых равняется n x m . Например, для доски 6 x 6 клеток задача имеет решение, для досок 5 x 5 или 2 x 8 — нет.

Интересной читателю будет и задача о поиске маршрута шахматной ладьи из одного угла доски в диагонально противоположный, проходящего через все клетки. Можно рассмотреть доску размерами 7 x 7 клеток или общий случай — n x n клеток.

Простая игра в шахматы может подарить вам огромное множество интересных задач.

Льюис Кэрролл и эйлеровы графы

Чарльз Лютвидж Доджсон(1832–1898), известный под псевдонимом Льюис Кэрролл, был не только автором «Алисы в стране чудес», но и любителем занимательных математических задач. Он любил придумывать остроумные головоломки, которые мог решить даже ребенок. Некоторые из его задач сегодня изучаются в теории графов, хотя в его эпоху к теории графов относили лишь задачи, где нужно было нарисовать заданную фигуру, не отрывая карандаша от бумаги. Самой известной из подобных задач Кэрролла является задача о трех квадратах, показанных на рисунке. Сможете ли вы обойти этот граф, не отрывая карандаша от бумаги и не проводя ни одну линию дважды?

Томас О’Бейрн придумал удивительный метод решения подобных задач, который заключается в том, что нужно раскрасить смежные области чередующимися цветами (см. рисунок) и тем самым «разделить» области, чтобы найти искомый путь. Маршрут обхода становится очевидным, и можно легко провести карандашом нужный путь на исходном графе.

Задача о четырех окружностях

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

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