Лекция 7. Алгоритм А. Минимальные остовы. Потоки в сетях

Август 20, 2022

Главная
Информатика
Лекция 7. Алгоритм А. Минимальные остовы. Потоки в сетях

Содержание

2. Ограничение на эвристики Допустимость h(v) -- для любой вершины эвристика не превосходит реальное кратчайшее расстояние Монотонность
3. Остовные деревья
4. Остовное дерево Ациклический связный подграф, включающий все вершины графа. Как найти?
5. Минимальное остовное дерево Остовное дерево, обладающее минимальным суммарным весом рёбер
6. Лемма о безопасном ребре Пусть G’ -- подграф миностова G Ребро не из G’ -- безопасное,
7. Лемма о безопасном ребре Рассмотрим граф G -- взвешенный неориентированный. G’ -- подграф его миноста, --
8. Алгоритм Прима Похож на Дейкстру Пытаемся построить миностов, начиная с любой вершины. Когда есть несколько вершин
9. Асимптотика алгоритма Прима
10. Алгоритм Крускала Отсортируем все рёбра в порядке возрастания и будем последовательно добавлять в остов. Если ребро
11. Система непересекающихся множеств Каждое множество -- дерево, корень -- его “представитель”. В каждой вершине -- ссылка
12. Эвристики СНМ Объединение по рангу. Подвешиваем дерево с меньшей высотой к дереву с большей. Чтобы не
13. Асимптотика алгоритма Крускала Сортировка рёбер -- O(ElogE) СНМ -- O(E*alpha(V)) Общая асимптотика -- O(ElogE)
14. Алгоритм Борувки Каждая вершина графа -- дерево Для каждого дерева найдём минимальноe инцидентное ему ребро. Добавим
15. Алгоритм Борувки. Асимптотика На каждом шаге количество деревьев сокращается как минимум вдвое. То есть шагов --
16. Максимальный поток в сети. RMQ & LCA
17. Определение сети и потока Сеть -- орграф, с:E->R+, с(e) -- пропускная способность. В сети есть исток
18. Разрез. Поток через разрез Разрез -- знаем Пропускная способность разреза -- сумма всех рёбер, пересекающих разрез
19. Лемма о величине потока f(S,T) = |f|
20. Лемма о минимальном разрезе Если f(S,T) = c(S,T), то поток f максимален, а разрез -- минимален
21. Ещё определения
22. Теорема Форда-Фалкерсона Если f -- поток в сети G = (V,E), то следующие утверждения эквивалентны: Поток
23. Алгоритм Форда-Фалкерсона Положим f(u,v) = 0 Далее поток увеличивается итеративно через поиск увеличивающего пути Поиск можно
24. Алгоритм Эдмонса-Карпа Улучшение алгоритма Форда-Фалкерсона, в качестве дополняющего пути берём кратчайший по рёбрам Асимптотика O(VE^2) Найти
25. Алгоритм Диница Слоистая сеть Определим для каждой вершины v длину кратчайшего s->v. В слоистую сеть включаем
26. Поиск блокирующего потока Можно просто искать все пути s->t по одному и наполнять(по крайней мере одно
27. Алгоритм Диница Инициализируем f(u,v) = 0 Построим вспомогательную сеть для остаточной данного графа. Если пустая --
28. Паросочетания Паросочетание -- набор попарно несмежных рёбер в двудольном графе. Максимальное паросочетание -- паросочетание с наибольшим
29. Теорема Бержа Паросочетание максимально тогда и только тогда, когда не существует увеличивающих относительно него цепей. Пусть
30. Теорема Бержа Пусть парсоч M не содержит ув. пути, но есть парсоч M’, который больше чем
31. Алгоритм Куна поиска паросочетаний Возьмём пустое паросочетание, пока в графе находим увеличивающую цепь -- выполняем “чередование”
32. Алгоритм Куна Возьмём пустое паросочетание Пока удаётся найти увеличивающую цепь -- выполняем чередование Массив matching[v] --
34. Скачать презентацию

Слайд 2

Ограничение на эвристики
Допустимость h(v) -- для любой вершины эвристика не превосходит

реальное кратчайшее расстояние
Монотонность h(v) -- для любых двух вершин на пути разница эвристик не превышает реального расстояния между ними
Монотонность -> допустимость
Монотонность -> На любом пути f(v) не убывает

Слайд 3

Остовные деревья

Слайд 4

Остовное дерево
Ациклический связный подграф, включающий все вершины графа.
Как найти?

Слайд 5

Минимальное остовное дерево
Остовное дерево, обладающее минимальным суммарным весом рёбер

Слайд 6

Лемма о безопасном ребре
Пусть G’ -- подграф миностова G
Ребро не из

G’ -- безопасное, если при добавлении его в G’ он не прекратит быть подграфом миностова
Разрез -- разделение множества вершин на S и T,
Ребро пересекает разрез , если один его конец принадлежит S, а второй -- T

Слайд 7

Лемма о безопасном ребре
Рассмотрим граф G -- взвешенный неориентированный. G’ --

подграф его миноста, -- разрез G такой, что его не пересекает ни одно ребро G’. Тогда ребро минимального веса, пересекающее разрез -- безопасное.

Слайд 8

Алгоритм Прима
Похож на Дейкстру
Пытаемся построить миностов, начиная с любой вершины. Когда

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

Слайд 9

Асимптотика алгоритма Прима

Слайд 10

Алгоритм Крускала
Отсортируем все рёбра в порядке возрастания и будем последовательно добавлять

в остов.
Если ребро соединяет вершины из разных компонент связности текущего остова -- берём, иначе -- не берём

Слайд 11

Система непересекающихся множеств
Каждое множество -- дерево, корень -- его “представитель”. В

каждой вершине -- ссылка на родителя
Объединение -- подвесим корень одного к корню другого. Понять, в каком множестве вершина -- пройтись до родителя

Слайд 12

Эвристики СНМ
Объединение по рангу.
Подвешиваем дерево с меньшей высотой к дереву

с большей. Чтобы не считать высоты -- используем ранги. Ранг одной вершины -- 0. При объединении -- максимум из двух. Если одинаковые -- +1
Сжатие пути
Храним указатель не на родителя, а на корень. Для этого при получении родителя обновляем все указатели, чтобы указывали на корень
Асимптотика -- обратная функция Аккермана (сложно, считать константной)

Слайд 13

Асимптотика алгоритма Крускала
Сортировка рёбер -- O(ElogE)
СНМ -- O(E*alpha(V))
Общая асимптотика --

O(ElogE)

Слайд 14

Алгоритм Борувки
Каждая вершина графа -- дерево
Для каждого дерева найдём минимальноe инцидентное

ему ребро. Добавим в миностов все рёбра
Повторяем шаг 2, пока не получим одно дерево
(В пункте 2 лучше брать ребро минимального номера при равных весах)

Слайд 15

Алгоритм Борувки. Асимптотика
На каждом шаге количество деревьев сокращается как минимум вдвое.

То есть шагов -- logV
Каждый раз надо просмотреть все рёбра, ведущие от дерева.
Итоговая асимптотика -- O(ElogV)

Слайд 16

Максимальный поток в сети.
RMQ & LCA

Слайд 17

Определение сети и потока
Сеть -- орграф, с:E->R+, с(e) -- пропускная способность.

В сети есть исток s и сток t
Поток в Сети -- f:(VxV)->R, где:
1)f(u,v) = -f(v,u)
2)f(u,v) <= c(u,v)
3) Сумма f(x,y) = 0 для всех вершин, кроме s и t
Величина потока -- сумма f(s,v) для всех v

