Составители:
Рубрика:
86
3.2. Критерий существования эйлерова цикла
Что необходимо, чтобы в графе существовал
эйлеров цикл? Во-первых, граф должен быть свя-
занным: для любых двух вершин должен сущест-
вовать путь, их соединяющий. Во-вторых, для не-
ориентированных графов число ребер в каждой
вершине должно быть четным. На самом деле это-
го оказывается достаточно.
Теорема 3.1. Чтобы в связанном неориентирован-
ном графе G существовал эйлеров цикл, необхо-
димо и достаточно, чтобы число вершин нечетной
степени было четным.
Доказательство.
Необходимость. Любой эйлеров цикл дол-
жен прийти в вершину по одному ребру и поки-
нуть ее по другому, так как любое ребро должно
использоваться ровно один раз. Поэтому
, если G
содержит эйлеров цикл, то степени вершин долж-
ны быть четными.
Достаточность. Пусть G – связный неори-
ентированный граф, все вершины которого имеют
четную степень. Начнем путь из некоторой произ-
вольной вершины x
0
и пойдем по некоторому ра-
нее не использованному ребру к следующей вер-
шине, и так до тех пор, пока не вернемся в верши-
ну x
0
и не замкнем цикл. Если все ребра окажутся
использованными, то нужный эйлеров цикл по-
91
Приведем теперь строгое обоснование кор-
ректности алгоритма Флёри построения эйлерово-
го цикла в данном эйлеровом графе.
Теорема 3.2. Пусть G (V, E) – эйлеров граф. Тогда
следующая процедура всегда возможна и приво-
дит к построению эйлерова цикла графа G (V, E).
Выходя из произвольной вершины, идем по
ребрам графа произвольным образом, соблюдая
при этом следующие правила:
1)
Стираем ребра по мере их прохождения
(вместе с изолированными вершинами, кото-
рые при этом образуются);
2)
На каждом шаге идем по мосту только в том
случае, когда нет других возможностей.
Доказательство.
Убедимся сначала, что указанная процедура
может быть выполнена на каждом этапе. Пусть мы
достигли некоторой вершины v, начав с вершины
u, v ≠ u. Удалив ребра пути из v в u, видим, что ос-
тавшийся граф
G
1
связен и содержит ровно две не-
четных вершины v и u. Согласно следствию 2 из
теоремы 1 граф G
1
имеет эйлеров путь P из v в u.
Поскольку удаление первого ребра инцидентного
u пути P либо не нарушает связности G
1
, либо
происходит удаление вершины u и оставшийся
граф G
2
связен с двумя нечетными вершинами, то
отсюда получаем, что описанное выше построение
3.2. Критерий существования эйлерова цикла Приведем теперь строгое обоснование кор-
Что необходимо, чтобы в графе существовал ректности алгоритма Флёри построения эйлерово-
эйлеров цикл? Во-первых, граф должен быть свя- го цикла в данном эйлеровом графе.
занным: для любых двух вершин должен сущест- Теорема 3.2. Пусть G (V, E) – эйлеров граф. Тогда
вовать путь, их соединяющий. Во-вторых, для не- следующая процедура всегда возможна и приво-
ориентированных графов число ребер в каждой дит к построению эйлерова цикла графа G (V, E).
вершине должно быть четным. На самом деле это- Выходя из произвольной вершины, идем по
го оказывается достаточно. ребрам графа произвольным образом, соблюдая
Теорема 3.1. Чтобы в связанном неориентирован- при этом следующие правила:
ном графе G существовал эйлеров цикл, необхо- 1) Стираем ребра по мере их прохождения
димо и достаточно, чтобы число вершин нечетной (вместе с изолированными вершинами, кото-
степени было четным. рые при этом образуются);
Доказательство. 2) На каждом шаге идем по мосту только в том
Необходимость. Любой эйлеров цикл дол- случае, когда нет других возможностей.
жен прийти в вершину по одному ребру и поки- Доказательство.
нуть ее по другому, так как любое ребро должно Убедимся сначала, что указанная процедура
использоваться ровно один раз. Поэтому, если G может быть выполнена на каждом этапе. Пусть мы
содержит эйлеров цикл, то степени вершин долж- достигли некоторой вершины v, начав с вершины
ны быть четными. u, v ≠ u. Удалив ребра пути из v в u, видим, что ос-
Достаточность. Пусть G – связный неори- тавшийся граф G1 связен и содержит ровно две не-
ентированный граф, все вершины которого имеют четных вершины v и u. Согласно следствию 2 из
четную степень. Начнем путь из некоторой произ- теоремы 1 граф G1 имеет эйлеров путь P из v в u.
вольной вершины x0 и пойдем по некоторому ра- Поскольку удаление первого ребра инцидентного
нее не использованному ребру к следующей вер- u пути P либо не нарушает связности G1, либо
шине, и так до тех пор, пока не вернемся в верши- происходит удаление вершины u и оставшийся
ну x0 и не замкнем цикл. Если все ребра окажутся граф G2 связен с двумя нечетными вершинами, то
использованными, то нужный эйлеров цикл по- отсюда получаем, что описанное выше построение
86 91
