Цикл в графе называется эйлеровым, если он содержит все ребра графа. Связный граф, в котором существует эйлеров цикл, также называется эйлеровым. Эйлеровый граф можно нарисовать не отрывая карандаша от бумаги.
Пример 4.11.
Теорема Эйлера. Связный граф является эйлеровым тогда и только тогда, когда степени всех его вершин четные.
Для нахождения эйлеровой цепи в связной графе, который имеет вершины только четной степени, используют алгоритм Флери. Этот алгоритм использует два правила:
1. Стартуем из произвольной вершины графа и идем по ребрам, включая эти ребра в эйлерову цепь и удаляя их из графа.
2. Выбираем в очередной вершине путь по перешейку только в том случае, если нет пути по циклу. Перешейком называется ребро, не принадлежащее никакому циклу.
Пример 4.12.
Начать построение эйлерового цикла можно с любого ребра графа. Начиная с е1, получим цикл
v1, e1, v5, e2, v4 ,e3, v3 ,e4 , v4 ,e5 ,v1,e6 ,v3, e8, v2, e7 ,v1.
В данном случае сразу получили эйлерову цепь. Если в графе остаются ребра, которые нельзя использовать для продолжения имеющегося пути, то следует начать строить простой замкнутый цикл из уже пройденной вершины и инцидентного ей ребра, если последнее ранее не использовалось.
