Алгоритм построения эйлерова цикла в эйлеровом графе

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

v ₁

v ₃

v ₂

v ₄

Содержательная постановка задачи о Кенигсбергских мостах дана в теме 1. Переформулируем эту задачу в терминах теории графов. Для этого рассмотрим следующий неориентированный мультиграф:

В этом графе вершины v ₁ и v ₄ соответствуют берегам, а v ₂ и v ₃ – островам.
Ребра отображают мосты. Таким образом, на языке теории графов исходная задача формулируется следующим образом: существует ли в указанном мультиграфе цикл, содержащий все ребра данного мультиграфа?

Определение: Цепь (цикл), содержащая все ребра графа и притом по одному разу, называется эйлеровой цепью (эйлеровым циклом). Граф, содержащий эйлеров цикл, называется эйлеровым графом.

Теорема. Для того, чтобы конечный связный неориентированный мультиграф был эйлеровым необходимо и достаточно, чтобы все его вершины имели чётные степени.

Доказательство:

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

Достаточность. Предположим, что все вершины связного графа G имеют чётные степени. Тогда, в силу связности графа G, для всех его вершин выполняется условие d (v)>0. Кроме того, в силу чётности вершин, должно быть d (v)³ 2 для всех v. По теореме Эйлера имеем:.Это значит, что: или, и следовательно граф G не является деревом, а поэтому он содержит хотя бы один простой цикл Z ₁ (Z ₁ - множество ребер), тогда G \ Z ₁ – остовный подграф, в котором все степени вершин также четные. Исключим из рассмотрения изолированные вершины, тогда в графе G \ Z ₁ существует простой цикл Z ₂ ÌG \ Z ₁, далее выделим Z ₃ и т.д. В результате этого получается разбиение множества ребер на простые циклы, то есть:,где.

Далее, возьмем какой-либо простой цикл из полученного разбиения. Если, то теорема доказана. Если нет, то в силу связности графа G, существуют цикл и вершина v ₁ такие, что и. Маршрут, объединяющий и, является циклом. Если, то теорема доказана. Если нет, то имеется цикл, при котором существует вершина v ₂ такая, что и. Далее будем наращивать эйлеров цикл до тех пор, пока не исчерпаем всё разбиение. В результате получаем эйлеров цикл всего графа.

Этот алгоритм задается следующими правилами:

1) Выбирается произвольная вершина v.

2) Выбирается ребро e инцидентное вершине v и ему присваивается номер 1 (это ребро называется пройденным).

3) Каждое пройденное ребро вычеркивается и ему присваивается номер на 1 больший номера предыдущего вычеркнутого ребра.

4) При нахождении в произвольной вершине x, не выбирается ребро, соединяющее x с v, если есть возможность другого выбора.

5) Ребро не проходится, если оно является перешейком. Перешейк – это ребро, при удалении которого, граф, образованный невычеркнутыми ребрами, распадается на две компоненты связности, каждая из которых имеет хотя бы одно ребро.

6)

v

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

Пример. Найти эйлеров цикл в эйлеровом графе

После выбора вершины v и прохождения рёбер 1 и 2 имеется три возможности: выбрать 3,6 или 7. Ребро 7 является перешейком, поэтому выбирается любое из оставшихся рёбер, например 3. Далее идёт обход оставшихся рёбер получается эйлеров цикл.

Дата добавления: 2014-01-11