8.11 Пути в бесконтурном графе

Рассмотрим второй случай, для которого известен алгоритм нахождения расстояний от фиксированной вершины за время 0(п²), а именно, случай, когда граф является бесконтурным.

Существует лемма, утверждающая, что в произвольном бесконтурном графе вершины можно перенумеро­вать так, что каждая дуга будет иметь вид (v_t, V ■), где i < j.

Пример такой нумерации приведен на рис. 33.

7 (3) 8

Самый длинный путь в

S=l

бесконтурном графе

2 (2) 3

Рис. 33 Самый длинный путь в бесконтурном графе

Для доказательства рассмотрим алгоритм, реализующий такую перенумерацию.

В качестве исходных данных будем использовать граф (ориентированный, бесконтурный) G = <V, E>, за­данный списками инцидентности СПИСОК[v] , v ∈V. Результатом работы алгоритма для каждой вершины v ∈V является номер N[v] такой, что для произвольной дуги (u, v)∈E выполняется неравенство N[u]<N[v].

1 BEGIN

2. FOR veV DO nz[v] := 0; {nz[v] - число дуг, входящих в v}

3. FOR ueV DO

4 FOR veСПИСОК[u] DO nz[v] := nz[v]+l;

5. СТЕК := 0;

6. FOR veV DO

7 IF nz[v] = 0 THEN СТЕК <= v;

8. num := 0;

9. WHILE СТЕК*0 DO BEGIN

10. u <t= СТЕК;

11. num := num + 1; N[u] := num;

12. FOR veСПИСОК[u] DO BEGIN

13. nz[v] := nz[v]-l;

14. IF nz[v] = 0 THEN СТЕК <= v

15 END

16 END

17 END

Алгоритм основывается на следующем факте: в произвольном бесконтурном графе существует вершина, в которую не заходит ни одна дуга.

Чтобы убедиться в этом, выберем произвольную вершину wi графа, затем некоторую вершину w₂, такую, что w₂ ->■ w_b затем вершину w₃, такую, что w₃ ->■ w₂, и т.д. Через конечное число шагов мы должны дойти до некоторой вершины w_b в которую не заходит ни одна дуга, т.к. в силу бесконтурности графа ни одна вершина в последовательности Wi,w₂,w₃,... не может повторяться.

В нашем алгоритме вершины, в которые не заходит ни одна дуга, накапливаются в стеке. В строке 10 вы­бирается верхний элемент стека и (это мог бы быть произвольный элемент стека) и этой вершине присваивает­ся самый маленький из еще неиспользованных номеров. Таким образом мы гарантируем, что все дуги, выхо­дящие из этой вершины, ведут к вершинам с большими номерами. Затем вершина и вместе с выходящими из нее дугами удаляется из графа. Это приводит к уменьшению на 1 числа дуг, заходящих в каждую вершину v, такую, что и ->■ v. Это число запоминается в nz[v]. Если для какой-либо из вершин v это число сводится к нулю, то v помещается в стек.

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

Мы видим, что каждая дуга анализируется один раз в строке 4 и один раз в строке 12. Таким образом сложность алгоритма есть О(т).

Рассмотрим теперь алгоритм нахождения расстояний от источника до всех вершин в бесконтурном графе. При этом будем считать, что вершины графа уже перенумерованы, так что каждая дуга идет из вершины с меньшим номером в вершину с большим номером. Кроме того, будем считать, что граф задан списками инци­дентности СПИСОКу], ve V.

Результатом работы алгоритма будут являться расстояния от vi до всех вершин графа, а именно D[Vi]=d(v_bVi), i=l,...,n.

1 BEGIN

2. Dtvj] := 0;

3. FOR j := 2 TO n DO D[_Vj] := oo;

4. FOR j := 2 TO n DO

5 FOR Vi£СПИСОК[Vj] DO D[_Vj] := min(D[_Vj], D[vJ + a[v_;,

6 END

Можно доказать (это нетрудно) индукцией по j, что после выполнения цикла 4 для некоторого значения] выполняется равенство

D[vJ=d(v_bVi), /=l,...,j.

Это вытекает из того факта, что все промежуточные вершины кратчайшего пути из vi в Vj имеют номера меньше j.

Сложность алгоритма есть О(т), т.к. каждая дуга (v_t, V ) анализируется в строке 5 ровно один раз.

Последние два алгоритма находят применение, например, в методах управления выполнения некоторого проекта. Эти методы основаны на построении графа, дуги которого соответствуют некоторым задачам, состав­ляющим проект, а их веса указывают на время, необходимое для решения отдельных задач. Кроме того, мы предполагаем, что для произвольных дуг (u, v) и (v, t) этого графа задача, изображаемая дугой (u, v) должна быть закончена перед началом решения задачи, изображаемой дугой (v, t). Легко заметить, что такой граф бу­дет бесконтурным. Нашей целью является нахождение самого длинного пути из вершины s, соответствующей

началу проекта, до вершины t, соответствующей его окончанию (см. путь на рис. 33). Такой путь называется критическим путем. Его длина определяет время, необходимое для реализации всего проекта. Очевидно, эта задача сводится к задаче о кратчайшем пути простым изменением знака каждого веса a[u, v], где u → v , на об­ратный.

Контрольные вопросы

1. Машинное представление графов.

2. Поиск в глубину в графе.

3. Поиск в ширину в графе.

4. Стягивающие деревья.

5. Нахождение стягивающего дерева методом поиска в ширину.

6. Нахождение стягивающего дерева методом поиска в глубину.

7. Фундаментальное множество циклов в графе.

8. Нахождение множества фундаментальных циклов графа.

9. Эйлеровы пути и циклы. Необходимое и достаточное условие существования эйлерова пути.

10. Нахождение эйлерова цикла в графе.

11. Нахождение гамильтоновых циклов графа.

12. Нахождение кратчайших путей в графе.

13. Алгоритм Форда-Беллмана.

14. Алгоритм Дейкстры.