6.7. Эйлеровы графы

Классической в теории графов является следующая задача. Имеются два острова, соединенных семью мостами с берегами реки и друг с другом, как показано на рис. 6.15. Задача состоит в следующем: осуществить прогулку по городу таким образом, чтобы, пройдя по каждому мосту один раз, вернуться обратно. Решение этой задачи сводится к нахождению некоторого специального маршрута на графе.

Рис. 6.15. План расположения мостов и соответствующий ему мультиграф

• Определение. Пусть неориентированный псевдограф. Цепь в называется эйлеровой, если она проходит по одному разу через каждое ребро псевдографа Такой граф называется эйлеровым. Замкнутая эйлерова цепь называется эйлеровым циклом.

Поставим в соответствие плану расположения суши и мостов, приведенному на рис. 6.15, мультиграф на рис. 6.15, в котором каждой части суши соответствует вершина, а каждому мосту — ребро, соединяющее соответствующие вершины. Теперь задача звучит так: найти эйлерову цепь (цикл) в мультиграфе. Решение этой задачи было дано Эйлером.

• Теорема Л. Эйлера. Эйлерова цепь в псевдографе существует тогда и только тогда, когда выполняются следующие условия:

1. Граф связный;

2. Степени внутренних вершин четные (внутренние вершины не являются началом и концом цепи);

3. Если вершины являются началом и концом цепи и а то степени их нечетные;

4. Если вершины являются началом и концом цепи и то степени их четные.

Доказательство. Дано, что существует эйлерова цепь где в которой содержатся все ребра по одному разу. Такая цепь включает все вершины графа, если граф не содержит изолированных вершин. Докажем условия 1—4: 1) по данной цепи из любой вершины можно попасть в любую другую, значит, граф связный; 2) каждая тройка цепи привносит вершине степень два, а так как все ребра в цепи различные, то степени внутренних вершин четные; 3) и 4) доказательства повторяют доказательство пункта 2.

Даны условия 1—4. Построим эйлерову цепь. Предварительно приведем условие 3 к условию 4 включением в граф фиктивного ребра и, которым свяжем вершины Теперь и в случае 3 все вершины будут иметь четную степень. Пусть произвольная вершина (рис. 6.16). Из нее будем строить цепь, выбирая в качестве продолжения пути ребро, которое еще не пройдено. Эта цепь (цикл может закончиться только в вершине А, так как, при входе в любую другую вершину, всегда существует ребро, по которому можно выйти из нее (степени вершин четные).

Возможны два случая: 1) построенный цикл содержит все ребра графа, тогда теорема доказана; 2) содержит не все ребра графа. Во втором случае рассмотрим граф полученный удалением из всех ребер, входящих в Граф вновь содержит вершины только с четными степенями (у каждой вершины удалили по четному числу ребер). Так как связный граф, то существует вершина в инцвдентная ребру из Пусть это вершина Построим из нее цикл так же, как строили цикл Построим общий цикл из так, как это сделано на рис. 6.16. Для вновь проверяем рассмотренные выше два случая, как для

Рис. 6.16. Объединение двух циклов в один цикл

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

Конструктивный характер доказательства теоремы позволяет на формальном уровне в алгоритме 6.5 записать рассмотренный поиск эйлеровой цепи. Исходный граф представлен своей структурой смежности где множество вершин, смежных с Результирующая эйлерова цепь формируется в множестве

Алгоритм 6.5. Алгоритм поиска эйлеровой цепи графа

(см. скан)

Частные же циклы, расширяющие представляются множеством Ребра, включенные в частный цикл (а значит, и в удаляются как пройденные из структуры смежности (из графа). Формирование расширяющих циклов осуществляется до тех пор, пока структура смежности графа содержит хотя бы одно ребро.

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

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

Алгоритм 6.6. Программа поиска эйлеровой цепи графа

(см. скан)

(см. скан)

(см. скан)

(см. скан)

Рассмотрим пример расчета по программе алгоритма 6.6 поиска эйлеровой цепи в графе, изображенного на рис. 6.17.

Рис. 6.17. Пример расчета эйлеровой цепи графа

Для программы алгоритма 6.6 исходные данные структуры смежности графа на рис. 6.17 задаются в текстовом файле Eiler.in. Структура (правило) заполнения файла совпадает с той, которая описана в рассмотренном примере поиска в глубину при расчете по программе алгоритма 6.2.

Данные файла Eiler.in для примера на рис. 6.17:

Результаты расчетов сохраняются в выходном файле Eiler.out со следующей структурой:

На каждом шаге показана строящаяся эйлерова цепь которая расширяется выделенным циклом. Результирующая эйлерова цепь графа отмечена признаком О в начале строки.