Эйлеров цикл

Определение. Эйлеров цикл — цикл, который проходит ровно один раз по каждому ребру (дуге) графа.

Определение. Если граф имеет цикл, содержащий все ребра (дуги) графа по одному разу, то граф называется эйлеровым.

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

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

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

Доказательство.

1. Докажем прямую теорему.

Пусть граф G содержит эйлеров цикл, значит, существует цикл, проходящий по всем ребрам графа ровно по одному разу. Будем идти по циклу, и считать степени вершин. Т.к. проходя через вершину каждый раз, прибавляем к её степени 2, то степени всех вершин четны.

2. Докажем обратную теорему (способ доказательства – конструктивный, то есть дает алгоритм построения эйлерова цикла).

Пусть все вершины графа имеют четную степень. Будем строить эйлеров цикл, начиная с некоторой вершины v₀, при этом пройденные ребра будем удалять. Так как все вершины имеют четную степень, то, попав в какую-либо вершину, обязательно найдем ребро, по которому можно из неё выйти. Таким образом, обязательно вернемся в вершину v₀, получив при этом некоторый цикл Р. Если при этом все ребра графа участвуют в цикле, то теорема доказана.

В противном случае, так как граф связен, обязательно найдется ребро не входящее в цикл, но инцидентное какой-либо вершине цикла. Обозначим эту вершину v₁. Будем строить цикл начиная с вершины v₁. Из аналогичных соображений мы обязательно вернемся в вершину v₁, получив цикл Р1. Если при этом все ребра графа присутствуют в циклах Р и Р1, то цикл v₁ Р v₁ Р1 v₁ содержит все ребра графа по одному разу, то есть является эйлеровым, следовательно, теорема доказана. В противном случае продолжаем аналогичные рассуждения. Так как ребер в графе конечное количество построение цикла обязательно закончится.

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

Доказательство аналогично случаю неориентированного графа.

Дата добавления: 2014-12-29