Особенности поиска в глубину (ПВГ) в ориентированных графах

Сентябрь 3, 2022

Главная
Алгебра
Особенности поиска в глубину (ПВГ) в ориентированных графах

Содержание

2. 28.04.2014 Сильно связные компоненты Особенности поиска в глубину (ПВГ) в ориентированных графах
3. 28.04.2014 Сильно связные компоненты Пример ПВГ в орграфе 1 2 3 4 (1) 5 6 7
4. 28.04.2014 Сильно связные компоненты Пример ПВГ в орграфе 1 2 3 4 (1) 5 6 7
5. 28.04.2014 Сильно связные компоненты 1 2 3 4 (1) 5 6 7 (2) (3) (4) (5)
6. 28.04.2014 Сильно связные компоненты 1 2 3 4 5 6 7 (1) (5) (4) (3) (2)
7. 28.04.2014 Сильно связные компоненты Топологическая сортировка Ациклический (бесконтурный) орграф Лемма 1. Орграф G является ациклическим ттогда,
8. 28.04.2014 Сильно связные компоненты Пример 0 1 2 3 4 5 1 2 3 4 5
9. 28.04.2014 Сильно связные компоненты Продолжение примера 0 (ПВГ) 1 5 2 4 3 1 2 3
10. 28.04.2014 Сильно связные компоненты Продолжение примера 0 (ПВГ) v [*] – имена вершин в исходной нумерации;
11. 28.04.2014 Сильно связные компоненты Продолжение примера 0 (ПВГ) 1) Получение sn [*] из fn [*]: for
12. 28.04.2014 Сильно связные компоненты Перестановки tn [sn [ i ]] := i , где i –
13. 28.04.2014 Сильно связные компоненты Выполнить ПВГ в орграфе G, заполнив массив fn[*]. Пронумеровать вершины номерами (n
14. 28.04.2014 Сильно связные компоненты Алгоритм топологической сортировки Пример 1 1 2 3 4 5 6 7
15. 28.04.2014 Сильно связные компоненты Алгоритм топологической сортировки Пример 2 (другие списки смежности) 1 7 6 4
16. 28.04.2014 Сильно связные компоненты Продолжение на следующей лекции! (28 апреля)
17. Нахождение сильно связных компонент графа (ССК) 28.04.2014 Сильно связные компоненты Алгоритм на основе поиска в глубину
18. 28.04.2014 Сильно связные компоненты Сильно связные компоненты (Strongly Connected Components) Сильно связная компонента – максимальный сильно
19. ? При стягивании каждой сильно связной компоненты в одну вершину получается ациклический ориентированный граф. (Почему?) 28.04.2014
20. 28.04.2014 Сильно связные компоненты 1 2 3 4 (1) 5 6 7 (2) (3) (4) (5)
21. 28.04.2014 Сильно связные компоненты Соответствие «ССК – дерево» Утверждение Пусть Gi =(Vi, Ei) – ССК орграфа
22. 28.04.2014 Сильно связные компоненты
23. Ещё пример 28.04.2014 Сильно связные компоненты
24. Вариант 1 (начало с «a») 28.04.2014 Сильно связные компоненты 1 2 3 1 4 5 6
25. Вариант 2 (начать с «b») 28.04.2014 Сильно связные компоненты 4 5 6 4 2 3 1
26. Вариант 3 (начать с «с») 28.04.2014 Сильно связные компоненты 7 8 9 7 4 2 3
27. Алгоритм на базе ПВГ (DFS) Хорошо бы при ПВГ обнаруживать корни деревьев, соответствующих ССК (!) Алгоритм
28. Sambasiva Rao Kosaraju is a professor of Computer Science is a professor of Computer Science at
29. 28.04.2014 Сильно связные компоненты Обращение орграфа (понадобится далее), при этом ССК – те же (!)
30. 28.04.2014 Сильно связные компоненты Алгоритм Косарайю (S.R.Kosaraju) нахождения ССК орграфа (на основе двух ПВГ) Выполнить ПВГ
31. 28.04.2014 Сильно связные компоненты 1 2 3 4 (1) 5 6 7 (2) (3) (4) (5)
32. 28.04.2014 Сильно связные компоненты Обращенный граф (4) (3) (2) (6) (7) (10) (1) (5) (8) (9)
33. 28.04.2014 Сильно связные компоненты Основные факты (утверждения), на которые опирается доказательство правильности алгоритма Граф ССК GССК
34. Иначе говоря Если начать с вершины, которая лежит в стоке стянутого графа, то мы найдем компоненту,
35. 28.04.2014 Сильно связные компоненты Пример (пояснение к утверждениям) 5/3 6/2 7/1 8/6 9/5 10/4 4/8 3/9
36. 28.04.2014 Сильно связные компоненты Пример (продолжение) 13-3 15-2 14-1 10-6 12-5 11-4 9-8 7-9 3-14 2-13
37. 28.04.2014 Сильно связные компоненты Сложность алгоритмов нахождения ССК Алгоритм Тарьяна (Tarjan R.E.) Алгоритм Косарайю (S.R.Kosaraju) O
39. Скачать презентацию

Слайд 2

28.04.2014
Сильно связные компоненты
Особенности поиска в глубину (ПВГ) в ориентированных графах

Слайд 3

28.04.2014
Сильно связные компоненты
Пример ПВГ в орграфе
1
2
3
4
(1)
5
6
7
(2)
(3)
(4)
(5)
(6)
(7)
8
9
10
(8)
(9)
(10)
Стоп!

Слайд 4

28.04.2014
Сильно связные компоненты
Пример ПВГ в орграфе
1
2
3
4
(1)
5
6
7
(2)
(3)
(4)
(5)
(6)
(7)
8
9
10
(8)
(9)
(10)
Стоп!
Древесное ребро – от отца к

сыну в глубинном остовном дереве (ГОД)
Направленное вперед (прямое) ребро – от предка к потомку в ГОД
Обратное ребро – от потомка к предку в ГОД
Поперечное ребро – не связывает предка и потомка

1 – номер при ПВГ: NumVert(v) или n(v)
(1) – номер в порядке использования при ПВГ: fn(v) [finishing]

Слайд 5

28.04.2014
Сильно связные компоненты
1
2
3
4
(1)
5
6
7
(2)
(3)
(4)
(5)
(6)
(7)
8
9
10
(8)
(9)
(10)
1
2
3
4
5
6
7
(1)
(5)
(4)
(3)
(2)
(6)
(7)
8
9
10
(8)
(9)
(10)

Слайд 6

28.04.2014
Сильно связные компоненты
1
2
3
4
5
6
7
(1)
(5)
(4)
(3)
(2)
(6)
(7)
8
9
10
(8)
(9)
(10)
Направленное вперед ребро(u,v): n(u)в момент рассмотрения n(v)≠0
Древесное ребро (u,v):

n(u)в момент рассмотрения n(v)=0

Обратное ребро (u, v): n(u)>n(v) и fn(v)=0
Поперечное ребро (u, v): n(u)>n(v) и fn(v)≠0

Слайд 7

28.04.2014
Сильно связные компоненты
Топологическая сортировка
Ациклический (бесконтурный) орграф
Лемма 1. Орграф G является ациклическим

ттогда, когда поиск в глубину в G не находит обратных ребер.
Лемма 2. В произвольном ациклическом орграфе G=(V,E) вершины могут быть пронумерованы так, что каждая дуга будет иметь вид (vi,vj), где iПримеры:
Сетевой график работ.
Связи между дисциплинами учебного плана (пререквизиты и постреквизиты).
Информационный граф программы (алгоритма).

Слайд 8

28.04.2014
Сильно связные компоненты
Пример 0
1
2
3
4
5
1
2
3
4
5
2
1
3
4
5
(пере)нумерация
(пере)группировка

Слайд 9

28.04.2014
Сильно связные компоненты
Продолжение примера 0 (ПВГ)
1
5
2
4
3
1
2
3
4
5
1
2
3
4
5
ПВГ (поиск в глубину)
1- номер в

порядке посещения
4 – номер в порядке использования

(пере)группировка

Если начать с красной вершины

Слайд 10

28.04.2014
Сильно связные компоненты
Продолжение примера 0 (ПВГ)
v [*] – имена вершин в

исходной нумерации;
nv [*] - номера в порядке посещения;
fn [*] - номера в порядке использования;
sn [*] – номера в порядке топ.сортировки, т.е. sn [i] – новый номер вершины с исходным номером i;
tn [i] – исходный номер вершины с номером i в порядке топ.сортировки

Слайд 11

28.04.2014
Сильно связные компоненты
Продолжение примера 0 (ПВГ)
1) Получение sn [*] из fn

