Рис. 11.5. Новый мост в Кёнигсберге и новый граф
Решение задачи о кёнигсбергских мостах иллюстрирует общее для математики явление. Начиная изучать проблему, мы сталкиваемся с уймой лишней информации. Хороший метод решения позволяет устранить все несущественное и сконцентрироваться на сути. В данном случае такие детали, как точное положение мостов и участков суши, ширина реки и форма острова, оказались не важны. Эйлер упростил задачу, так что ее стало возможно сформулировать в терминах теории графов. Это и есть признак гения.
В заключение приведем три примера. В 1847 году Иоганн Бенедикт Листинг (1808–1882), математик, с которым мы еще встретимся снова, придумал граф, изображенный на рис. 11.6, чтобы проиллюстрировать проблему вычерчивания (мы рисуем граф так, как это сделал Листинг, опуская вершины в точках пересечения)92. Допускает ли этот граф эйлеров обход? А эйлеров цикл? Предлагаем читателю подумать над этой задачей, прежде чем продолжить чтение.
Мы видим, что все вершины имеют четную степень, кроме самой левой и самой правой, степень которых равна 5. Поскольку существует ровно две вершины нечетной степени, граф Листинга опускает эйлеров обход, и каждый такой обход должен начинаться в одной из этих вершин и заканчиваться в другой. Поскольку в графе есть вершины нечетной степени, то эйлерова цикла не существует.
Рис. 11.6. Головоломка Листинга на вычерчивание графа
Второй пример — вариация на тему задачи о мостах. Рассмотрим рисунок, напоминающий кирпичную стену (рис. 11.7). Можно ли провести непрерывную кривую, пересекающую каждый отрезок ровно один раз (кривая может начинаться и заканчиваться в разных кирпичах)? Попытка, показанная на правом рисунке, — не решение, потому что кривая не пересекает один отрезок.
Рис. 11.7. Неправильное решение головоломки
Это невозможно. Обосновать это утверждение можно, преобразовав задачу в задачу о вычерчивании графа. Поместим по одной вершине внутри каждого кирпича и еще одну вне стенки. Проведем между вершинами ребра, соответствующие отрезкам, разделяющим кирпичи (см. рис. 11.8). Достаточно выяснить, допускает ли этот граф эйлеров обход. Поскольку в графе четыре вершины степени 5, эйлеров обход невозможен. Поэтому не существует кривой, обладающей желаемыми свойствами.
И наконец, применим теорию графов и эйлеровых обходов к игре в домино. Этот пример придумал Орли Теркем (1782–1862) в 1849 году93. В стандартном комплекте домино на каждой половине костяшки нанесено от одной до шести точек. В комплекте нет двух одинаковых костяшек и все комбинации присутствуют. Всего, таким образом, получается 28 костяшек. Каждый игрок по очереди выкладывает костяшки, так чтобы число точек на одной половине его костяшки совпадало с числом точек на свободном конце уже выложенной костяшки. Костяшки с одинаковым числом точек на обеих половинах (дубли) можно класть перпендикулярно костяшке с соответствующим числом точек (как на рис. 11.9). Игра заканчивается, когда игрок не может выложить очередную костяшку. Спрашивается, всегда ли игра заканчивается, когда у какого-то игрока на руках есть костяшки? Или можно выложить все костяшки, так что у игроков ни одной не останется?
Рис. 11.8. Граф, ассоциированный с головоломкой о кирпичной стене
Рис. 11.9. Типичная партия в домино
Для анализа этой задачи построим граф следующим образом. Начнем с семи вершин, пронумерованных от 0 до 6. Каждой костяшке соответствует ребро графа. Костяшке с m точками на одной половине и n точками на другой соответствует ребро из вершины m в вершину n. Сопоставив ребра всем костяшкам, мы получим граф, показанный на рис. 11.10. Заметим, что в каждой вершине имеется петля, соответствующая костяшкам-дублям.
Все вершины в графе домино имеют степень 8. Поскольку степени всех вершин четные, граф допускает эйлеров обход. Следовательно, весь граф можно вычертить, не проходя по одному ребру дважды. Это наблюдение и есть ключ к ответу на поставленный вопрос. Чтобы показать, что можно сыграть все костяшки домино, достаточно предъявить соответствующую партию. Мы построим ее просто (хотя вряд ли такая конфигурация возникнет в реальной партии) — выстроив костяшки в линию.
Рис. 11.10. Граф, соответствующий комплекту костяшек домино