Задача 1. Нахождение эйлерова цикла и эйлерова пути в графе.

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

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

Теорема 2. Эйлеров путь в графе существует тогда и только тогда, когда граф связный и число вершин с нечетной степенью равно 0 или 2.

Алгоритм нахождения эйлерова цикла.

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

2. Выбрать произвольно некоторое ребро, инцидентное вершине А, и присвоить ему номер 1. Это ребро называется помеченным.

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

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

5. Находясь в вершине X, не выбираем рёбра, являющиеся мостом.

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

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

Пример. В следующем графе найти эйлеров цикл.

По теореме 1, эйлеров цикл в данном графе существует, так как степени всех его вершин четны. Используя вышеприведенный алгоритм, найдем эйлеров цикл: 1®4®3®2®1®5®4®6®3®7®2®8®1.