�ݺ�ߣ

Хакасский государственный университет им. Н.Ф. Катанова

Структуры и алгоритмы обработки данных

Лекция: Графы: сильно связанные
компоненты, остовные деревья.

Николай Гребенщиков, www.grebenshikov.ru

Проблема связности

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

Орграф называется сильно связным, если для каждой па-
ры вершин u, v ∈ V существует путь из v в u и обратно.

1

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

2

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

3

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

FindStrongComp(G)
1 DF S(G) £ вычислим f [u] для каждой вершины u
2 R ← Reverse(G) £ инвертируем все ребра в G
3 SortByF (R) £ сортируем вершины в R по f [u] по убыванию
4 DF S(R)

Результат: каждое DFS-дерево в R яляется сильно связным
компонентом.

4

Алгоритм поиска сильно связных компонетов

5

Доказательство теоремы на семинар:

Процедура F indStrongComp(G) корректно вычисляет сильно
связные компоненты ориентированного графа G.

6

Проблема построения сети

Области возникновения: коммуникационные и дорожные се-
ти.

Дано: множество узлов сети (хосты, города).

Необходимо: построение сети с наименьшим общим весом
ребер (длина сетевых кабелей, длина дорог).

Графовая модель: узлы сети являются узлами графа, E =
V 2, нам известны веса всех ребер.

Результат: свободное дерево.
7

Минимальное дерево Стайнера

8

Минимальное остовное дерево

Остовное дерево - ацикличный подграф G1 = (V 1, E1, w1)
графа G = (V, E, w), где E1 ⊆ E, V 1 = V, w1 = w.

Минимальное остовное дерево - остовное дерево с мини-
мальным весом. w(G) = w(u, w).
(u,w)∈E

9

Примеры остовных деревьев

10

Подход к поиску МОД

Строим дерево путем добавления по одному ребру, и перед
каждой итерацией текущее дерево является подмножеством
некоторого МОД.

GenericMST(G, w)
1 A←0
2 while A не является МОД
3 do Найти безопасное для A ребро (u, v)
4 A ← A {(u, v)}
5 return A

11

Разрез (S, V − S) неориентированного графа G = (V, E) есть
разбиение множества вершин графа.

12

Ребро (u, v) ∈ E пересекает разрез (S, V − S), если один из
его концов находится в S, а другой в V − S.

Разрез согласован с множеством A по ребрам, если ни одно
ребро из A не пересекает разрез.

Ребро, пересекающее разрез, является легким, если оно име-
еит минимальный вес среди всех ребер, пересекающих раз-
рез.

13

Теорема

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

Доказательство на семинар.

14

Алгоритм Крускала

15

Алгоритм Крускала - процедуры

Create − Set(u) - создать множество из одной вершины u.

F ind − Set(u) - найти множество, которому принадлежит вер-
шина u.

U nion(u, v) - объединить множества, которые содержат вер-
шины u и v.

Структуры данных для хранения непересекающихся под-
множеств на семинар.

16

Алгоритм Крускала

17

Анализ алгоритма Крускала

E ≥ V , так как граф связный.

Создание множеств - Θ(V · αV ) = Θ(V logV ) = Θ(ElogE)

Сортировка ребер - Θ(ElogE).

Цикл выполняется E раз.

Поиск и объединие множеств - Θ(αV ) = Θ(logV ) = Θ(logE)

T (G) = Θ(ElogE)

18

Алгоритм Прима: идея

19

Алгоритм Прима

20

Алгоритм Прима: пример

21

Алгоритм Прима: анализ

T (G) = V + V logV + (logV + deg(u)logV ) = V + V logV + (V +
u∈V
2E)logV = Θ(ElogV )

22

На семинар

Алгоритм Барувки (Baruvka)

23

Список литературы

• David M. Mount, The Lecture notes: Design and Analysis
of Computer Algorithms. [Электронный ресурс] / Dept. of
Computer Science, University of Maryland, 2004. - Режим
доступа: http://www.cs.umd.edu/ mount/451/Lects/451lects.pdf
. - сс.39-49

• Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгорит-
мы: построение и анализ, 2-е издание. - М. : Издатель-
ский дом “Вильямс”, 2007. сс.644-662.

24

�ݺ�ߣ

Лекция №13. Графы: сильно связные компоненты и остовные деревья. Предмет "Структуры и алгоритмы обработки данных"

Recommended

More Related Content

What's hot (20)

Similar to Лекция №13. Графы: сильно связные компоненты и остовные деревья. Предмет "Структуры и алгоритмы обработки данных" (20)

More from Nikolay Grebenshikov (12)

Лекция №13. Графы: сильно связные компоненты и остовные деревья. Предмет "Структуры и алгоритмы обработки данных"