Слайд 18

Разрез. Поток через разрез
Разрез -- знаем
Пропускная способность разреза -- сумма

всех рёбер, пересекающих разрез
Минимальный разрез -- разрез с минимально возможной пропускной способностью
Поток в разрезе -- сумма по f(u,v), (u,v) пересекает разрез

Слайд 19

Лемма о величине потока
f(S,T) = |f|

Слайд 20

Лемма о минимальном разрезе
Если f(S,T) = c(S,T), то поток f максимален,

а разрез -- минимален

Слайд 21

Ещё определения

Слайд 22

Теорема Форда-Фалкерсона
Если f -- поток в сети G = (V,E), то

следующие утверждения эквивалентны:
Поток f максимален
В Gf не существует пути из s в t
|f| = c(S,T) для некоторого разреза сети

Слайд 23

Алгоритм Форда-Фалкерсона
Положим f(u,v) = 0 Далее поток увеличивается итеративно через поиск увеличивающего

пути Поиск можно осуществлять с помощью dfs
Повторяем, пока можем найти увеличивающий путь O(|E|f)

Слайд 24

Алгоритм Эдмонса-Карпа
Улучшение алгоритма Форда-Фалкерсона, в качестве дополняющего пути берём кратчайший по

рёбрам
Асимптотика O(VE^2)
Найти новый кратчайший по рёбрам путь можем только VE раз Во-первых, длина пути -- от 1 до V Сколько различных путей длины i? Ну где-то Е

Слайд 25

Алгоритм Диница
Слоистая сеть Определим для каждой вершины v длину кратчайшего s->v. В

слоистую сеть включаем только те рёбра (u,v), что d[u] + 1 = d[v] Слоистая сеть -- вспомогательная Найдём блокирующий поток -- такой, что любой путь из s в t содержит насыщенное этим потоком ребро. Увеличить не получается.

Слайд 26

Поиск блокирующего потока
Можно просто искать все пути s->t по одному и

