Составители:
Рубрика:
88
Хотя доказательство проведено для неори-
ентированных графов, оно сразу переносится на
ориентированные, только требование четности за-
меняется теперь на такое: число входящих в каж-
дую вершину ребер должно быть равно числу вы-
ходящих.
Следствие 1. Для связного эйлерова графа G мно-
жество ребер можно разбить на простые циклы.
Следствие 2. Для того чтобы связный граф G по-
крывался единственной эйлеровой цепью, необхо-
димо и достаточно, чтобы он содержал ровно 2
вершины с нечетной степенью. Тогда цепь начи-
нается в одной из этих вершин и заканчивается в
другой.
3.3. Алгоритмы построения эйлерова цикла
Выше был установлен эффективный способ
проверки наличия эйлерова цикла в графе. Для
этого достаточно убедиться, что степени всех
вершин четные. Предложенный в доказательстве
алгоритм линеен, т.е. число действий прямо про-
порционально числу ребер.
Алгоритм построения эйлерова цикла
в эйлеровом графе
Вход: Эйлеров граф G (V, E), заданный матрицей
смежности. Для простоты укажем, что Г [v] –
множество вершин, смежных с вершиной v.
89
Обоснование алгоритма: Принцип действия этого
алгоритма заключается в следующем. Начиная с
произвольной вершины, строим путь, удаляя ребра
и запоминая вершины в стеке, до тех пор, пока
множество смежности очередной вершины не
окажется пустым, что означает, что путь удлинить
нельзя. Заметим, что при этом мы с необходимо-
стью придем в ту
вершину, с которой начали. В
противном случае это означало бы, что вершина v
имеет нечетную степень, что невозможно по усло-
вию. Таким образом, из графа были удалены ребра
цикла, а вершины цикла были сохранены в стеке S.
Заметим, что при этом степени всех вершин оста-
лись четными. Далее вершина v выводится
в каче-
стве первой вершины эйлерова цикла, а процесс
продолжается, начиная с вершины, стоящей на
вершине стека.
Приведем еще один алгоритм построения
эйлерова цикла в эйлеровом графе – это Алгоритм
Флёри, он позволяет пронумеровать ребра исход-
ного графа так, чтобы номер ребра указывал каким
по счету это ребро войдет эйлеров цикл.
Алгоритм Флёри
1. Начиная с любой вершины v, присваиваем ребру
vu номер 1. Вычеркиваем это ребро из списка ре-
бер и переходим к вершине u.
Хотя доказательство проведено для неори- Обоснование алгоритма: Принцип действия этого
ентированных графов, оно сразу переносится на алгоритма заключается в следующем. Начиная с
ориентированные, только требование четности за- произвольной вершины, строим путь, удаляя ребра
меняется теперь на такое: число входящих в каж- и запоминая вершины в стеке, до тех пор, пока
дую вершину ребер должно быть равно числу вы- множество смежности очередной вершины не
ходящих. окажется пустым, что означает, что путь удлинить
Следствие 1. Для связного эйлерова графа G мно- нельзя. Заметим, что при этом мы с необходимо-
жество ребер можно разбить на простые циклы. стью придем в ту вершину, с которой начали. В
Следствие 2. Для того чтобы связный граф G по- противном случае это означало бы, что вершина v
крывался единственной эйлеровой цепью, необхо- имеет нечетную степень, что невозможно по усло-
димо и достаточно, чтобы он содержал ровно 2 вию. Таким образом, из графа были удалены ребра
вершины с нечетной степенью. Тогда цепь начи- цикла, а вершины цикла были сохранены в стеке S.
нается в одной из этих вершин и заканчивается в Заметим, что при этом степени всех вершин оста-
другой. лись четными. Далее вершина v выводится в каче-
стве первой вершины эйлерова цикла, а процесс
3.3. Алгоритмы построения эйлерова цикла
продолжается, начиная с вершины, стоящей на
Выше был установлен эффективный способ вершине стека.
проверки наличия эйлерова цикла в графе. Для Приведем еще один алгоритм построения
этого достаточно убедиться, что степени всех эйлерова цикла в эйлеровом графе – это Алгоритм
вершин четные. Предложенный в доказательстве Флёри, он позволяет пронумеровать ребра исход-
алгоритм линеен, т.е. число действий прямо про- ного графа так, чтобы номер ребра указывал каким
порционально числу ребер. по счету это ребро войдет эйлеров цикл.
Алгоритм построения эйлерова цикла Алгоритм Флёри
в эйлеровом графе
1. Начиная с любой вершины v, присваиваем ребру
Вход: Эйлеров граф G (V, E), заданный матрицей vu номер 1. Вычеркиваем это ребро из списка ре-
смежности. Для простоты укажем, что Г [v] – бер и переходим к вершине u.
множество вершин, смежных с вершиной v.
88 89