[*]:
for i := 1..n do sn [ i ] := n - fn [ i ] + 1;
2) Получение tn [*] из sn [*]:
for i := 1..n do tn [sn [ i ]] := i;
--------------------------------------------------
Или получение tn [*] сразу из fn [*]:
for i := 1..n do tn [n - fn [ i ] + 1] := i ;

Оказывается, что
sn [*] и tn [*] –
обратные перестановки
(см. след. слайд)

Слайд 12

28.04.2014
Сильно связные компоненты
Перестановки
tn [sn [ i ]] := i , где

i – из исходной нумерации,
sn [tn [ j ]] := j , где j – из нумерации топ.сортировки

Слайд 13

28.04.2014
Сильно связные компоненты
Выполнить ПВГ в орграфе G, заполнив массив fn[*].
Пронумеровать вершины

номерами (n - fn[v] + 1), т.е. заполнить sn [*] – вектор (последовательность) новых номеров в порядке топологической сортировки (sn [ i ] – новый номер вершины с исходным номером i).
Перегруппировать вершины, т.е. заполнить tn [*] – вектор старых номеров в новом порядке (tn [ i ] – исходный номер вершины с номером i в порядке топологической сортировки)

Алгоритм топологической сортировки

Слайд 14

28.04.2014
Сильно связные компоненты
Алгоритм топологической сортировки
Пример 1
1
2
3
4
5
6
7
1
2
3
4
5
6
7
a
b
c
d
e
f
g

