ОПРЕДЕЛЕНИЕ. Цикл в графе Gназывается циклом Эйлера, если он проходит через все ребра графа и каждое ребро проходится один раз

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

Например, для графа G, изображенного на рис. 5.17., имеется цикл Эйлера, а граф G ₁ такого цикла не имеет.

G G ₁

Рис. 5.17

Для тривиального графа, состоящего из единственной вершины, цикл Эйлера - это цикл длины 0 или цикл, состоящий из единственной вершины.

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

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

А A

B C

B C

D D

Рис. 5.18.

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

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

Большое число перестановок даже для графов с небольшим количеством ребер делает предложенный метод практически неприменимым.

Рассмотрим более простой способ установления существования и построения циклов Эйлера. Он основан на использовании характеристического свойства графов, имеющих такие циклы.