Все вершины имеют четные валентности. Разметка ребер может быть, например, такой:

Тогда эйлеров цикл (при вершине 1) имеет вид:

1 u1 2 u2 3 u3 4 u4 5 u6 6 u8 7 u7 5 u5 3 u10 7 u9 2 u11 6 u12 1. J

7.5.4 Эйлеровы пути

Введем следующие обозначения: v+(x) = s+(x) + s±(x);

v¡(x) = s¡(x) + s±(x):

v+(x) и v¡(x) – полувалентности вершины x.

Определение. Путь в орграфе G, содержащий все его дуги, называется эйлеровым путем.

Теорема 7.7 Эйлеров путь из вершины s в вершину t существует тогда и только тогда, когда

1) x 2 X n fs; tg [v+(x) = v¡(x)]:

2) s =6 t : v+(s) ¡ v¡(s) = 1; v¡(t) ¡ v+(t) = 1:

Доказательство полностью аналогично предыдущему.

Для решения задачи нахождения эйлерова цикла вручную (например, для решения головоломок) можно использовать следующий алгоритм.

7.5.4.1Алгоритм Флери

( все валентности – четные).

Маршрут начинается с любой вершины. Пройденное ребро удаляется. Не проходить по ребру, если его удаление приводит к увеличению числа компонент связности (не считая изолированных вершин).

Некоторые обобщения задачи нахождения эйлеровой цепи.

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

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

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

7.5.5Гамильтоновы цепи и циклы

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

Пока неизвестен какой-либо достаточно простой критерий необходимости и достаточности существования гамильтоновой цепи (цикла) для произвольного графа G. Неизвестен также алгоритм нахождения гамильтоновой цепи (цикла) полиномиальной сложности.

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

(X; U) имеется наибольшая простая цепь

Q = x0 u1 : : : xl¡1 ul xl,

такая, что l ¸ 2 и s(x0) + s(xl) ¸ l + 1. Тогда в G существует гамильтонов цикл.

Теорема 7.9 Если для двух несмежных различных вершин x и y связного обыкновенного графа G с n ¸ 3

s(x) + s(y) ¸ n(G),

то G имеет гамильтонов цикл. Если

s(x) + s(y) ¸ n(G) ¡ 1,

то существует гамильтонова цепь.

Следствие.Если G – связный обыкновенный граф с n(G) ¸ 3, такой, что для всех его вершин x

s(x) ¸ n(2G), то в G существует гамильтонов цикл.

Самый очевидный алгоритм нахождения гамильтоновой цепи состоит в генерировании n! перестановок различных последовательностей вершин, и в проверке каждой из них на наличие простой цепи. Такой алгоритм требует по меньшей мере n!n шагов и его сложность имеет порядок n!n ¼ O(nn).

Продемонстрируем на примере методы поиска в ширину и в глубину для нахождения гамильтоновых цепей (циклов) на орграфе.

7.5.5.1Алгоритм поиска гамильтоновой цепи (цикла) в ширину

Пример 7.14. Алгоритм поиска в ширину заключается в последовательном нахождении цепей длины 2; 3; : : : ; n и проверке на каждом шаге найденной цепи на допустимость (отсутствие цикла длины меньшей чем n).

Пусть граф G задан как бинарное отношение с помощью массива пар вершин. Цепи длины 2 , 3,... будем находить как степени отношений R2; R3; : : : .

G = (X; R); X = fa; b; c; d; eg;

цепи (пути) длины n¡1 или простые циклы длины n, т.е. исключать в процессе поиска циклы длины меньше, чем n.

Дерево поиска для графа из предыдущего примера имеет сле-

дующий вид:

Вставить картинку

Вычеркнутые ребра в дереве поиска соответствуют циклам длины менее, чем n.

Найденные гамильтоновы циклы: fabdcea; adcbeag.

7.5.5.3Связь между эйлеровыми и гамильтоновыми циклами

Построим реберный граф L (linegraph) данного графа G следующим образом:

²Множество вершин графа L соответствует множеству ребер графа G.

²Вершины графа L смежны, если смежны соответствующие ребра в графе G.

Верны следующие утверждения:

1.Если G имеет эйлеров цикл, то его реберный граф L имеет как эйлеров, так и гамильтонов цикл.

2.Если G имеет гамильтонов цикл, то его реберный граф L также имеет гамильтонов цикл.

Утверждения, обратные к 1 , 2 – неверны. Таким образом эти утверждения мало что дают для практики.

Задача нахождения гамильтоновой цепи (цикла) имеет обобщение на взвешенные графы.

Задача коммивояжера (travelling seller problem, TSP) формулируется следующим образом: во взвешенном графе (обычно – полном) найти гамильтонову цепь (цикл) наименьшей длины (с наименьшим суммарным весом ребер).

Название задачи происходит от следующей формулировки: имеется n городов и известны расстояния между каждой парой городов; коммивояжер (бродячий торговец), выходящий из какоголибо города, должен посетить n ¡ 1 других городов и вернуться в исходный. В каком порядке ему нужно посещать города, чтобы общее пройденное расстояние было минимальным ?