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

Считается, что теория графов началась с задачи о кенигсбергских мостах, поставленной и решенной Эйлером. На рис. 5 приведена схема мостов в г. Кенигсберге времен Эйлера.

C

A D

B

Рис. 5

На этой схеме B и C – берега реки Преголь, а A и D – острова. Острова соединены с берегами и друг с другом семью мостами. Требуется так составить маршрут, чтобы пройти каждый мост ровно по одному разу и вернуться в исходную точку. Можно построить граф задачи, в котором каждой части города соответствует вершина, а каждому мосту – ребро

(рис. 6).

C

D A

B

Рис. 6

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

Задача о кенигсбергских мостах решается с помощью следующего несложного рассуждения. Предположим, что на графе с рис. 6 существует эйлеров цикл. Рассмотрим последовательность «выходов» – «заходов» для вершины из этого цикла. Если вершина промежуточная, последовательность имеет вид: «зашел» – «вышел» – «зашел» – «вышел» –… –

«зашел» – «вышел»; если вершина начальная: «вышел» –

«зашел» – «вышел» – «зашел» – … – «вышел» – «зашел». В любом случае вершина должна быть инцидентна четному числу ребер, по которым только и можно «зайти» и «выйти». Таким образом, если на графе имеется эйлеров цикл, степени всех вершин должны быть четными. Граф на рис. 6 этим свойством не обладает, а значит, составит соответствующий маршрут невозможно.

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

«выходов» – «заходов» имеет вид: «зашел» – «вышел» –… –

«зашел» – «вышел»; для начальной вершины: «вышел» –… –

«зашел» – «вышел»; для конечной: зашел» – «вышел» –… –

«зашел». Таким образом, все промежуточные вершины имеют четные степени, а начальная и конечная – нечетные. Менее тривиальным является обратное утверждение.

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