Реферат: Aлгоритмы на графах

f:=True;

Write(B);

Break

End

else Depth(k);

If f then write('<=', p);

End;

Begin

For i:=1 to n do Visited[i]:=False;

f:=false;

Depth(A);

If not f then write('Пути из ', A, ' в ', B, ' нет')

End;

Begin

write('A= '); readln(A);

write('B= '); readln(B);

A_to_B(A, B)

End.

Эйлеровы циклы .

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

Задача возникла из предложенной Эйлеру головоломки, получившей название "проблема кенигсбергских мостов". Река Прегель, протека ющая через Калининград (прежде город назывался Кенигсбергом), омывает два острова. Берега реки связаны с островами так, как это показано на рисунке. В головоломке требовалось найти маршрут, проходящий по всем участкам суши таким образом, чтобы каждый из мостов был пройден ровно один раз, а начальный и конечный пункты маршрута совпадали.

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

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

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

Доказательство. Необходимость доказана выше. Доказательство достаточности конструктивно - в результате будет получен требуемый алгоритм.

Доказательство ведется индукцией по числу ребер графа. Пусть утверждение доказано для всех m<n. Рассмотрим граф с n ребрами. Выберем произвольную вершину A и начнем строить требуемый путь, вычерчивая (стирая) каждое ребро, по которому проходим, чтобы не пройти его дважды.

Заметим, что, пока мы не вернулись в А, мы всегда можем продолжить путь из текущего узла X по крайней мере на одно ребро. В самом деле, каждый проход через X оставляет четным число ребер в этой вершине. Поэтому, если мы входим в X, остается нечетное число невычеркнутых ребер, из нее выходящих (по крайней мере одно ребро). Пусть мы вернулись в A. Тогда, если все ребра вычеркнуты, теорема доказана. В противном случае оставшиеся ребра распадаются на связанные подграфы, каждый из которых содержит хотя бы одну вершину из уже построенного цикла (поскольку первоначальный граф связанный) и содержит менее n ребер. Пусть, …,– вершины указанных подграфов, через которые проходит построенный путь.

По предположению индукции в каждом из них существует эйлеров цикл. Строим теперь новый путь из A следующим образом:

– идем по старому пути до;

– включаем в него новый путь;