Глава 17. Свойства и типы графов. положило появление в печати работы Эйлера, посвященной решению этой проблемы, известная как задача о Кенигсбергских мостах (см

положило появление в печати работы Эйлера, посвященной решению этой проблемы, известная как задача о Кенигсбергских мостах (см. рис. 17.21). В немецком городе Кениг­сберг (с 1946 года — Калининград, входящий в состав России) семь мостов соединяли бе­рега реки и острова, и жители этого города обнаружили, что они, по-видимому, не мо­гут перейти все семь мостов, не пройдя по одному из них дважды. От этой задачи берет начало проблема поиска эйлерова цикла.

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

Эйлер нашел легкий способ определить, существует ли такая цепь, для этого доста­точно определить степень каждой вершины. Это свойство нетрудно сформулировать и применять, однако его доказательство в теории графов требует немалой изобретательности.

Свойство 17.4. Граф содержит эйлеров цикл тогда и только тогда, когда он связный и все его вершины имеют четную степень.

Доказательство: Чтобы упростить доказательство, допустим существование петель и парал­лельных ребер, хотя совсем нетрудно изменить доказательство таким образом, чтобы по­казать, что это свойство справедливо и для простых графов (см. упражнение 17.94).

Если в графе имеется эйлеров цикл, то он должен быть связным в силу того, что цикл определяет путь, соединяет каждую пару вершин. Кроме того, степень любой задан­ной вершины графа v должна быть четной, поскольку, когда мы проходим цикл (на­чало которого находится в какой-то другой вершине), то мы входим в вершину v че­рез одно ребро и выходим из нее через другое ребро (ни то, ни другое больше в цикл не входят); следовательно, число ребер, инцидентных вершине v, должно быть равно удвоенному числу наших посещений вершины v при прохождении эйлерова цикла, т.е. должно быть равно четному числу.

Чтобы доказать достаточность, воспользуемся методом индукции по количеству ребер. Это утверждение заведомо выполняется для графов, у которых нет ребер. Рассмотрим любой связный граф, в котором содержится более одного ребра, при этом степени всех вершин четные. Предположим, что начиная с произвольной вершины, мы про­двигаемся по любому ребру, после чего его удаляем. Мы продолжаем этот процесс до тех пор, пока не окажемся в вершине, у которой нет ребер. Этот процесс должен ког­да-нибудь завершиться, поскольку мы удаляем по одному ребру на каждом шаге, од­нако каким может стать результат этой процедуры? На рис. 17.22 приводятся приме­ры. Нам сразу становится ясно, что этот процесс должен закончиться на вершине v тогда и только тогда, когда ее степенью было число нечетное в момент, когда этот процесс начинался.

Одна из возможностей состоит в том, что мы пройдем по всему циклу; если это так, то доказательство завершено. В противном случае, все вершины графа, который при этом остался, имеют четные степени, но тогда граф может оказаться несвязным. Од­нако в соответствии с индуктивным предположением, каждая его связная компонен-

Часть 5. Алгоритмы на графах

пени (на концах пути). ■

Отсюда следует, например, что никто не может прой­ти через все мосты Кенигсберга так, чтобы не пройти по одному мосту дважды, поскольку в соответствующем гра­фе все четыре составляющие его вершины обладают нечет­ными степенями (см. рис. 17.21).

В соответствии с изложенным в разделе 17.5, мы мо­жем найти все степени вершин за время, пропорциональ­ное E для представления графа в виде списков смежных вершин или в виде множества ребер, либо за время, про­порциональное V² для представления графа в виде матри­цы смежности, либо мы можем поддерживать вектор, ин­дексированный именами вершин, в котором степени вершин являются частью представления графа (см. упраж­нение 17.42). При наличии такого вектора мы можем про­верить, выполняется ли свойство 17.4 за время, пропорци­ональное V. Программа 17.18 реализует эту стратегию и показывает, что проверка заданного графа на наличие в нем эйлеровою цикла представляет собой достаточно про­стую вычислительную задачу. Этот факт важен в силу того, что до сих пор мы не были уверены в том, что эта задача проще, чем определение гамильтонова пути в заданном графе.

Теперь предположим, что мы и в самом деле хотим найти эйлеров цикл. Мы идем по тонкому льду, посколь­ку прямая рекурсивная реализация (поиск пути за счет проверки ребра, после которой выполняется рекурсивный вызов с целью определения пути в остальной части графа) обеспечивает ту же производительность, пропорциональ­ную факториалу числа вершин, что и программа 17.17. Мы не можем смириться с такой производительностью, по-

РИСУНОК 17.21. МОСТЫ КЕНИГСБЕРГА

Широко известная задача, изучавшаяся еще Эйлером, связана с городом Кенигсберг, в котором в устье реки Лреголь расположены острова, соеди­ненные с берегами семью мостами. Существует ли путь, который позволяет во время непрерывной прогулки по городу, обойти все семь мостов и ни на одном из них не побывать дважды? Если мы обозначим остров через 0, берега реки через 1 и 2 еще один остров через 3, а также определим ребра, соответствующие каждому мосту, мы получим мультиграф, показанный в нижней части рисунка. Суть задачи заключа­ется в том, чтобы найти такой путь, который использу­ет каждое ребро в точности один раз.

Глава 17. Свойства и типы графов

скольку довольно легко проверить существование такого пути, поэтому мы намерены отыскать более приемлемый алгоритм. Есть возможность избежать зависимости от факториала числа вершин в условиях фиксированной стоимости проверки, можно ли ис­пользовать то или иное ребро (в отличие от неизвестной стоимо­сти в условиях рекурсивных вызовов), однако мы оставляем этот подход на самостоятельную проработку (см. упражнения 17.96 и 17.97).

Другой подход вытекает из доказательства свойства 17.4. Про­следуем по циклическому пути, стирая все ребра и помещая в стек все вершины, которые нам встретятся, так что (i) мы можем проследить свой путь, распечатав его ребра, и (ii) проверить каж­дую вершину на наличие боковых путей (который может быть включен в главный путь). Этот процесс иллюстрируется рисунком 17.23.

Сначала программа добавляет в искомый цикл ребро 0-1 и удаляет его из списков смежных вершин (из двух мест) (диаграм­ма в верхнем левом углу, списки слева от диаграммы). Затем она добавляет ребро 1-2 в искомый цикл тем же способом (диаграм­ма слева, вторая сверху). Далее, она поворачивает назад в 0, но при этом продолжает строить цикл 0-5-4-6-0, возвращаясь в вершину 0, при этом ребер, инцидентных вершине 0, не оста­ется (справа, вторая диаграмм сверху). Затем она выталкивает из стека изолированные вершины 0 и 6, так что вверху стека остается вершина 4, и начинает цикл с вершины 4 (справа, третья диаграмма сверху), проходит через вершины 3, 2 и воз­вращается в 4, вследствие чего из стека выталкиваются все те­перь уже изолированные вершины 4, 2, 3 и т.д. Последователь­ность вершин, вытолкнутых из стека, определяет эйлеров цикл 0-6-4-2-3-4-5-0-2-1-0 для всего графа.

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

РИСУНОК 17.22. ЧАСТИЧНЫЕ ЦИКЛЫ

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

Часть 5. Алгоритмы на графах

РИСУНОК 17.23. ПОИСК ЭЙЛЕРОВА ПУТИ МЕТОДОМ УДАЛЕНИЯ ЦИКЛОВ

Этот рисунок служит иллюстрацией того, как программа 17.19 находит эйлеров цикл из вершины О в вершину 0 на простом графе. В этот цикл входят жирные черные ребра, содержимое стека показа­но под каждой диаграммой, список смежных вершин, не входящих в искомый цикл, находится слева от диаграммы, а списки смежных вершин ребер, не попавших в цикл, показаны слева от каждой диаг­раммы.