Жемчужина Эйлера

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

В заключение приведем три примера. В 1847 году Иоганн Бенедикт Листинг (1808–1882), математик, с которым мы еще встретимся снова, придумал граф, изображенный на рис. 11.6, чтобы проиллюстрировать проблему вычерчивания (мы рисуем граф так, как это сделал Листинг, опуская вершины в точках пересечения)⁹². Допускает ли этот граф эйлеров обход? А эйлеров цикл? Предлагаем читателю подумать над этой задачей, прежде чем продолжить чтение.

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

Рис. 11.6. Головоломка Листинга на вычерчивание графа

Второй пример — вариация на тему задачи о мостах. Рассмотрим рисунок, напоминающий кирпичную стену (рис. 11.7). Можно ли провести непрерывную кривую, пересекающую каждый отрезок ровно один раз (кривая может начинаться и заканчиваться в разных кирпичах)? Попытка, показанная на правом рисунке, — не решение, потому что кривая не пересекает один отрезок.

Рис. 11.7. Неправильное решение головоломки

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

И наконец, применим теорию графов и эйлеровых обходов к игре в домино. Этот пример придумал Орли Теркем (1782–1862) в 1849 году⁹³. В стандартном комплекте домино на каждой половине костяшки нанесено от одной до шести точек. В комплекте нет двух одинаковых костяшек и все комбинации присутствуют. Всего, таким образом, получается 28 костяшек. Каждый игрок по очереди выкладывает костяшки, так чтобы число точек на одной половине его костяшки совпадало с числом точек на свободном конце уже выложенной костяшки. Костяшки с одинаковым числом точек на обеих половинах (дубли) можно класть перпендикулярно костяшке с соответствующим числом точек (как на рис. 11.9). Игра заканчивается, когда игрок не может выложить очередную костяшку. Спрашивается, всегда ли игра заканчивается, когда у какого-то игрока на руках есть костяшки? Или можно выложить все костяшки, так что у игроков ни одной не останется?

Рис. 11.8. Граф, ассоциированный с головоломкой о кирпичной стене

Рис. 11.9. Типичная партия в домино

Для анализа этой задачи построим граф следующим образом. Начнем с семи вершин, пронумерованных от 0 до 6. Каждой костяшке соответствует ребро графа. Костяшке с m точками на одной половине и n точками на другой соответствует ребро из вершины m в вершину n. Сопоставив ребра всем костяшкам, мы получим граф, показанный на рис. 11.10. Заметим, что в каждой вершине имеется петля, соответствующая костяшкам-дублям.

Все вершины в графе домино имеют степень 8. Поскольку степени всех вершин четные, граф допускает эйлеров обход. Следовательно, весь граф можно вычертить, не проходя по одному ребру дважды. Это наблюдение и есть ключ к ответу на поставленный вопрос. Чтобы показать, что можно сыграть все костяшки домино, достаточно предъявить соответствующую партию. Мы построим ее просто (хотя вряд ли такая конфигурация возникнет в реальной партии) — выстроив костяшки в линию.

Рис. 11.10. Граф, соответствующий комплекту костяшек домино

Начнем с первого ребра в эйлеровом обходе. Пусть оно соединяет вершины 0 и 3. Выложим костяшку, содержащую 0 и 3 точки (0:3). Теперь рассмотрим второе ребро в обходе. Допустим, что оно соединяет вершины 3 и 1. Выложим костяшку 3:1, приложим ее к предыдущей (рис. 11.11). Будем продолжать таким же образом, выкладывая костяшки на каждом шаге. Поскольку мы совершаем эйлеров обход, каждое ребро будет посещено ровно один раз. Поэтому мы сможем выложить все до одной костяшки.

Рис. 11.11. Часть партии в домино и соответствующая ей часть обхода графа