Эти понятия возникли в статье Эйлера в 1735 г., в которой он решал задачу о Кенигсбергских мостах и впервые ввел понятие графа. На рис. 3.39, а приведен план расположения семи мостов в Кенигсберге (ныне Калининграде). Задача состоит в том, чтобы пройти каждый мост по одному разу и вернуться в исходную точку С. Поскольку в конце обхода нужно вернуться в исходную часть города, и на каждом мосту нужно побывать по одному разу, этот маршрут является простым циклом, содержащим все ребра графа. В дальнейшем такие циклы стали называть эйлеровыми, а графы, имеющие эйлеров цикл – эйлеровыми графами.
а) б)
Рис. 3.39. Схема Кенигсбергских мостов и соответствующий граф
Эйлеров цикл можно считать следом пера, вычерчивающего этот граф, не отрываясь от бумаги. Таким образом, эйлеровы графы – это графы, которые можно изобразить одним росчерком пера, причем процесс такого изображения начинается и заканчивается в одной и той же точке.
Обнаружив, что в данном графе не существует циклических обходов, проходящих по всем ребрам по одному разу, Эйлер обратился к общей задаче: при каких условиях в графе можно найти такой цикл? Ответ на этот вопрос дает следующая теорема.
|
|
Теорема 1 (Эйлера). Конечный связный неориентированный мультиграф является эйлеровым графом тогда и только тогда, когда в нем отсутствуют вершины нечетной степени.
Доказательство. Каждый раз, когда эйлеров цикл проходит через какую-либо вершину, он должен войти в нее по одному ребру, а выйти по другому. Поэтому условие отсутствия вершин нечетной степени в эйлеровом графе является необходимым.
Для доказательства достаточности предположим, что все вершины графа имеют четные степени. Начнем цепь Р в произвольной вершине хi графа G (рис. 3.40, а), и будем продолжать ее, насколько возможно, все время через новые ребра. Так как в каждой вершине число ребер четно, этот процесс может закончиться только в xi. Если цикл Р содержит не все ребра графа G, то удалим из G часть, соответствующую циклу Р. Графы Р и G имеют четные степени всех вершин. То же должно быть справедливо и для оставшегося графа `Р.
а) б)
Рис. 3.40. Иллюстрация доказательства теоремы Эйлера (а) и пример построения эйлерова цикла (б)
Так как граф G связен, в цикле P должна найтись вершина xj, инцидентная также ребрам `Р. Из хj можно построить новую цепь Р', содержащую только ребра из `Р. И снова такая цепь может закончиться только при возвращении в хj .
Процесс построения эйлерова цикла иллюстрирует рис. 3.40, б. Объединяя, например, циклы (x1, х2, х3, х4, х5, х6, x1) и (х3, х7, х8, x3,x5, x1 x3), получим эйлеров цикл (x1, x2, x3, x7, x8, х3,х5, х1, х3, х4, х5, х6, x1).
Как граф с эйлеровым циклом можно рассмотреть схему обхода выставки по различным коридорам, которую посетители должны пройти согласно указателям так, чтобы увидеть каждый экспонат по одному разу.
|
|
Эйлеровой цепью называется цепь, включающая все ребра данного конечного неориентированного графа G(X), но имеющая различные начало xi и конец xj. Чтобы в графе существовала эйлерова цепь, он должен быть связным и все вершины в нем, кроме хi и xj, должны иметь четные степени. Степени вершин хi и xj должны быть нечетными, что естественно, так как из xi мы лишний раз выходим, а в xj мы лишний раз входим. Эти условия являются достаточными для существования эйлеровой цепи.
Важен также следующий вопрос: каково наименьшее количество не пересекающихся по ребрам цепей, покрывающих конечный связный граф G(X) (покрыть – значит включить все ребра графа в цепь)? На этот вопрос отвечает теорема 2.
Теорема 2. В конечном связном неориентированном графе G(X) с k вершинами нечетной степени минимальное число непересекающихся по ребрам цепей, покрывающих G(X) равно k/2.
Доказательство. Пусть G(X) не является эйлеровым графом и k – число его вершин нечетной степени. Ранее было доказано, что k четно. Каждая вершина нечетной степени должна быть концом хотя бы одной из покрывающих граф цепей. Следовательно, число таких цепей не меньше, чем k/2. Но можно показать, что и не больше. Соединим попарно вершины нечетной степени k/2 ребрами. Тогда степень каждой вершины увеличится на единицу и станет четной. Получится эйлеров граф, в котором существует эйлеров цикл. Теперь будем постепенно выбрасывать присоединенные ребра. При выбрасывании первого ребра эйлеров цикл превратится в эйлерову цепь, а при выбрасывании каждого последующего ребра одна из возникших к этому моменту цепей разобьется на две части. Таким образом, общее число этих цепей равно k/2.
Следствие. Из теоремы 2 следует, что если в связном неориентированном мультиграфе имеются две вершины нечетной степени xi и xj, то существует эйлерова цепь, начинающаяся в хi, и кончающаяся в xj.
В качестве примера рассмотрим граф на рис. 3.41. В нем х1, х2, х3, х5 – вершины нечетной степени. Добавим два ребра: (х2, х5), (х1 х3) (штриховые линии). Получим эйлеров граф с эйлеровым циклом (x1, x2, х3, х4, х5, х2, x5, х6, х1, х3, х1). Убрав (х3, х1), получим эйлерову цепь. Убрав (х2, х5), получим 2 покрывающих цепи: (x1, х2, х3, х4, х5, х2) и (х5, х6, х1, х3).
Рассмотрим теперь случай конечного ориентированного графа. Чтобы в конечном ориентированном графе существовал эйлеров цикл (контур), необходимо и достаточно, чтобы полустепени исхода и захода вершин этого графа по входящим и исходящим дугам были равны:
m'(xi) = m"(хi), " xi Î X.
Доказательство то же, что и для неориентированного графа.