2018-01-08
935
Задача о максимальном потоке.
Сеть – это ориентированный взвешанный граф G = (v,e) с положительными весами ребер с(е), в котором есть ровно одна вершина – источник (S) и ровно одна вершина – сток (T).
Вершины не равные S и Т называются внунтренними,
Вес ре6ра с(e) – пропускная способность ребра.
Потоком называется функция f, которая переводит множество ребер в множество действительных чисел.
Функция f удовлетворяет:
1. Для любого ребра e € E: 0<=f(e)<=c(e)
2. Для всех v € V, v<>S, v=T: div+ (v) =div_(v), где
· div+ - суммарный поток по всем ребрам е, таким что е=(u,v)
div+(v) = 
, e=(u,v) – величина входящего потока
· div_ - величина исходящего потока
div_(v) = ,
Свойство потока: div_(S)=div+(T)
Величина div_(S)=div+(T) называется величиной потока в сети.
Задача о максимальном потоке.
Найти поток, величина которого не меньше величины любого другого потока (найти поток с максимальной величиной)
Остаточная сеть.
Пусть дана сеть G и в ней запущен поток f, остаточная сеть – это взвешенный ориентированный граф с множеством вершин V и множеством дуг, определяющих:
|
|
|
1. если в сети G есть ребро (u,v) и величина потока по этому ребру меньше с(е), то в остаточной сети есть ребро e=(u,v) с весом с(е)-f(e) – прямые ребра
2. если в G есть ребро е=(u,v) и поток через это ребро >0, то в остаточной сети есть ребро e’=(u,v) с весом f(e) – встречные ребра
Аугментальный (увеличивающий) путь.
Если в остаточной сети существует ориентированный путь из S в T, то в исходной сети можно увеличить поток вдоль этого пути. При этом проход по прямым ребрам - увеличение потока в данном ребре исходной сети, а по встречному ребру – уменьшение потока.
Алгоритм Форда-Фалкерсона
1. Запустить 0-й поток f(e)=0
2. Построитьостаточнуюсеть
3. Найти в остаточной сети ориентированный путь из S в T
4. Если путь найден, то увеличить поток вдоль этого пути и перейти к шагу 2. Иначе конец алгоритма. Текущий поток является максимальным.
