52. Топологическая сортировка. Алгоритм топологической сортировки.

Топологическая сортировка ориентированного ациклического графа G=(V,E) представляет собой такое линейное упорядочение всех его вершин, что если граф G содержит ребро (u,v), то u при таком упорядочении располагается до v (если граф не является ацикличным, такая сортировка невозможна). Топологическую сортировку графа можно рассматривать как такое упорядочение его вершин вдоль горизонтальной линии, что все ребра направлены слева направо.

Мы можем выполнить топологическую сортировку за время θ(V+E), поскольку поиск в глубину выполняется именно за это время, а вставка каждой из |V| вершин в начало связного списка занимает время О.

Алгоритм TopologSort(G)

1. for each vV do

2. num [v] ←0

3. lable [v] ←0

4. end for

5. j←|V|+1

6. i←0

7. for each vV do

8. if num [v]=0 then TOPSORT(V)

9. end for

TOPSORT(V)

1. i←i+1

2. num [i] ←i

3. for each wV, смежные с v do

4. if num[w]=0 then TOPSORT(W)

5. else if lable [w] to then

6. printf “граф содержит цикл”

7. end if

8. end if

53. Двусвязность. Алгоритм определения двусвязности графа.

Если граф не одержит точек разделения, то он называется двусвязным или неразделимым. Максимальный подграф называется двусвязной компонентой или блоком. Для определения точек сочленения – последовательно убирать точки и анализировать, распадается ли граф на несвязные компоненты.

Алгоритм BICONNECTIVITY(G)

1. num ←0, stack ←Ø

2. for each v V do Num[v] ←0, L[v] ←0

3. for each v V do

4. if Num[v]=0 then

Block(v,a)

1. num ← num+1

2. Num[v] ←num

3. L[v] ←num

4. for each w V, смежные c V do

5. if Num[w]=0 then

6. stack ←(v,w)

7. Block(w,v)

8. L[v] ←Min(L[v],L[w])

9. if L[w]≥Num[v] then

10. repeat

11. (v1, w1) ←stack

12. printf “(v1,w2)”

13. until(v1, w1) = (v,w)

14. else if(Num[w] ←Num[v]) and (w≠u) then

15. stack

16. L[v] ←Min(L[v], Num[v])

17. end if

18. end if

19. end if

20. end for

Метка вершины сочленения получает минимальный номер из всех вершин блока.

Вычислительная сложность: О(n+m)

54. Сильно связные компоненты. Алгоритм.

Слабо связные компоненты ориентированного графа легко получить игнорируя положения ребер и алгоритм нахождения связных компонент неориентированного графа.

Алгоритм:

10. Выполнить обход в глубину с сохранением номера окончания обработки узла.

11. Заменить все ребра ориентированного графа на противоположные.

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

13. Деревья леса поиска в глубину получающиеся на предыдущем этапе представляют собой сильно связные компоненты графа.

Используется 2 раза обход в глубину.

Вычислительная сложность: О(n+m) – граф в виде списка смежности, О(n²) – граф в виде матрицы смежности.

55. Эйлеровы пути и циклы. Алгоритм нахождения эйлерова цикла.

Эйлеров путь в графе - произвольный путь, проходящий через каждое ребро графа ровно один раз, т.е. та­кой путь Vj,..., V_m+1, что каждое ребро Е появляется один раз как {Vj,V-₊j} для некоторого i. Если Vj = V_m+1, то такой путь называется эйлеровым циклом.

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

Если в графе нет вершин нечетной степени, то каждый эйлеров путь является эйлеровым циклом.

Пусть G = <V, Е> - связный граф, представленный списками СПИСОК[г], ve V. Алгоритм нахождения эй­лерова цикла в графе построим следующим образом. Используем два стека: СТЕК1 и СТЕК2.

Выбираем произвольную вершину графа Vq и строим последовательно путь из этой вершины. Вершины этого пути помещаем в СТЕК1, а ребра удаляем из графа. Эти действия продолжаем до тех пор, пока оказыва­ется, что путь удлинить, включив в него новую вершину, уже нельзя. Т.е. СПИСОК[у] = 0. Отметим, что тогда должно быть V = Vq , иначе это бы означало, что вершина v - нечетной степени. Таким образом из нашего гра­фа был удален цикл, а вершины этого цикла находятся в стеке СТЕК1. При этом в графе, модифицированном таким образом, степень произвольной вершины остается четной. Вершина V = v₀ переносится теперь из стека СТЕК1 в стек СТЕК2, а процесс повторяется, начиная с вершины, верхней в СТЕК1 (если ее список не пустой). Теперь снова в СТЕК1 помещается некоторый цикл, проходящий через эту вершину, и т.д. Процесс продолжа­ется до тех пор, пока СТЕК1 не станет пустым.

Очевидно, что вершины, помещенные в СТЕК2, образуют некоторый путь, причем вершина v переносится в СТЕК2 только тогда, когда СПИСОК[у] = 0, т.е. когда все ребра, инцидентные этой вершине, представлены в СТЕКеl (парами соседних вершин). Отсюда следует, что по окончании алгоритма СТЕК2 содержит эйлеров цикл.

Алгоритм:

1. BEGIN

2. СТЕК1 := 0; СТЕК2 := 0;

3. v := произвольная вершина графа;

4. СТЕК1 <= v;

5. WHILE СТЕК1 /0DO BEGIN

6. v := top(СТЕКl); {v - верхний элемент СТЕК1}

7. IF СПИСОК[у] Ф 0

8. THEN BEGIN

9. u := первую вершину списка СПИСОК[у];

10. СТЕК1 <= u;

11. СПИСОК^] := СПИСОК^] \ { u }; {удалить ребро}