наполнять(по крайней мере одно ребро удалится
Оптимизация -- удалять заполненные рёбра и все лишние (из которых нельзя дойти до стока) O(VE)

Слайд 27

Алгоритм Диница
Инициализируем f(u,v) = 0
Построим вспомогательную сеть для остаточной данного графа.

Если пустая -- останавливаемся
Найдём блокирующий поток f’ в Gl
Дополним поток f найденным потоком f’ и повторим с 2
Поиск блок.потока в слоистой сети -- О(VE). Почему итераций -- не более |V|? После пропускания блок.потока по слоистой сети кратчайший дополняющий путь будет длиннее хотя бы на 1. max(length) = |V|
Асимптотика -- O(V^2E)

Слайд 28

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

-- паросочетание с наибольшим количеством рёбер
Чередующаяся цепь -- рёбра поочерёдно принадлежат/не принадлежат паросочетанию
Увеличивающая цепь -- чередующаяся цель, у которой начальная и конечная вершины не принадлежат паросочетанию

Слайд 29

Теорема Бержа
Паросочетание максимально тогда и только тогда, когда не существует увеличивающих

относительно него цепей.
Пусть существует увеличивающая цепь. Тогда “сдвинем” рёбра на один (раз первое и последнее не принадлежат -> увеличим паросочетание -> оно не максимально

Слайд 30

Теорема Бержа <=
Пусть парсоч M не содержит ув. пути, но есть

парсоч M’, который больше чем M
Рассмотрим граф G -- симметрич. отрицание M и M’ -- все рёбра, которые лежат либо в М, либо в M’, но не одновременно. Рассмотрим как граф
У каждого ребра из G есть смежное (если нет, то просто добавим его в M или M’, получим противоречение)
Циклы -- чётные + чередуются из M и M’. Значит, в циклах равное количество
Пути -- чётные. Почему? Если неч, значит начинается с M’ и заканчивается M’, то есть для M это увеличивающий путь.
Если всё чётное -- их размер одинаковые и условие не выполнено

Слайд 31

Алгоритм Куна поиска паросочетаний
Возьмём пустое паросочетание, пока в графе находим увеличивающую

цепь -- выполняем “чередование” и повторяем процесс.
Ищем любую цепь, запуская обход в глубину или ширину вдоль каждой вершины из первой доли. Найдя -- “насыщаем”, то есть вычёркиваем из оставшихся, а обратную считаем созданной. Повторяем, пока не кончатся увеличивающие цепи

Слайд 32

Алгоритм Куна
Возьмём пустое паросочетание
Пока удаётся найти увеличивающую цепь -- выполняем чередование
Массив

matching[v] -- вторая вершина из парсоча или -1
Массив used -- посещена вершина или нет
Функция -- просматриваем все вершины, смежные с v. Если to ненасыщенная или удаётся найти ненасыщенную через рекурсивный запуск от to -- нашли увеличивающую цепь и чередуем.
Функция применяется последовательно ко всем вершинам, перед каждым запуском обнуляем used
O(VE)

Лекция 7. Алгоритм А. Минимальные остовы. Потоки в сетях

Содержание

Ограничение на эвристикиДопустимость h(v) -- для любой вершины эвристика не превосходит

Остовные деревья

Остовное деревоАциклический связный подграф, включающий все вершины графа.Как найти?

Минимальное остовное деревоОстовное дерево, обладающее минимальным суммарным весом рёбер

Лемма о безопасном ребреПусть G’ -- подграф миностова GРебро не из

Лемма о безопасном ребреРассмотрим граф G -- взвешенный неориентированный. G’ --

Алгоритм ПримаПохож на ДейкструПытаемся построить миностов, начиная с любой вершины. Когда

Асимптотика алгоритма Прима

Алгоритм КрускалаОтсортируем все рёбра в порядке возрастания и будем последовательно добавлять

Система непересекающихся множествКаждое множество -- дерево, корень -- его “представитель”. В

Эвристики СНМОбъединение по рангу. Подвешиваем дерево с меньшей высотой к дереву

Асимптотика алгоритма Крускала Сортировка рёбер -- O(ElogE)СНМ -- O(E*alpha(V))Общая асимптотика --

Алгоритм БорувкиКаждая вершина графа -- деревоДля каждого дерева найдём минимальноe инцидентное

Алгоритм Борувки. АсимптотикаНа каждом шаге количество деревьев сокращается как минимум вдвое.

Максимальный поток в сети. RMQ & LCA

Определение сети и потокаСеть -- орграф, с:E->R+, с(e) -- пропускная способность.

Разрез. Поток через разрезРазрез -- знаемПропускная способность разреза -- сумма

Лемма о величине потокаf(S,T) = |f|

Лемма о минимальном разрезеЕсли f(S,T) = c(S,T), то поток f максимален,