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

Пусть G – псевдограф. Цепь (цикл) в G называется эйлеровой (эйлеровым), если она (он) проходит по одному разу через каждое ребро псевдографа G.

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

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

Пусть G – связный мультиграф, степени вершин которого – четные числа.

ЗАДАНИЕ 4. Построить эйлеров цикл в графе.

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

Данные: матрица инцидентности В(G) мультиграфа G.

Результат: последовательность ребер, образующих эйлеров цикл.

1. Выбрать произвольную вершину v.

2. Выбрать произвольное ребро x, инцидентное v, и присвоить ему номер 1. (Назовем это ребро “пройденным”).

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

4. Находясь в вершине w, не выбирать ребра, соединяющего w с v, если только есть возможность другого выбора.

5. Находясь в вершине w, не выбирать ребра, которое является “перешейком” (при удалении которого граф, образованный незачеркнутыми ребрами, распадается на две компоненты связности, имеющие хотя бы по одному ребру).

6. После того, как в графе будут занумерованы все ребра, цикл m = [ x_{i 1}, x_{i 2},…, x_im ], образованный ребрами с номерами от 1 до m, где m – число ребер в графе, есть эйлеров цикл.

Замечание. Прежде чем строить эйлеров цикл, проверить условие существования этого цикла.

ЗАДАНИЕ 5. Построить эйлерову цепь в графе.

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