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

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

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

Теорема. Для связного графа G следующие утверждения эквивалентны'.

(1) G — эйлеров граф;

(2) каждая вершина графа G имеет четную степень;

(3) множество ребер графа G можно разбить на простые циклы.

Доказательство. (1) влечет (2). Пусть Т — эйлеров цикл в G. Каждое прохождение данной вершины в Т вносит 2 в степень этой вершины и, поскольку каждое ребро графа G появляется точно один раз в Т, любая вершина должна иметь четную степень.

(2) влечет (3). Так как G — связный и нетривиальный граф, то степень каждой вершины равна, по крайней мере 2, так что G содержит простой цикл Z. Удаление ребер цикла Z приводит к остовному подграфу G1; в котором также каждая вершина имеет четную степень. Если в G1 нет ребер, то (3) уже доказано; в противном случае применим высказанные выше соображения к G1 и получим граф G2, в котором опять степени всех вершин четны, и т. д. Одновременно с пустым графом Gn получаем разбиение ребер графа G на n простых циклов.

(3) влечет (1). Пусть Z1 — один из простых циклов этого разбиения. Если G состоит только из этого цикла, то, очевидно, что G — эйлеров граф. В противном случае другой простой цикл Z2 в G имеет вершину и, общую с Z1 Маршрут, начинающийся с v и состоящий из цикла Z2 и следующего непосредственно за ним цикла Z2, является замкнутой цепью, которая содержит ребра этих двух циклов. Продолжая эту процедуру, мы можем построить замкнутую цепь, содержащую все ребра графа G; следовательно, G — эйлеров граф.

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

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

Следствие(а).Пусть G — связный граф, в котором 2п вершин имеют нечетные степени. Тогда множество ребер графа G можно разбить на n открытых цепей.

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