5.11. Эйлеровы графы

Эйлеровой цепью для неориентированного графа называется такая цепь, которая содержит все рёбра графа и притом только по одному разу. Цепь называется эйлеровой, если она содержит все ребра графа.

Эйлеров цикл — это эйлерова цепь, являющийся циклом. Цикл называется эйлеровым, если он содержит все ребра графа.

Эйлеров граф — граф, содержащий эйлеров цикл.

Полуэйлеров граф — граф, содержащий эйлерову цепь.

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

Теорема. Граф является полуэйлеровым, если в нем не более двух вершин нечетной степени.

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

Пример 5.2. Граф на рис.27 является эйлеровым, так как в нем есть эйлеров цикл 6123143546.

Пример 5.3. Граф G (рис. 28) является полуэйлеровым, так как цепь 6,1,2,3,1,4,3,5,4,6,5 – эйлерова. В графе G ровно две вершины нечетной степени: v₅ и v₆, поэтому эйлеров цикл отсутствует.

Поиск эйлерова цикла может быть произведен по алгоритму Флери, который состоит в следующем:

1. начинаем с любой вершины и “стираем” пройденные ребра.

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

Пример 5.4. Рассмотрим граф, изображенный на рис. 29 (он эйлеров в силу теоремы Эйлера о циклах) и найдем в нем эйлеров цикл.

Пусть вершина v₁ выбрана как начальная, а ребро (v₁,v₅) стерто на первом шаге. Далее стерто ребро (v₅,v₂) и (v₂,v₆). Тогда текущим графом становится граф, изображенный на рис. 28 справа (текущая вершина v₆). На следующей итерации нельзя выбрать ребро(v₆,v₃) из-за ограничения; вместо него выбрано ребро (v₆,v₅). Дальнейший выбор ребер определен однозначно, так что в итоге будет построен следующий эйлеров цикл: 1,5,2,6,5,4,6,3,2,1.

Для нахождения эйлеровых циклов в графе может быть использована лемма о хороводах.

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

Следствие: семейство ребер эйлерова графа можно разбить на непересекающиеся по ребрам циклы.

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

Пример 5.5. Разобьем граф, изображенный на рис. 30, на непересекающиеся простые циклы.

Выберем любую вершину и найдем произвольный цикл. Начнем обход по этому циклу, пока не встретим вершину, одновременно принадлежащую новому циклу. Перескочим на новый цикл. Если при обходе по нему опять встретится вершина, принадлежащая дополнительно еще одному новому циклу, то нужно перескочить на последний новый цикл. Так будет продолжаться, пока не закончатся появляющиеся новые циклы. После обхода последнего цикла произойдет возвращение на предпоследний новый цикл и т.д. В результате вернемся в исходную вершину. В примере получится эйлеров цикл: 1,2,5,4,3,2,4,6,5,1,7,6,1.