Изменения

Перейти к: навигация, поиск

Циркуляция потока

22 байта убрано, 08:31, 18 декабря 2011
Решение
[[Файл:Циркул3.png]]
Каждое ребро изначального графа мы заменили на три новых. Если по изначальному ребру $e_i = (v_{from}, v_{to})$ должен течь поток $l_i \leqslant f_i \leqslant c_i$, то в новой сети по ребру $(x, v_{to})$ должен течь поток, равный $l_i$, то есть его пропускной способности. Поток, который раньше мог вытекать из $v_{from}$ по изначальному ребру, заменяется на поток, который может течь по ребрам $(v_{from}, v_{to})$ и $(v_{from}, y)$ (это ясно из того, что сумма их пропускных способностей в полученном графе равна $c_i$). То же самое верно и Аналогично в вершине $v_{to}$, куда суммарный возможный входящий поток в которую не изменился. Таким образом, ясно, что любой допустимый поток по любому ребру в изначальном графе можно распределить между тремя ребрами в полученном графе. Заметим, что в этом самом графе все $l_i = 0$, то есть мы имеем обыкновенную сеть.
От нас требовалось найти циркуляцию в исходной сети, то есть проверить, есть ли такой поток, что <tex>\sum\limits_v f(u,v)=0</tex> выполнено для всех вершин этого графа. Но это равносильно существованию потока между вершинами $x$ и $y$ в сети $G'$, который полностью насытит ребра, исходящие из истока. Действительно, этот факт будет означать, что этот поток в исходном графе насытит $i$-ое ребро как минимум на $l_i$, то и является нужным требованием. Если этот поток существует, то мы будем иметь:
355
правок

Навигация