Поиск Эйлерового цикла и пути

Эйлеров путь и цикл

Эйлеров путь(цепь) проходит через каждое ребро графа ровно по одному разу.

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

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

Сервис использует алгоритм поиска Эйлеров цикла на основе циклов.

Будем рассматривать самый общий случай — случай ориентированного мультиграфа, возможно, с петлями. Также мы предполагаем, что эйлеров цикл в графе существует (и состоит хотя бы из одной вершины). Для поиска эйлерова цикла воспользуемся тем, что эйлеров цикл — это объединение всех простых циклов графа. Следовательно, наша задача — эффективно найти все циклы и эффективно объединить их в один.

Кроме того, перед поиском цикла проверяется его существование, для этого происходит поиск степени вершин.

Более подробно вы можете узнать об этом алгоритме в Википедии.

Реализацию алгоритма на языке C++ вы можете найти в нашем репозитории на GitHub: Реализация поиска Эйлерового цикла в Graphoffline.

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

Для поиска Эйлеров пути мы добавляем псевдо ребро соединяющие начальную и конечную вершину Эйлерова пути.

Начальная и конечная вершина для неориентированного графа будет иметь нечётные степени.

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

Как использовать

1. Создайте граф.
2. Выберите пункт меню Алгоритмы -> "Найти Эйлеров цикл" для поиска Эйлеров цикл.

1. Выберите пункт меню Алгоритмы -> "Найти Эйлерову цепь" для поиска Эйлеровой цепи.