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

Цикл, проходящий через каждое ребро графа ровно один раз, называется эйлеровым циклом. Граф, имеющий эйлеров цикл, называется эйлеровым графом .

Теорема (Л. Эйлер, 1736 г.)

Связный граф является эйлеровым тогда и только тогда, когда степени всех его вершин четные

Алгоритм

Создаем 2 стека - в 1-ый заносим вершину 1, затем вершину 2(смежную с 1), затем например 4(смежную с 2), пусть затем 1 смежна с 4 – мы снова вернулись в 1, тогда заносим 1 как 1-ый элемент стека 2 и удаляем последнюю 1 из стека 1, пробуем идти в другую смежную с 4 вершину, пусть это 6, из 6 в 7, из 7 в 5, из 5 в 4, а в 4 уже были , тогда заносим 4 как 2-ой элемент стека 2 и удаляем последнюю 4 из стека 1, затем из 5 в 3, из 3 в 2, из 2 в 5, а 5 уже была, тогда заносим ее как 3-ий элемент очереди 2 и удаляем из очереди 1, а затем поочереди удаляем элемента с конца из стека 1 и заносим в стек 2, в итоге в стеке 2 получаем эйлеров цикл – 1 4 5 2 3 5 7 6 4 2 1.

Трудоемкость алгоритма – O(m).