Лекции 14. Основные понятия теории графов. Некоторые виды графов (4 часа)

2. Эйлеровы циклы и цепи
Считают, что начало теории графов положила задача, предложенная Ейлером. В каких случая конечный граф мо­жно определить циклом без дополнений? Если граф G пред­ставим таким циклом, то он называется эйлеровым графом.
Теорема. Конечный граф 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 = .