Поиск в глубину в ориентированных графах Топологическая сортировка

лекции:
Поиск в глубину в ориентированных графах
Топологическая сортировка

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

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

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

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

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

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

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

нумерация
Нумерация ПВГ

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

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

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

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

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

fn [*]:
for (i=1; i

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

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

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

j ]] = j , где j – из нумерации топ.сортировки

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

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

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

поиска в глубину
Сильная связность (Strongly Connection)
Определение. Орграф G сильносвязный, если

любые две его вершины достижимы друг из друга.

Определение. Орграф G односторонне связный, если для любой его пары вершин по меньшей мере одна достижима из другой.

Определение. Орграф G слабо связный, если любые две его вершины соединены полупутём.

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

далее)
ПОИСК
в глубину

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

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

Т.о. «ССК ⇒ дерево», но «дерево ⇒ ССК» - не верно (см.пример)

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

ациклический ориентированный граф.
21.04.2014
ПВГ в орграфе

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

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

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

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

E → D
Топ. сорт. графа

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



КОНЕЦ ССК

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