Слайд 15

28.04.2014
Сильно связные компоненты
Алгоритм топологической сортировки
Пример 2 (другие списки смежности)
1
7
6
4
1
3
2
3
6
5
4
2
5
7
1
2
3
4
5
6
7
1
2
3
4
5
6
7

Слайд 16

28.04.2014
Сильно связные компоненты
Продолжение на следующей лекции! (28 апреля)

Слайд 17

Нахождение сильно связных компонент графа (ССК)
28.04.2014
Сильно связные компоненты
Алгоритм на основе поиска

в глубину
Сильная связность (Strongly Connection)

Слайд 18

28.04.2014
Сильно связные компоненты
Сильно связные компоненты (Strongly Connected Components)
Сильно связная компонента –

максимальный сильно связный подграф
Сильно связная компонента = ССК

Стягивание ССК

Слайд 19

?
При стягивании каждой сильно связной компоненты в одну вершину получается ациклический

ориентированный граф.
(Почему?)

28.04.2014

Сильно связные компоненты

Слайд 20

28.04.2014
Сильно связные компоненты
1
2
3
4
(1)
5
6
7
(2)
(3)
(4)
(5)
(6)
(7)
8
9
10
(8)
(9)
(10)
1
2
3
4
5
6
7
(1)
(5)
(4)
(3)
(2)
(6)
(7)
8
9
10
(8)
(9)
(10)
Каждой ССК графа соответствует дерево в ПВГ-лесу
(более точно далее)
ПОИСК
в

глубину

Слайд 21

28.04.2014
Сильно связные компоненты
Соответствие «ССК – дерево»
Утверждение
Пусть Gi =(Vi, Ei) – ССК

орграфа G, а F =(V, T) - глубинный остовный лес для G. Тогда узлы Vi орграфа G вместе с ребрами из Ei ∩T образуют дерево.
Т.о. «ССК ⇒ дерево», но «дерево ⇒ ССК» - не верно (см.пример) + ещё примеры на след. слайдах