12. СПИСОКи] := СПИСОКи] \ { v }; {{ v, и } из графа}

13. v :=и;

14. END

15. ELSE { СПИСОК[у] = 0}

16. BEGIN

17. v <= СТЕКl;

18. СТЕК2 <= v;

19. END

20. END

21. END

Мы предполагаем здесь, что каждый из списков инцидентности СПИСОК[у], veV, реализован таким об­разом, что каждая вершина в этом списке содержит указатели на предыдущую и последующую вершины, а вершина и в списке СПИСОК[у] содержит указатель на вершину v в списке СПИСОК[и]. Это дает возможность удалить ребро {v, и} за число шагов, ограниченное константой. Тогда можно оценить вычислительную слож­ность алгоритма следующим образом.

Каждая итерация главного цикла (строка 5) либо помещает вершину в СТЕК1 и удаляет ребро из графа, либо переносит вершину из СТЕК1 в СТЕК2. Т.е. число итераций этого цикла О(т). Число же шагов в каждой итерации ограничено константой. Поэтому можно считать, что общая сложность алгоритма О(т). Алгоритм считается оптимальным.

Пример.

Эйлеров цикл, найденный с помощью нашего алгоритма: 1, 2, 3, 4, 5, 6, 7, 2, 8, 6, 9, 7, 8, 5,3, 1

Buler(G,stack2)

1. Stack1←0; Stack2←0;

2. Stack1←V₀

3. While stack1≠0 do

4. V←Top(Stack1)

5. If Spisok[V]≠0 then

6. w←произв вер spisok[v]

7. Stack1←w

8. Spisok[v] ←Spisok[v]-w

9. Spisok[w] ←Spisok[w]-v

10. Else

11. v←Stack1

12. Stack₀←V

13. End while

14. Return stack2

56. Множество фундаментальных циклов графа. Рекурсивный алгоритм нахождения множества фундаментальных циклов.

Если к стягивающему дереву <V, T> графа G = <V, E> мы добавим произвольную хорду e∈E\T, то воз­никший при этом подграф C = <V, T∪{e}> содержит в точности один цикл. Обозначим этот цикл через C_e. Множество C = {C_e : e∈E \ T} называют фундамен­тальным множеством циклов графа G (относительно стягивающего дерева <V, T>). Название "фундаменталь­ное" связано с тем, что каждый цикл графа G можно достаточно просто получить из циклов множества G.

Нахождение фундаментального множества циклов имеет прикладное значение, например, при анализе электрических цепей. А именно, каждому фундаментальному циклу в графе, соответствующему данной элек­трической цепи, мы можем поставить в соответствие закон Кирхгофа для напряжений: сумма падения напряжений вдоль цикла равна 0. Нахождение фундаментального множества циклов позволяет выделить в математи­ческом описании цепи независимые уравнения.

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

Каждая новая вершина, встречающаяся в процессе поиска, помещается в стек, представленный таблицей СТЕК, и удаляется из стека после использования. Очевидно, что стек всегда содержит последовательность вершин от рассматриваемой в данный момент вершины v к корню.

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

1 PROCEDURE цикл(у);

{переменные d, пит, СТЕК, СПИСОК, WGN - глобальные}

2 BEGIN d := d+1; СТЕК[d] := v; пит := num+1; WGN[ ] := пит;

3 FOR uеСПИСОК[у] DO

4. IF WGN[u] = 0 THEN цикл(г)

5. ELSE IF (и Ф СТЕК[d-l]) and (WGN[v] > WGN[u])

THEN {ребро {v, и} замыкает новый цикл}

6. выписать цикл с вершинами

7. СТЕК[d], СТЕК[d-l], ..., СТЕК[с], где СТЕК[с] = и

8 d := d-1 {использованная вершина v удаляется из стека}

9 END (цикл}; Основная программа:

1 BEGIN

2. FOR veV DO WGN[r] := 0; num := 0; {инициализация}

3. d := 0; СТЕК[0] := 0; {d - число элементов в стеке}

4. FOR reV DO

5 IF WGN[r] = 0 THEN цикл(у)

6 END.

Оценим вычислительную сложность алгоритма. Отметим, что общее число шагов, не считая вычисления циклов, как и во всех алгоритмах, основанных на поиске в глубину, имеет порядок 0(n+m). К этому следует добавить суммарную длину всех циклов. Эта длина не превосходит (m-n+1), что дает общую сложность алго­ритма O(nm), если отбросить вырожденный случай т=0.

56. Алгоритм Воршалла.

G=(V,E)Транзитивное замыкание ориентированного графа с n вершинами можно определить как булиеву матрицу Т размера n*n, в кот. Элемент на пересечении i-той строки и j-того столбца равен 1, если существует ориентированный путь положительной длины из вершины I в вершину j.В противном случае это значение равно 0. А-матрица смежности.

В.предложил строить транзит.замыкание как последовательность матриц размера n*n –элемент матрицы содержит 1, если есть путь из I в j, причем все промежут.верш.не превыш.номера k. Матрица содержит инф. о путях между вершинами гр., в кот. в кач.промежуточной верш.может использоваться только вершина 1. . Если существует путь от I до j и от k до j, то сущ-ет путь от k до i-появл.1.

Алгоритм Wavshell(A[1..n]*A[1..n])

1.R⁽⁰⁾A;

2.for k=1 to n do

3.for i=1 to n do

4.for j=1 to n do

5.R^(k)[I,j]R^(k-1)[I,j] or (R^(k-1)[I,k] and R^(k-1)[k,j]

6.end for

7.end for;

8.end for;

9.retirn R⁽ⁿ⁾

Вычислит.сложность=О(n³)