Жемчужина Эйлера - Дэвид С. Ричесон
Для обсуждения решения нам понадобится несколько определений. Как и в случае многогранников, будем называть степенью вершины количество исходящих из нее ребер. Если в вершине есть петля (ребро, начинающееся и заканчивающееся в ней, как в правом графе на рис. 11.1), то она увеличивает степень на 2. В графе, образованном кёнигсбергскими мостами, имеется три вершины степени 3 и одна вершина степени 5. Граф называется связным, если из любой вершины можно дойти до любой другой, следуя по ребрам.
Вычерчивание графа, начинающееся в одной вершине и заканчивающееся в другой, называется обходом. Нас интересует весьма специальный класс обходов — такие, при которых каждое ребро посещается ровно один раз; они называются эйлеровыми обходами. Если эйлеров обход начинается и заканчивается в одной и той же вершине, то она называется эйлеровым циклом. В общем случае циклом называется обход графа, который начинается и заканчивается в одной и той же вершине и не проходит по одному ребру дважды. Произвольный (не эйлеров) цикл может не проходить по каждому ребру.
На языке теории графов мы можем переформулировать задачу о кёнигсбергских мостах следующим образом:
Существует ли для графа кёнигсбергских мостов (рис. 11.3) эйлеров обход? Вообще, как узнать, существует для произвольного графа эйлеров обход?
Эйлер решил обе эти задачи. В переводе на современный язык решение описывается следующим образом.
Для графа существует эйлеров обход тогда и только тогда, когда граф связный и в нем имеется ноль или две вершины нечетной степени. Если имеется две вершины нечетной степени, то обход должен начинаться в одной из них, иначе он может начинаться в любой вершине.
С помощью этого критерия задача о кёнигсбергских мостах легко решается. Поскольку в графе четыре вершины нечетной степени, то эйлерова обхода не существует! Неудивительно разочарование жителей Кёнигсберга, которые никак не могли отыскать маршрута для идеальной вечерней прогулки.
Но почему решение Эйлера правильно? Требование связности графа очевидно. А вот требование о существовании нуля или двух вершин нечетной степени нуждается в осмыслении. Для доказательства теоремы нужно сделать две вещи. Во-первых, мы должны показать, что в любом графе, допускающем эйлеров обход, существует ноль или две вершины нечетной степени. Во-вторых, мы должны доказать обратное: если в связном графе имеется ноль или две вершины нечетной степени, то он допускает эйлеров обход.
Предположим, что имеется граф, допускающий эйлеров обход; мы покажем, что в нем имеется ноль или две вершины нечетной степени. Положим лист кальки поверх графа и начнем вычерчивать эйлеров обход. В начале вычерчивания первая вершина будет иметь степень 1, а остальные — степень 0. После того как мы дойдем до второй вершины и оставим ее позади, она будет иметь степень 2. Начиная с этого момента, каждый проход через вершину увеличивает ее степень на два. Это продолжается, пока мы не дойдем до конца обхода. В этот момент мы увеличиваем степень последней вершины на единицу. Если обход начинается и заканчивается в разных вершинах, то обе они будут иметь нечетную степень, и это будут единственные вершины нечетной степени. Если же обход начинается и заканчивается в одной и той же вершине, то она, как и все остальные вершины, будет иметь четную степень.
Обратное утверждение Эйлер принял как само собой разумеющееся: если в графе имеется ноль или две вершины нечетной степени, то он допускает эйлеров обход. Первое доказательство этого факта было дано Карлом Хирхольцером (1840–1871) и опубликовано после его смерти, в 1873 году90.
Начнем со связного графа, имеющего ноль или две вершины нечетной степени. если таких вершин две, то поместим карандаш в одну из них, в противном случае — в произвольную вершину. Начнем вычерчивание в любом направлении. Дойдя до первой вершины, выберем случайным образом следующее ребро. Будем продолжать таким образом — делать случайный выбор в каждой вершине (конечно, избегая уже посещенных ребер), пока дальнейшее движение не станет невозможным. В силу приведенного выше рассуждения, если мы начинали с вершины нечетной степени, то закончим вычерчивание в другой вершине нечетной степени, иначе вычерчивание завершится в той вершине, с которой начинали. На рис. 11.4 путь abcdefghi определяет такой обход.
Если этот путь не проходит по всем ребрам графа, то удалим все посещенные ребра и посмотрим на оставшийся граф (возможно, он уже не связный). Поместим карандаш в какую-нибудь вершину, которая посещалась при первоначальном вычерчивании. Как и раньше, будем вычерчивать граф, пока не окажется, что дальше двигаться невозможно. В нашем примере получится обход jkl. Теперь вставим новую трассу вычерчивания в нужное место построенного ранее обхода. В нашем примере путь jkl вставляется между ребрами b и c первоначального обхода. Таким образом, мы получили путь abjklcdefghi, являющийся эйлеровым обходом. В общем случае, возможно, придется проделать такую вставку несколько раз, пока не будут вычерчены все ребра.
Рис. 11.4. Построение эйлерова обхода
Заметим, что мы узнали о вычерчивании графов больше, чем видно из этого решения на первый взгляд. Мы ставили целью найти эйлеровы обходы, но заодно определили, когда обход может начинаться и заканчиваться в одной и той же вершине. Точнее:
Граф допускает эйлеров цикл тогда и только тогда, когда он связный и не содержит вершин нечетной степени. В этом случае эйлеров цикл может начинаться и заканчиваться в любой вершине.
В 1875 году, спустя полтора века после того, как Эйлер проанализировал маршруты прогулок по Кёнигсбергу, в городе был построен новый мост91. Он был возведен к западу от острова Кнайпхоф и соединил северный берег реки с южным (рис. 11.5). Наконец-то жители Кёнигсберга смогли совершить прогулку по всем мостам, пройдя по каждому ровно один раз, поскольку теперь оказалось ровно две вершины нечетной степени — соответствующие острову и суше между рукавами реки. Конечно, некоторые горожане не могли начать прогулку от порога своего дома, и никому не удалось бы закончить прогулку в том же месте, где она началась.
Рис. 11.5. Новый мост в Кёнигсберге и новый граф
Решение задачи о кёнигсбергских мостах иллюстрирует общее для математики явление. Начиная изучать проблему, мы сталкиваемся с уймой лишней информации. Хороший метод решения позволяет устранить все несущественное и сконцентрироваться на сути. В