Слайд 22

28.04.2014
Сильно связные компоненты

Слайд 23

Ещё пример
28.04.2014
Сильно связные компоненты

Слайд 24

Вариант 1 (начало с «a»)
28.04.2014
Сильно связные компоненты
1
2
3
1
4
5
6
2
3
4
5
7
8
9
6
7
8
9
Остовный лес из двух деревьев

Слайд 25

Вариант 2 (начать с «b»)
28.04.2014
Сильно связные компоненты
4
5
6
4
2
3
1
3
1
2
5
7
8
9
6
7
8
9
Остовный лес из трех деревьев

Слайд 26

Вариант 3 (начать с «с»)
28.04.2014
Сильно связные компоненты
7
8
9
7
4
2
3
2
3
1
8
1
5
6
9
4
5
6
Остовный лес из двух деревьев

Слайд 27

Алгоритм на базе ПВГ (DFS)
Хорошо бы при ПВГ обнаруживать корни деревьев,

соответствующих ССК (!)
Алгоритм Тарьяна (Tarjan R.E.) аналогичен ранее рассмотренному алгоритму нахождение двусвязных компонент.
Мы рассмотрим далее другой алгоритм (Алгоритм Косарайю ).

28.04.2014

Сильно связные компоненты

Слайд 28

Sambasiva Rao Kosaraju is a professor of Computer Science is a

professor of Computer Science at Johns Hopkins University is a professor of Computer Science at Johns Hopkins University, and division director for Computing & Communication Foundations at the National Science Foundation is a professor of Computer Science at Johns Hopkins University, and division director for Computing & Communication Foundations at the National Science Foundation.He has done extensive work in the design and analysis of parallel and sequential algorithms. (From Wikipedia, the free encyclopedia)

28.04.2014

Сильно связные компоненты

Слайд 29

28.04.2014
Сильно связные компоненты
Обращение орграфа (понадобится далее), при этом ССК – те же

(!)

Слайд 30

28.04.2014
Сильно связные компоненты
Алгоритм Косарайю (S.R.Kosaraju) нахождения ССК орграфа (на основе двух ПВГ)
Выполнить ПВГ

орграфа G и вычислить номера вершин в порядке их использования fn[*].
Сконструировать новый (обращенный) орграф GR , путем обращения всех дуг исходного графа.
Выполнить ПВГ орграфа GR , начиная с вершины, имеющей наибольший номер fn[ ]. Если ПВГ не завершен, то продолжить, начиная с вершины, имеющей наибольший номер fn[ ] среди оставшихся.
Каждое дерево полученного глубинного остовного дерева (леса) орграфа GR является ССК орграфа G.

Слайд 31

28.04.2014
Сильно связные компоненты
1
2
3
4
(1)
5
6
7
(2)
(3)
(4)
(5)
(6)
(7)
8
9
10
(8)
(9)
(10)
1
2
3
4
5
6
7
(1)
(5)
(4)
(3)
(2)
(6)
(7)
8
9
10
(8)
(9)
(10)
abde
hij
cfg
копия

Слайд 32

28.04.2014
Сильно связные компоненты
Обращенный граф
(4)
(3)
(2)
(6)
(7)
(10)
(1)
(5)
(8)
(9)
I
II
(10)
(7)
III
(4)
ПВГ в обращенном графе

Слайд 33

28.04.2014
Сильно связные компоненты
Основные факты (утверждения), на которые опирается доказательство правильности алгоритма

Граф ССК GССК орграфа G – ациклический
ССК орграфов G и GR совпадают (как множества вершин)
При втором ПВГ граф ССК (GR)ССК орграфа GR проходится в порядке, обратном топологической сортировке

Слайд 34

Иначе говоря
Если начать с вершины, которая лежит в стоке стянутого графа,

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

28.04.2014

Сильно связные компоненты

Слайд 35

