Алгоритмы на графах и их приложения. Дорофеева В.И. - 12 стр.

     Пусть ν=(Х0, Х , …, Х        , Х n ) – цепь, соединяющая вход Х0 с выходом
                     i1      in

ХN. Предположим, что она не является путем. Если ориентация дуги совпадает
с направлением прохождения цепи, то будем обозначать ее через u→ , в против-
ном случае – через u← .
     Положим
                                  δ(u→)=с(u→)–ϕ (u→) ,

                                    ϕ*=min ϕ (u←) ,

                                    δ*= min δ (u←) ,

                                     ε*=min[ϕ*,δ*].

     Теорема 2. Если ε*>0, то, увеличивая на ε* поток на каждой дуге u→ и
уменьшая на ε* поток на каждой дуге u← цепи ν, мы увеличиваем поток ϕ так-
же на ε*.
     Полный поток. Поток ϕ транспортной сети назовем полным, если любой
путь, соединяющий Х0 с ХN, содержит по крайней мере одну насыщенную дугу.
     Иначе говоря, нельзя увеличить ϕ, рассматривая только пути; хотя это
иногда можно сделать, рассматривая цепи, соединяющие Х0 с ХN.
     Теорема 3. Если не существует цепи ν от Х0 до ХN с ε*>0, то поток ϕ
нельзя больше увеличить, то есть он максимальный.
     Действительно, исключая из транспортной сети все дуги, для которых
δ(u→)=0 или ϕ (u←)=0, получаем по крайней мере два несвязных подграфа (в
противном случае существовала бы ненасыщенная цепь, соединяющая Х0 с
ХN). Множество вершин тог из них, среди вершин которого содержится ХN,
обозначим через А.

     Очевидно, что А определяет разрез U -А и




                                           12