Карты метро и нейронные сети. Теория графов
Шрифт:
Немецкий математик Давид Гильберт.
Существует множество игр, в которых нужно построить определенный граф или же с помощью графа определить, существует ли выигрышная стратегия. В качестве примера и в завершение нашей книги мы расскажем о некоторых таких играх.
Кто назовет 20?
Первый игрок называет одно из двух
Лабиринт в саду Роуз Болла
Благодаря занимательным задачам У. У. Роуз Болла, популярность получили многие разделы математики. В знаменитом лабиринте Болла стрелками отмечены вход и выход, а точкой — место, где лежат сокровища. Можно ли добраться до них? Попробуйте не подсматривать ответ, а найти решение сами. Получилось? Найденный маршрут будет состоять из линий и точек, обозначающих повороты. Каждое ребро полученного графа нужно пройти дважды (туда и обратно), поэтому все вершины маршрута должны иметь степень 2. Чтобы найти требуемый маршрут, достаточно отмечать коридоры, которые мы уже прошли, чтобы не терять времени понапрасну.
Лабиринт Роуз Болла.
Игра «змейка»
В этой игре, которую придумал Дэвид Сильверман, два игрока по очереди проводят единичные отрезки на сетке размерами 5x5 или 6x6 точек (размер игрового поля может быть произвольным). Отрезки можно добавлять только в начало и конец «змейки». Проигрывает тот, кто вынужден построить цикл. Существует ли выигрышная стратегия для этой игры?
Изящная нумерация графа
В этой игре Соломона Голомба нужно построить граф и подписать его вершины различными целыми положительными числами (или нулем). Вершины нужно пронумеровать так, чтобы разности чисел, присвоенных соседним вершинам, не совпадали, и при этом наибольший номер вершины был как можно меньшим числом.
Ханойские башни
В этой игре, придуманной Эдуардом Люка в 1883 году (и окруженной мнимыми легендами), на три стержня нанизаны п колец разного размера, упорядоченные от меньшего к большему. Большее кольцо не может располагаться поверх меньшего. Нужно переместить кольца так, чтобы восстановить исходную пирамиду на третьем стержне. На каждом ходу можно перемещать только одно кольцо.
Начальное положение колец в игре «Ханойские башни».
Число решений для n колец равно 2n — 1. С увеличением n число решений стремительно возрастает. Чтобы определить правильную последовательность ходов, можно использовать графы. Интерактивные версии этой игры есть в интернете.
Игра Ним
Два
Две цепи Мартина Гарднера
Мартин Гарднер, который обожал задачи с плоскими графами, предложил множество подобных задач своим читателям со всего мира. Стремясь показать, как плоские графы используются в электрических цепях, Гарднер придумал задачи, в которых точки (вершины) графа нужно соединить линиями так, чтобы получился плоский граф, то есть избежать пересечений (если две линии пересекаются в точке, которая не является вершиной графа, возникает короткое замыкание). Мы предлагаем читателю решить следующие задачи (ответы приводятся в конце главы на стр. 122).
Цепь в прямоугольнике
В этом прямоугольнике нужно провести пять линий, соединяющих А и A, В и В, С и С, D и D, E и E, не пересекая отрезки AD и ВС, отмеченные на рисунке, и не выходя за границы прямоугольника.
Цепь на квадратной сетке
На этой сетке размерами 7 x 7 клеток нужно провести вдоль линий сетки пять непересекающихся линий так, чтобы соединить точки, обозначенные одинаковыми буквами.
Советуем читателю вооружиться терпением и как следует поразмыслить над тем, как найти единственное решение этой задачи. Не торопитесь заглядывать в ответы в конце главы.
* * *
МАРТИН ГАРДНЕР (1914–2010)
Среди звездных авторов научно-популярной литературы особенно ярко блистает звезда Мартина Гарднера. Он родился в городе Талса, штат Оклахома, США, изучал философию, но после окончания университета занялся журналистикой. Много лет, с 1956 по 1986 год, он был автором ежемесячной рубрики «Математические игры» в журнале Scientific American. В этой рубрике и в своих многочисленных книгах он рассказывал о математике, играх, алгоритмах, парадоксах и головоломках.
Кроме этого, он писал о философии, научных исследованиях в различных областях, а также был автором комментариев ко многим книгам. Любопытно, что Гарднер не выступал на конференциях и не преподавал, уделяя все время написанию книг и статей.
Обложка одной из многочисленных книг Мартина Гарднера.
* * *
Маршрут коня на шахматной доске
Шахматная доска используется во множестве математических задач. Классическими являются задачи о перемещении различных фигур (пешки, слона, ладьи, ферзя) по шахматной доске. Особый интерес представляет следующий вопрос: может ли шахматный конь пройти по всем 64 клеткам доски ровно один раз и вернуться в исходную клетку?