28.04.2014
Сильно связные компоненты
Пример (пояснение к утверждениям)
5/3
6/2
7/1
8/6
9/5
10/4
4/8
3/9
2/14
12/13
13/12
1/15
G
ПВГ в G
GССК
Топ. сорт. графа

Слайд 36

28.04.2014
Сильно связные компоненты
Пример (продолжение)
13-3
15-2
14-1
10-6
12-5
11-4
9-8
7-9
3-14
2-13
4-12
1-15
GR
ПВГ в GR
(GR)ССК
A→ C → B → E

→ D

Топ. сорт. графа

Слайд 37

28.04.2014
Сильно связные компоненты
Сложность алгоритмов нахождения ССК
Алгоритм Тарьяна (Tarjan R.E.)
Алгоритм Косарайю (S.R.Kosaraju)
O

(n +m)
КОНЕЦ ССК

Особенности поиска в глубину (ПВГ) в ориентированных графах

Содержание

28.04.2014Сильно связные компонентыОсобенности поиска в глубину (ПВГ) в ориентированных графах

28.04.2014Сильно связные компонентыПример ПВГ в орграфе1234(1)567(2)(3)(4)(5)(6)(7)8910(8)(9)(10)Стоп!

28.04.2014Сильно связные компонентыПример ПВГ в орграфе1234(1)567(2)(3)(4)(5)(6)(7)8910(8)(9)(10)Стоп!Древесное ребро – от отца к

28.04.2014Сильно связные компоненты1234(1)567(2)(3)(4)(5)(6)(7)8910(8)(9)(10)1234567(1)(5)(4)(3)(2)(6)(7)8910(8)(9)(10)

28.04.2014Сильно связные компоненты1234567(1)(5)(4)(3)(2)(6)(7)8910(8)(9)(10)Направленное вперед ребро(u,v): n(u)в момент рассмотрения n(v)≠0Древесное ребро (u,v):

28.04.2014Сильно связные компонентыТопологическая сортировкаАциклический (бесконтурный) орграфЛемма 1. Орграф G является ациклическим

28.04.2014Сильно связные компонентыПример 0123451234521345(пере)нумерация(пере)группировка

28.04.2014Сильно связные компонентыПродолжение примера 0 (ПВГ)152431234512345ПВГ (поиск в глубину)1- номер в

28.04.2014Сильно связные компонентыПродолжение примера 0 (ПВГ)v [*] – имена вершин в

28.04.2014Сильно связные компонентыПродолжение примера 0 (ПВГ)1) Получение sn [*] из fn

28.04.2014Сильно связные компонентыПерестановкиtn [sn [ i ]] := i , где

28.04.2014Сильно связные компонентыВыполнить ПВГ в орграфе G, заполнив массив fn[*].Пронумеровать вершины

28.04.2014Сильно связные компонентыАлгоритм топологической сортировкиПример 112345671234567abcdefg

28.04.2014Сильно связные компонентыАлгоритм топологической сортировкиПример 2 (другие списки смежности)1764132365425712345671234567

28.04.2014Сильно связные компонентыПродолжение на следующей лекции! (28 апреля)

Нахождение сильно связных компонент графа (ССК)28.04.2014Сильно связные компонентыАлгоритм на основе поиска

28.04.2014Сильно связные компонентыСильно связные компоненты (Strongly Connected Components)Сильно связная компонента –

?При стягивании каждой сильно связной компоненты в одну вершину получается ациклический

28.04.2014Сильно связные компоненты1234(1)567(2)(3)(4)(5)(6)(7)8910(8)(9)(10)1234567(1)(5)(4)(3)(2)(6)(7)8910(8)(9)(10)Каждой ССК графа соответствует дерево в ПВГ-лесу(более точно далее)ПОИСКв

28.04.2014Сильно связные компонентыСоответствие «ССК – дерево»УтверждениеПусть Gi =(Vi, Ei) – ССК

28.04.2014Сильно связные компоненты

Ещё пример28.04.2014Сильно связные компоненты

Вариант 1 (начало с «a»)28.04.2014Сильно связные компоненты123145623457896789Остовный лес из двух деревьев

