Курсовой проект «Комбинаторные алгоритмы. Поиск кратчайшего пути на графе.»

Построение эйлерова цикла на графе

Постановка задачи

Необходимо найти эйлеров цикл на графе.

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

Методы решения и описания алгоритма

Алгоритм Флери

Один из алгоритмов поиска эйлерова цикла. Он заключается в следующем: выходим из произвольной вершины графа, соблюдая два правила:
•все рёбра, по которым мы проходим, стираются, так же как и появившиеся в результате изолированные вершины;
•на каждом шаге идём по мосту только тогда, когда нет других возможностей (мост — это такое ребро графа, при стирании которого граф становится несвязным).
Другой алгоритм похож на алгоритм поиска в глубину: начиная с произвольно выбранной стартовой вершины a, строим путь, выбирая каждый раз для дальнейшего продвижения еще не пройденное ребро. Главное отличие от поиска в глубину состоит в том, что как пройденные помечаются именно ребра, а не вершины. Поэтому одна и та же вершина может посещаться несколько раз, но каждое ребро проходится не более одного раза, так что в полученном маршруте ребра не будут повторяться. Вершины пути накапливаются в стеке S. Через некоторое количество шагов неизбежно наступит тупик - все ребра, инцидентные активной (последней посещенной) вершине x, уже пройдены. Так как степени всех вершин графа четны, в этот момент x=a и пройденные ребра образуют цикл, но он может включать не все ребра графа. Для обнаружения еще не пройденных ребер возвращаемся по пройденному пути, перекладывая вершины из стека S в другой стек C , пока не встретим вершину x , которой инцидентно непройденное ребро. Так как граф связен, такая вершина обязательно встретится. Тогда возобновляем движение вперед по не пройденным ребрам, пока не дойдем до нового тупика и т.д. Процесс заканчивается, когда в очередном тупике обнаруживается, что S пуст. В этот момент в стеке C находится последовательность вершин эйлерова цикла.
Алгоритм построения эйлерова цикла:

1. 
   выбрать произвольно вершину a
   
2. 
   aS
   
3. 
   while S=! 0 do
   
4. 
   x=top(S)
   
5. 
   if имеется непройденное ребро (x,y)
   
6. 
   then пометить ребро (x,y) как пройденное
   
7. 
   yS
   
8. 
   else переместить вершину x из S в C
   

Программа представлена в приложении.