данном случае такие детали, как точное положение мостов и участков суши, ширина реки и форма острова, оказались не важны. Эйлер упростил задачу, так что ее стало возможно сформулировать в терминах теории графов. Это и есть признак гения.
В заключение приведем три примера. В 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. Граф, соответствующий комплекту костяшек домино
Начнем с первого ребра в эйлеровом обходе. Пусть оно соединяет вершины 0 и 3. Выложим костяшку, содержащую 0 и 3 точки (0:3). Теперь рассмотрим второе ребро в обходе. Допустим, что оно соединяет вершины 3 и 1. Выложим костяшку 3:1, приложим ее к предыдущей (рис. 11.11). Будем продолжать таким же образом, выкладывая костяшки на каждом шаге. Поскольку мы совершаем эйлеров обход, каждое ребро будет посещено ровно один раз. Поэтому мы сможем выложить все до одной костяшки.
Рис. 11.11. Часть партии в домино и соответствующая ей часть обхода графа
Как показывают эти примеры, теория графов имеет интересные применения в развлекательной математике. Однако это также весьма важная часть серьезной математики, имеющая многочисленные практические применения в таких разных областях, как информатика, вычислительные сети, социальные структуры, транспортные системы и моделирование эпидемий. Мы еще встретимся с теорией графов в последующих главах. В частности, мы выведем аналог формулы Эйлера для одного класса графов.
Приложения к главе
84. Thoreau (1894), 419.
85. Quoted in Sachs, Stiebitz, and Wilson (1988).
86. Там же.
87. Quoted in Hopkins andWilson (2004).
88. Euler (1736), английский перевод в Biggs, Lloyd, and Wilson (1986), 3–8.
89. Ball (1892).
90. Hierholzer (1873).
91. Barabasi (2002), 12.
92. Listing (1847).
93. Terquem (1849).
Глава 12
Плоскостные многогранники Коши
Коши — безумец, и с этим ничего не поделаешь, но сейчас он единственный, кто знает, как надо делать математику.
— Нильс Абель94
За сто лет, прошедших с того момента, когда Эйлер доказал формулу для многогранников, появилось много новых доказательств и целый ряд обобщений на экзотические многогранные тела. Первое значительное обобщение сделал Огюстен Луи Коши, который также придумал остроумное новое доказательство.
Рис. 12.1. Огюстен-Луи Коши
Коши родился в Париже в 1789 году. Он был старшим сыном высокопоставленного чиновника. Хотя в эпоху террора семья покинула Париж, отец позаботился о том, чтобы сын получил хорошее образование. В юности он познакомился с математиками Пьером-Симоном Лапласом (1749–1827) и Жозефом-Луи Лагранжем, а также с химиком Клодом Луи Бертолле (1748–1822), так что уже на заре своей жизни общался с авторитетными учеными.
Коши недолго работал военным инженером на строительстве Уркского канала, моста Сен-Клод и Шербургской базы флота. Первые математические сочинения он опубликовал в 1811 году, за два года до возвращения в Париж, где начал строить карьеру в математике. В 1815 году он был принят на работу в Политехническую школу.
Коши был потрясающе плодовитым ученым. По количеству написанных работ он уступает только Эйлеру; собрание его сочинений,
