Разделы презентаций

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

Содержание

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

Слайды и текст этой презентации

Слайд 128.04.2014
Сильно связные компоненты
Построение и анализ алгоритмов
Лекция 11
Раздел: Алгоритмы на графах
Тема

лекции:
Поиск в глубину в ориентированных графах (напомнить!)
Топологическая сортировка
Сильно связные

компоненты (сл.17…)

1-2: 21.04.2014
3: 28.04.14

28.04.2014Сильно связные компонентыПостроение и анализ алгоритмовЛекция 11Раздел: Алгоритмы на графахТема лекции: Поиск в глубину в ориентированных графах

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

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

Слайд 328.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Сильно связные компонентыПример ПВГ в орграфе1234(1)567(2)(3)(4)(5)(6)(7)8910(8)(9)(10)Стоп!

Слайд 428.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]

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

Слайд 528.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Сильно связные компоненты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)

Слайд 628.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)

(u,v): n(u)n(v) и

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

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

ациклическим ттогда, когда поиск в глубину в G не находит

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

Слайд 828.04.2014
Сильно связные компоненты
Пример 0





1
2
3
4
5





1
2
3
4
5





2
1
3
4
5
(пере)нумерация
(пере)группировка

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

Слайд 928.04.2014
Сильно связные компоненты
Продолжение примера 0 (ПВГ)





1
5
2
4
3





1
2
3
4
5





1
2
3
4
5
ПВГ (поиск в глубину)
1- номер

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

1
2
3
4
5
5
4
3
2
1
Если начать с

красной вершины



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

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

в исходной нумерации;
nv [*] - номера в порядке посещения;
fn

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


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

Слайд 1128.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 [*] –
обратные перестановки
(см. след. слайд)

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

Слайд 1228.04.2014
Сильно связные компоненты
Перестановки


tn [sn [ i ]] := i ,

