Алгоритмы конспект. Занятие по алгоритмам 0904 Другое определение потока. Сеть это hV, c, s, ti, где c это таблица смежности для всех пар вершин(таблица не симметричная). Поток это f
 Скачать 256.79 Kb.
|
|
1-ое занятие по алгоритмам. Поток(flow). Это математический объект. Мы можем рассматривать как водопроводную сеть, которая представлена в виде взвешенного ориентированного графа. В графе есть две(может больше) особенные вершины - исток и сток. Мы хотим "перегонять"как можно больше воды в секунду. Сеть - это ориентированный граф. : E → R - пропускная способность, e ∈ V - исток, t ∈ V - сток. Поток - это функция f : E → R которая возвращает поток по ребру. В котором выполняется два правила. (1) Сумма входящей воды равна выходящей. (2) По ребру проходит воды не больше чем его пропускная способность. Величина потока. |f | t = сумма входящих в сток минус сумма всех исходящих из стока. |f | s = сумма выходящих из истока минус сумма всех входящих из истока. На самом деле эти суммы равны, доказательство заключается в том что в каждую вершину входит столько же воды сколько и выходит, но в исток "свыше"приходит вода, значит она куда-то должна деться, очевидно что только в сток. Доказательство существования максимального потока. У потоков есть точная верх- няя грань, возьмем последовательность потоков подходящей к точной верхней грани. Выберем какое-то ребро и возьмем бесконечную сходящуюся подпоследовательность из нашей последо- вательности для ребра. Проделаем данную операцию для каждого ребра, возьмем предел для каждого ребра, все свойства будут выполняться. Просто искать пути и заполнять их - нельзя. Есть пример даже без циклов, если мы выбрали путь, который блокирует другие пути. Опр. Пусть есть сеть и поток, тогда остаточной сетью назовем сеть в которой пропускную способность заменим на (пропускную способность минус поток) и добавим обратное ребро с весом потока. Утв. Если в остаточной сети есть путь по не нулевым ребрам, то поток не максимален. 2-е занятие по алгоритмам 09-04 Другое определение потока. Сеть - это hV, c, s, ti, где c - это таблица смежности для всех пар вершин(таблица не симметричная). Поток - это f : V × V → R, такая что (1)∀u, v ∈ V : f (u, v) 6 c(u, v), (2)∀u, v ∈ V : f (u, v) = −f (v, u), (3)∀v ∈ V \ {s, t} : P u∈V f (u, v) = 0 Все следующие действия производятся с данным определением потока. Величина потока и доказательство равенства двух определений. |f | s = P u∈V f (s, u), |f | t = P u∈V f (u, t). 0 = P u,v∈V f (u, v) = P u∈V f (s, u) − P u∈V f (u, t) = |f | s − |f | t Разрез. Пусть есть сеть, тогда разрез - это два множества (S, T ) : S t T = V, s ∈ S, t ∈ T Чистый поток через разрез. Пусть есть сеть и разрез, тогда чистый поток через разрез - это f (S, T ) := P u∈S,v∈T f (u, v) Пропускная способность разреза - это c(S, T ) = P u∈S,v∈T c(u, v) Утв. f (S, T ) 6 c(s, T ) Лемма. ∀(S, T ) : f (S, T ) = |f |. Доказательство: |f | = P u∈S P v∈V f (u, v) + P u∈T P v∈V f (u, v) = = P u∈S P v∈T f (u, v) = f (S, T ) Следствие. ∀(S, T )|f | 6 c(S, T ) Остаточная сеть - это c(u, v) = c(u, v) − f (u, v) Теорема.(Форда-Фалкерсона). Пусть есть сеть, тогда следующие утверждения эквива- лентны. 1. f - максимальный поток 2. В остаточной сети нет пути по не насыщенным ребрам. 3. |f | = c(S, T ) для какого-то разреза. 1 ⇒ 2 очевидно. 3 ⇒ 1 очевидно. Доказательство 2 ⇒ 3, например, можно удалить все насы- щенные ребра, получится хотя бы две компоненты, очевидным способом выберем разрез. *** Тут гуляют примеры задач, но зачем их записывать? *** Метод Форда-Фаркенсона пока можем находим путь из s в t по ненасыщенным ребрам и пускаем по нему сколько можем. Этот алгоритм верен для целых чисел, но если числа не целые, то алгоритм может не завершиться . Асимптотика будет O(|f |(V + E)), O(kE), O(V E). Выбирай любую. Утв. Пусть в сети ищется поток ФФ, пусть в какой-то момент времени от вершины v до вершины t нет пути, тогда после этого момента такой путь от v до t не появится никогда. Доказательство на пальцах. *** Тут гуляют примеры задач, но зачем их записывать? *** 3-е занятие по алгоритмам. Алгоритм Эдмондса-Карпа - это метод ФФ, но с поиском пути BFS. Утв. Расстояние(по количеству ребер) от произвольной s до произвольной вершины v в процессе алгоритма не уменьшается. Доказательство. Пусть мы ищем произвольный путь. Заметим, что если мы пустим поток через путь, то вершина не перескочит в слой левее, значит утверждение верно. Рассмотрим сколько раз могло насытиться ребро. Заметим, что если ребро насытилось несколько раз, то между этими насыщениями ребро когда-то разнасытилось, тогда рассмот- рим в каких слоях находятся эти вершины. Значит насыщений ребра могло быть только V 2 . Ребер всего 2E. Значит алгоритм работает за O(V E 2 ) Давайте заметим, что если расстояние от s до t не увеличивается, то нам не надо переза- пускать BFS. Концепция блокирующих потоков - пока у нас есть ненасыщенный путь мы находим слоистую сеть и находим блокирующий поток в слоистой сети. Слоистая сеть - это первая картинка, но мы временно игнорируем обратные ребра и внутри слоя. Блокирующий поток - это такой поток, что мы не можем найти путь, который не содер- жит обратных ребер. Наша концепция завершится, потому что каждая итерация нашего цикла увеличивает рас- стояние между вершинами от s до t, строго увеличится. Рассмотрим алгоритм поиска блокирующего потока. Если ребро насытилось, то мы про него забываем, если мы прошли по ребру и дальше не нашли путь до t, то тоже про ребро забываем. Заметим, что теперь DFS по слоистой сети работает за V + E удаленные . Значит поиск блокирующего потока происходит за V E. Чтобы забывать ребра можно как-то пронумеровать ребра исходящие из каждой вершины и еще хранить число сколько ребер мы забыли. Итоговый алгоритм работает за O(V 2 E) Целочисленные сети. Единичные сети. Давайте посмотрим на алгоритм Диницы, заметим, что мы удаляем все ребра по которым прошли, значит поиск блокирующего будет за E. Давайте заметим, что всего итераций поиска блокирующего потока будет не больше чем 2 √ E. Доказательство Рассмотрим сеть после √ E поиска блокирующего потока, продолжим алгоритм и посмотрим на поток, заметим что все пути больше √ E, значит фаз будет не больше E √ E . Значит в итоге Диница работает за O(V √ E). |