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

Началом математической теории графов послужила задача о Кёнигсбергских мостах, поставленная Леонардом Эйлером (1707 – 1783).

Кёнигсберг (теперь Калининград) расположен на обоих берегах реки Преголя и на двух островах этой реки. Берега реки и два острова соединены семью мостами, как показано на рис.1. Эйлер в 1736 г. поставил вопрос: можно ли, начав с некоторой точки, совершить прогулку и вернуться в исходную точку, пройдя по каждому мосту ровно один раз. Если каждый берег и острова считать вершинами графа, а каждый мост – ребром, то карту города можно представить в виде мультиграфа (рис. 1).

B

с d g g

e c d D

C

a b h a b h

A

а б

Рис. 1. Карта города (а) и эквивалентный ей граф (б)

Эйлеровым циклом (цепью) в мультиграфе называется цикл (цепь), содержащий все ребра мультиграфа по одному разу. Граф, имеющий эйлеров цикл, также будем называть э йлеровым. Граф, содержащий эйлерову цепь, называется полуэйлеровым. Эйлеров граф можно нарисовать на бумаге, не отрывая от нее карандаша. Замкнутые линии, которые можно получить, не отрывая карандаша от бумаги, проходя при этом каждый участок один раз, называются уникурсальными. С этими линиями связана задача минимизации холостого хода пера графопостроителя.

Эйлер установил, что задача кёнигсбергских мостов неразрешима, и этот результат ознаменовал возникновение теории графов.

Теорема.Мультиграф обладает эйлеровым циклом тогда и только тогда, когда он связный и все его локальные степени четны.

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

Достаточность докажем индукцией по числу ребер мультиграфа. При теорема справедлива. Пусть утверждение теоремы верно для всех мультиграфов с числом ребер, не превосходящем . Для мультиграфа с числом ребер рассмотрим произвольный простой цикл. Хотя бы один такой цикл обязательно существует для графов с четными степенями вершин. Обозначим его . Далее удалим из все пройденные ребра. Получим мультиграф , в котором все вершины по-прежнему имеют четные степени, но он будет несвязным. Пусть – компоненты связности . Каждая из этих компонент представляет собой связный мультиграф с четными степенями и с числом ребер, меньшим, чем , поэтому по предположению индукции она обладает эйлеровым циклом. Обозначим эйлеровы циклы компонент . Присоединяя к циклу эйлеровы циклы , получаем эйлеров цикл мультиграфа .

Следствия.

1°. Связный мультиграф, имеющий ровно две вершины с нечетной степенью, является полуэйлеровым графом.

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

2°. В общем случае число вершин мультиграфа, имеющих нечетную степень, всегда четно. Если мультиграф имеет таких вершин, то все его ребра можно включить в цепей. Другими словами, мультиграф можно нарисовать, раз отрывая карандаш от бумаги.

Обоснование этого утверждения аналогично предыдущему.

Ребро графа , через которое проходит хотя бы один цикл, называется цикловым. Ребро, которое не входит ни в один цикл, называется перешейком или мостом. Например, в графе, изображенном на рис. 2, ребра и – перешейки, а остальные ребра цикловые.

Рис. 2. Пример разбиения ребер графа на цикловые и перешейки

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