где i – из исходной нумерации,
sn [tn [

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

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

вершины номерами (n - fn[v] + 1), т.е.

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



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

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

Слайд 1428.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Сильно связные компонентыАлгоритм топологической сортировкиПример 112345671234567abcdefg

Слайд 1528.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Сильно связные компонентыАлгоритм топологической сортировкиПример 2 (другие списки смежности)1764132365425712345671234567

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

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

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

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

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

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

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



Стягивание

ССК




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

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

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

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

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

Слайд 2028.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Сильно связные компоненты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)Каждой ССК графа соответствует дерево в ПВГ-лесу(более точно далее)ПОИСКв глубину

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

ССК орграфа G, а F =(V, T) - глубинный остовный

лес для G. Тогда узлы Vi орграфа G вместе с ребрами из Ei ∩T образуют дерево.

Т.о. «ССК ⇒ дерево», но «дерево ⇒ ССК» - не верно (см.пример) + ещё примеры на след. слайдах


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

Слайд 22

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

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

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


Ещё пример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

Остовный лес из двух

деревьев

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

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


4
5
6
4
2
3
1
3
1
2
5
7
8
9
6
7
8
9
Остовный лес из трех

деревьев

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

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


7
8
9
7
4
2
3
2
3
1
8
1
5
6
9
4
5
6
Остовный лес из двух

деревьев

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

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

деревьев, соответствующих ССК (!)
Алгоритм Тарьяна (Tarjan R.E.) аналогичен ранее рассмотренному

алгоритму нахождение двусвязных компонент.
Мы рассмотрим далее другой алгоритм (Алгоритм Косарайю ).

28.04.2014

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

Алгоритм на базе ПВГ (DFS)Хорошо бы при ПВГ обнаруживать корни деревьев, соответствующих ССК (!)Алгоритм Тарьяна (Tarjan R.E.)

Слайд 28Sambasiva 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

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

Sambasiva Rao Kosaraju is a professor of Computer Science is a professor of Computer Science at Johns

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

те же (!)










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

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

ПВГ орграфа G и вычислить номера вершин в порядке их

использования fn[*].
Сконструировать новый (обращенный) орграф GR , путем обращения всех дуг исходного графа.
Выполнить ПВГ орграфа GR , начиная с вершины, имеющей наибольший номер fn[ ]. Если ПВГ не завершен, то продолжить, начиная с вершины, имеющей наибольший номер fn[ ] среди оставшихся.
Каждое дерево полученного глубинного остовного дерева (леса) орграфа GR является ССК орграфа G.
28.04.2014Сильно связные компонентыАлгоритм Косарайю (S.R.Kosaraju) нахождения ССК орграфа (на основе двух ПВГ)Выполнить ПВГ орграфа 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
копия

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копия

Слайд 3228.04.2014
Сильно связные компоненты
Обращенный граф
(4)
(3)
(2)
(6)
(7)
(10)



(1)
(5)
(8)
(9)



I
II
(10)
(7)
III
(4)
ПВГ в обращенном графе

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

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

алгоритма
Граф ССК GССК орграфа G – ациклический
ССК орграфов G

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

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

графа, то мы найдем компоненту, соответствующую стоку.
Если мы нашли компоненту-сток,

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

28.04.2014

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

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

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

Слайд 3628.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
Топ. сорт. графа

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

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

(S.R.Kosaraju)
O (n +m)



КОНЕЦ ССК

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

Слайд 3828.04.2014
Сильно связные компоненты
КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
КОНЕЦ

ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ

28.04.2014Сильно связные компонентыКОНЕЦ ЛЕКЦИИКОНЕЦ ЛЕКЦИИКОНЕЦ ЛЕКЦИИКОНЕЦ ЛЕКЦИИКОНЕЦ ЛЕКЦИИКОНЕЦ ЛЕКЦИИКОНЕЦ ЛЕКЦИИКОНЕЦ

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

3D моделювання у програмі T-Flex 3D моделювання у програмі T-Flex 286
Миссия и цели организации Миссия и цели организации 208
Наследование.ppt Наследование.ppt 233
Организационные основы управления таможенными органами Организационные основы управления таможенными органами 485
© Finance group 2005-2014 © Finance group 2005-2014 193
Правление Святослава Правление Святослава 470
Сердечно-легочная реанимация Сердечно-легочная реанимация 211
Мария Монтессори (31 августа 1870 г.-6 мая 1952 г.) Мария Монтессори (31 августа 1870 г.-6 мая 1952 г.) 217
МБУ МЦБ МР Уфимский район РБ Михайловская сельская библиотека № 23 МБУ МЦБ МР Уфимский район РБ Михайловская сельская библиотека № 23 165
Социальные утопии Социальные утопии 381
Дистанционное обучение 3 класс МБОУ СОШ 8 Дистанционное обучение 3 класс МБОУ СОШ 8 193
Ларин Борис Александрович Ларин Борис Александрович 268
Коломеец Вениамин Плохушко Виталий Коломеец Вениамин Плохушко Виталий 185
Внешняя политика России 1856-1881 Внешняя политика России 1856-1881 327
ФЕДЕРАЛЬНЫЙ ГОСУДАРСТВЕННЫЙ ПОЖАРНЫЙ НАДЗОР СООБЩАЕТ Отдел надзорной ФЕДЕРАЛЬНЫЙ ГОСУДАРСТВЕННЫЙ ПОЖАРНЫЙ НАДЗОР СООБЩАЕТ Отдел надзорной 221
Бронхиальная астма (БА) является одним из наиболее распространенных заболеваний Бронхиальная астма (БА) является одним из наиболее распространенных заболеваний 280
Система Амосова Система Амосова 218
Проведення зборів та нарад Проведення зборів та нарад 226
Есенин Сергей Александрович Есенин Сергей Александрович 208
Острый живот, дифференциальная диагностика Острый живот, дифференциальная диагностика 407

Обратная связь

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

Email: Нажмите что бы посмотреть 

Что такое TheSlide.ru?

Это сайт презентации, докладов, проектов в PowerPoint. Здесь удобно  хранить и делиться своими презентациями с другими пользователями.

Для правообладателей

Яндекс.Метрика