Вариант 2 (начать с «b»)28.04.2014Сильно связные компоненты456423131257896789Остовный лес из трех деревьев

Вариант 3 (начать с «с»)28.04.2014Сильно связные компоненты789742323181569456Остовный лес из двух деревьев

Алгоритм на базе ПВГ (DFS)Хорошо бы при ПВГ обнаруживать корни деревьев,

Sambasiva Rao Kosaraju is a professor of Computer Science is a

28.04.2014Сильно связные компонентыОбращение орграфа (понадобится далее), при этом ССК – те же

28.04.2014Сильно связные компонентыАлгоритм Косарайю (S.R.Kosaraju) нахождения ССК орграфа (на основе двух ПВГ)Выполнить ПВГ

28.04.2014Сильно связные компоненты1234(1)567(2)(3)(4)(5)(6)(7)8910(8)(9)(10)1234567(1)(5)(4)(3)(2)(6)(7)8910(8)(9)(10)abdehijcfgкопия

28.04.2014Сильно связные компонентыОбращенный граф(4)(3)(2)(6)(7)(10)(1)(5)(8)(9)III(10)(7)III(4)ПВГ в обращенном графе

28.04.2014Сильно связные компонентыОсновные факты (утверждения), на которые опирается доказательство правильности алгоритма

Иначе говоряЕсли начать с вершины, которая лежит в стоке стянутого графа,

28.04.2014Сильно связные компонентыПример (пояснение к утверждениям)5/36/27/18/69/510/44/83/92/1412/1313/121/15GПВГ в GGССКТоп. сорт. графа

28.04.2014Сильно связные компонентыПример (продолжение)13-315-214-110-612-511-49-87-93-142-134-121-15GRПВГ в GR(GR)ССКA→ C → B → E

28.04.2014Сильно связные компонентыСложность алгоритмов нахождения ССКАлгоритм Тарьяна (Tarjan R.E.)Алгоритм Косарайю (S.R.Kosaraju) O

Похожие презентации

28.04.2014
Сильно связные компоненты
Особенности поиска в глубину (ПВГ) в ориентированных графах

28.04.2014
Сильно связные компоненты
Пример ПВГ в орграфе
1
2
3
4
(1)
5
6
7
(2)
(3)
(4)
(5)
(6)
(7)
8
9
10
(8)
(9)
(10)
Стоп!

28.04.2014
Сильно связные компоненты
Пример ПВГ в орграфе
1
2
3
4
(1)
5
6
7
(2)
(3)
(4)
(5)
(6)
(7)
8
9
10
(8)
(9)
(10)
Стоп!
Древесное ребро – от отца к

28.04.2014
Сильно связные компоненты
1
2
3
4
(1)
5
6
7
(2)
(3)
(4)
(5)
(6)
(7)
8
9
10
(8)
(9)
(10)
1
2
3
4
5
6
7
(1)
(5)
(4)
(3)
(2)
(6)
(7)
8
9
10
(8)
(9)
(10)

28.04.2014
Сильно связные компоненты
1
2
3
4
5
6
7
(1)
(5)
(4)
(3)
(2)
(6)
(7)
8
9
10
(8)
(9)
(10)
Направленное вперед ребро(u,v): n(u)в момент рассмотрения n(v)≠0
Древесное ребро (u,v):

28.04.2014
Сильно связные компоненты
Топологическая сортировка
Ациклический (бесконтурный) орграф
Лемма 1. Орграф G является ациклическим

28.04.2014
Сильно связные компоненты
Пример 0
1
2
3
4
5
1
2
3
4
5
2
1
3
4
5
(пере)нумерация
(пере)группировка

28.04.2014
Сильно связные компоненты
Продолжение примера 0 (ПВГ)
1
5
2
4
3
1
2
3
4
5
1
2
3
4
5
ПВГ (поиск в глубину)
1- номер в

28.04.2014
Сильно связные компоненты
Продолжение примера 0 (ПВГ)
v [*] – имена вершин в

28.04.2014
Сильно связные компоненты
Продолжение примера 0 (ПВГ)
1) Получение sn [*] из fn

