5. Обходы графов: эйлеровы цепи и циклы, необходимые и достаточные условия их существования, алгоритм Флери.

Графом G называется пара (V, E), где – непустое множество вершин графа, а– множество ребер графа, причем каждое ребро – это неупорядоченная пара различных вершин.

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

Определение. Эйлеров цикл – цикл, при котором происходит обход всех вершин через единичное прохождение каждого ребра.

Утверждение. Критерий существования эйлерова цикла - только тогда, когда в графе все вершины имеют четную степень; связность.

Утверждение. Критерии существования эйлеровой цепи - существует тогда и только тогда, когда в графе ровно две вершины имеют четную степень; связность.

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

• Из произвольной начальной вершины по любому инцидентному ей ребру переходим в следующую вершину, нумеруем это ребро цифрой 1 и удаляем его.

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

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