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

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

Теорема 4.5 Конечный граф G является эй­леровым графом тогда и только тогда, когда он связан и все степени его вершин четны.

Доказательство. Условие связности, очевидно, необходимо. Условие четности степеней вершин также не­обходимо, поскольку цикл, выйдя по одному ребру, должен возвратиться по другому.

Докажем достаточность. Предположим, что необходи­мые условия выполнены. Начнем строить цепь из про­из­вольной вершины a = v₀ и будем продолжать ее, переходя от v₀ к v₁, от v₁ к v₂ и так далее, последовательно отмечая пройденные ребра. Очевидно, список вершин, начавшись на v₀, должен на v₀ и закончиться за конечное число шагов. В противном случае приходим к противоречию о связности графа либо, допуская связность, приходим к противоречию о четности степеней всех его вершин.

Если при построении цепи все ребра графа G ока­за­лись отмеченными, то эйлеров цикл построен и этот цикл является эйлеровым графом G. В противном случае на G бу­дут не отмечены некоторые ребра. В силу связности графа G неотмеченные ребра составят связный подграф G. Все сте­пени вершин, этого подграфа четны. Это обусловлено тем, что все вершины, как исходного графа, так и построенного цикла имеют четные степени. На графе G найдется хотя бы одно из неотмеченных ребер, которое инцидентно одной из вершин построенной цепи. Это обусловлено связностью гра­фа G. Обозначим эту вершину b. Повторяя процесс постро­ения цикла из вершины b на подграфе G снова возвра­щаемся в эту же вершину за конечное число шагов.

Обозначим: P(v_i,v_j) — некоторая цепь из v_i в v_j. Очеви­дно, объединяя цепи так, что P(a, b)  P(b, b)  P(b, a) мы имеем цикл P(a, a), который мощнее по множеству входя­щих в него ребер, чем P(a, a),

Если цикл P(a, a)  G, то повторим процесс увели­чения мощности цикла P(a, a), включив в него новые ребра, аналогично ранее выполненному процессу. Тогда за конеч­ное число шагов k имеем P^k(a, a) = G, что и требовалось.

Ясно, что доказанная теорема определяет также и алгоритм построения эйлерового цикла на графе.

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

Говорят, что множество цепей P₁, P₂,…, P_n покрывает граф G, если G = P₁  P₂ … P_n и P₁  P₂ … P_n = .

Теорема 4.6 Пусть G — связный граф с k вер­шинами нечетной степени. Тогда минимальное по­кры­тие графа цепями имеет мощность k / 2.

Доказательство. В силу теоремы 4.4 число вершин не­четной степени четно. Следовательно, каждая из k вершин нечетной степени должна быть концом одной из покры­ва­ющих цепей графа. Отсюда с необходимостью следует, что число всех покры­вающих цепей должно быть не менее, чем k / 2. Расширим граф G до эйлерова графа, добавив k / 2 ребер, соединяющих различные пары вершин нечетной степени. Тогда на графе определен единственный эйлеров цикл. Аннулируя ребра, вместе с каждым аннулированным ребром имеем и новую цепь. Тогда число k / 2 является также и достаточным чис­лом цепей, покрывающих граф.

Для ориентированных графов можно получить ана­логичный результат. В частности, имеет место

Теорема 4.7 Для того, чтобы на ориенти­рованном графе G существовал контур, содержащий все дуги G, необходимо и достаточно, чтобы число всех входящих и выходящих дуг было одинаковым в каждой из вершин.

Такой контур называется эйлеровым контуром.