-
Эйлеровы пути и циклы
Задача о кенигсбергских мостах послужила началом теории графов. План расположения семи мостов в Кёнигсберге (ныне г. Калининград) приведен на рис. 3.5.
Рис. 3.5.
Задача состоит в том, чтобы пройти каждый мост по одному разу и вернуться в исходную точку С. Так как существенны только переходы через мосты, план города можно свести к изображению графа, в котором ребра соответствуют мостам, а вершины - разделенным частям города.
Развлечения, в которых требуется обрисовать некоторую фигуру, не прерывая и не повторяя линии, являются, по-видимому, очень давними. Считается, что фигура, называемая саблями Магомета, имеет арабское происхождение.
Эйлер обратился к общей задаче, касающейся графов: в каких случаях в конечном графе можно найти такой цикл, в котором каждое ребро участвовало бы один раз?
Эйлеровым
путем в графе G
= < V,
E
> называется произвольный
путь, проходящий через каждое ребро
графа в точности один раз, т.е. путь
такой, что каждое ребро
появляется в последовательности
в точности один раз как
для некоторого i.
Если
,
то такой путь называется эйлеровым
циклом.
Теорема 3.11. Эйлеров путь в неориентированном простом графе существует тогда и только тогда, когда граф связный и содержит не более, чем две вершины нечетной степени.
Если в
связном графе нет вершин нечетной
степени, то каждый эйлеров путь является
циклом, так как концы эйлерова пути, не
являющегося циклом, всегда вершины
нечетной степени. Предположим, что u
и v
- единственные вершины нечетной степени
в связном графе G
= <V,
T
> и образуем граф G
добавлением дополнительной вершины t
и ребер {u,v}
и {v,t}
(или просто
добавлением ребра {u,v},
если
).
Тогда G
- связный граф без вершин нечетной
степени, а эйлеровы пути в G
будут в очевидном взаимно однозначном
соответствии с эйлеровыми циклами в
G.
В силу этого мы будем заниматься только
эйлеровыми циклами и переформулируем
теорему.
Теорема 3.12. Конечный граф G = <V, E > содержит эйлеров цикл тогда и только тогда, когда
1. G - связен.
2. Все степени его вершин четные.
Доказательство. Условие 1, очевидно, необходимо. Далее, каждый раз, когда эйлеров цикл проходит через какую-то вершину, он должен войти в нее по одному ребру и выйти по другому; поэтому условие 2 также необходимо.
Предположим теперь, что эти два условия выполнены. Начнем путь Р в произвольной вершине а графа G и будем продолжать его, насколько возможно, всё время через новые рёбра. Так как степени всех вершин четны, этот процесс может закончится только в вершине а.
Если Р содержит не все рёбра графа G, то удалим из G часть Р, состоящую из ребер этого цикла.
Графы
Р и G
имеют четные степени вершин, то же будет
справедливо и для остающегося графа
.
Так как
граф G
связен, в Р
должна найтись вершина b,
инцидентная также ребрам из
.
Из b
построим новый путь P,
содержащий ребра только из
.
Снова такой путь может закончится только
при возвращении в b.
Но тогда из Р
и P
составим новый путь P1
,
который возвращается в а и содержит больше ребер, чем Р.
Если P1 не является эйлеровым циклом, то это построение повторяется. Когда процесс закончится, эйлеров цикл будет построен.
Представим изложенный процесс построения эйлерова цикла в виде схемы алгоритма на “псевдоалгоритмическом” языке.