28.04.2014
Сильно связные компоненты
Перестановки
tn [sn [ i ]] := i , где

28.04.2014
Сильно связные компоненты
Выполнить ПВГ в орграфе G, заполнив массив fn[*].
Пронумеровать вершины

28.04.2014
Сильно связные компоненты
Алгоритм топологической сортировки
Пример 1
1
2
3
4
5
6
7
1
2
3
4
5
6
7
a
b
c
d
e
f
g

28.04.2014
Сильно связные компоненты
Алгоритм топологической сортировки
Пример 2 (другие списки смежности)
1
7
6
4
1
3
2
3
6
5
4
2
5
7
1
2
3
4
5
6
7
1
2
3
4
5
6
7

28.04.2014
Сильно связные компоненты
Продолжение на следующей лекции! (28 апреля)

Нахождение сильно связных компонент графа (ССК)
28.04.2014
Сильно связные компоненты
Алгоритм на основе поиска

28.04.2014
Сильно связные компоненты
Сильно связные компоненты (Strongly Connected Components)
Сильно связная компонента –

?
При стягивании каждой сильно связной компоненты в одну вершину получается ациклический

28.04.2014
Сильно связные компоненты
Соответствие «ССК – дерево»
Утверждение
Пусть Gi =(Vi, Ei) – ССК

28.04.2014
Сильно связные компоненты

Ещё пример
28.04.2014
Сильно связные компоненты

Вариант 1 (начало с «a»)
28.04.2014
Сильно связные компоненты
1
2
3
1
4
5
6
2
3
4
5
7
8
9
6
7
8
9
Остовный лес из двух деревьев

Вариант 2 (начать с «b»)
28.04.2014
Сильно связные компоненты
4
5
6
4
2
3
1
3
1
2
5
7
8
9
6
7
8
9
Остовный лес из трех деревьев

Вариант 3 (начать с «с»)
28.04.2014
Сильно связные компоненты
7
8
9
7
4
2
3
2
3
1
8
1
5
6
9
4
5
6
Остовный лес из двух деревьев

Алгоритм на базе ПВГ (DFS)
Хорошо бы при ПВГ обнаруживать корни деревьев,

28.04.2014
Сильно связные компоненты
Обращение орграфа (понадобится далее), при этом ССК – те же

28.04.2014
Сильно связные компоненты
Алгоритм Косарайю (S.R.Kosaraju) нахождения ССК орграфа (на основе двух ПВГ)
Выполнить ПВГ

28.04.2014
Сильно связные компоненты
1
2
3
4
(1)
5
6
7
(2)
(3)
(4)
(5)
(6)
(7)
8
9
10
(8)
(9)
(10)
1
2
3
4
5
6
7
(1)
(5)
(4)
(3)
(2)
(6)
(7)
8
9
10
(8)
(9)
(10)
abde
hij
cfg
копия

28.04.2014
Сильно связные компоненты
Обращенный граф
(4)
(3)
(2)
(6)
(7)
(10)
(1)
(5)
(8)
(9)
I
II
(10)
(7)
III
(4)
ПВГ в обращенном графе

28.04.2014
Сильно связные компоненты
Основные факты (утверждения), на которые опирается доказательство правильности алгоритма

Иначе говоря
Если начать с вершины, которая лежит в стоке стянутого графа,

28.04.2014
Сильно связные компоненты
Пример (пояснение к утверждениям)
5/3
6/2
7/1
8/6
9/5
10/4
4/8
3/9
2/14
12/13
13/12
1/15
G
ПВГ в G
GССК
Топ. сорт. графа

28.04.2014
Сильно связные компоненты
Пример (продолжение)
13-3
15-2
14-1
10-6
12-5
11-4
9-8
7-9
3-14
2-13
4-12
1-15
GR
ПВГ в GR
(GR)ССК
A→ C → B → E

28.04.2014
Сильно связные компоненты
Сложность алгоритмов нахождения ССК
Алгоритм Тарьяна (Tarjan R.E.)
Алгоритм Косарайю (S.R.Kosaraju)
O