Эйлеровы маршруты и циклы. Теорема Эйлера

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

Эйлеров цикл — это эйлеров путь, являющийся циклом.

1. пока есть цикл, проходящий через v, находим его

добавляем все вершины найденного цикла в массив cycles (сохраняя порядок обхода)

удаляем цикл из графа

2. идем по элементам массива cycles

каждый элемент cycles[i] добавляем к ответу

из каждого элемента рекурсивно вызываем себя: find_all_cycles (cycles[i])

В неориентированном графе

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

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

В ориентированном графе

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