Эйлеровы пути и циклы

Задача о кенигсбергских мостах послужила началом теории графов. План расположения семи мостов в Кёнигсберге (ныне г. Калининград) приведен на рис. 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 составим новый путь P₁

,

который возвращается в а и содержит больше ребер, чем Р.

Если P₁ не является эйлеровым циклом, то это построение повторяется. Когда процесс закончится, эйлеров цикл будет построен. 

Представим изложенный процесс построения эйлерова цикла в виде схемы алгоритма на “псевдоалгоритмическом” языке.