Эйлеров путь в графе — это путь, проходящий по всем рёбрам графа и притом только по одному разу.
Чтобы определить, существует ли эйлеров путь, нужно воспользоваться теоремой: эйлеров путь в связном графе существует тогда и только тогда, когда в нём имеется не более двух вершин с нечётными степенями.
Кроме того, граф должен быть достаточно связным (то есть если удалить из него все изолированные вершины, то должен получиться связный граф).
Если есть две вершины с нечётной степенью, то можно построить новый граф, добавив ребро, соединяющее эти вершины. В новом графе степени всех вершин чётны и, следовательно, существует эйлеров цикл. Удалив из этого цикла последнее ребро, получим эйлеров путь в исходном графе.
Рассмотри изображённые графы и заполни пропуски.
В графе на рисунке А
отсутствует
эйлеров путь.
В графе на рисунке Б
присутствует
эйлеров путь.