Занятие по алгоритмам 0904 Другое определение потока. Сеть это hV, c, s, ti, где c это таблица смежности для всех пар вершин(таблица не симметричная). Поток это f
 Скачать 123.34 Kb.
|
|
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 не появится никогда. Доказательство на пальцах. *** Тут гуляют примеры задач, но зачем их записывать? *** |