Изменения

Перейти к: навигация, поиск
Подробное описание
===Подробное описание===
Для каждой вершины <tex>v</tex> вычислим входящий и исходящий потенциал: <tex>\varphi_{in}=\sum \limits_{u} c(u, v)</tex> и <tex>p_\varphi_{out}=\sum \limits_{u} c(u, v)</tex>. Пусть <tex>p_\varphi_{in}(s)=\infty</tex> и <tex>p_\varphi_{out}(t)=\infty</tex>. Определим потенциал или пропускную способность вершины в [[Определение сети, потока|сети]] <tex>p\varphi(v)=min(p_\varphi_{in}(v), p_\varphi_{out}(v))</tex>. Таким образом, потенциал вершины определяет максимально возможное количество потока, который может через нее проходить. Ясно, что через вершины с <tex>p\varphi(v)=0</tex> поток проходить не может. Следовательно, их можно удалить из [[Дополняющая сеть, дополняющий путь|вспомогательной сети]]. Удалим эти вершины и дуги, им инцидентные, обновив должным образом потенциалы вершин, смежных с удаленными. Если в результате появятся новые вершины с <tex>p\varphi(v)=0</tex>, удалим рекурсивно и их. В результате во вспомогательной сети останутся только вершины с <tex>p\varphi(v)\ne0</tex>.
После этого приступим к построению [[Блокирующий поток|блокирующего потока]]. Пусть вершина <tex>v</tex> принадлежит <tex>k</tex>-ому слою. Протолкнем <tex>p</tex> единиц потока из вершины с минимальным потенциалом в смежные с ней вершины по исходящим дугам с ненулевой остаточной пропускной способностью. Попутно будем переносить проталкиваемый поток в исходную сеть, а также корректировать потенциалы вершин, отправляющих и принимающих избыток потока. В результате, весь (в виду минимальности потенциала вершины <tex>v</tex>) проталкиваемый поток соберется в вершинах <tex>(k+1)</tex>-го слоя.
Анонимный участник

Навигация