Потоки минимальной стоимости
Потоки минимальной стоимости Пусть h некоторый поток в сети Gf . Определим по h поток в сети G по формуле . Для любой вершины выполняется равенство Поэтому - поток. Здесь . Лемма 1. Пусть f - допустимый поток в сети G = (V,E) , h – допустимый поток в сети Gf =(Vf ,Ef) и - определённый выше поток в сети G . Тогда поток допустим в G , причём Доказательство. В силу допустимости потока h в сети Gf получим Поэтому , что означает допустимость потока . Из равенства вытекает Наконец ■ Для потоков f , g в сети G определим новый поток h=gѲf в сети Gf : 1) если и g(e) > f(e), то h(e) = g(e) – f(e); 2) если ; 3) на всех остальных дугах сети Gf поток считаем равным 0. Очевидно gѲf всегда неотрицательна. Поэтому, вообще говоря gѲf ≠ fѲg . Более того, функции gѲf и fѲg определены на разных сетях Gf и Gg . Отметим, что для любых допустимых потоков f и g в сети G и для любой вершины v из V выполняется равенство div (gѲf) (v) = div (g-f) (v) . Потоки минимальной стоимости Лемма 2. Для любых двух допустимых потоков f и g в сети G = (V,E) поток h = gѲf в сети Gf =(Vf ,Ef) также допустим. Для него справедливы равенства v(h) = v(g) – v(f) и S(h) = S(g) – S(f) . Доказательство. Рассмотрим произвольную дугу е ∈ Е. В силу допустимости потоков f, g, если g(e) > f(e), то h(e) = g(e) - f(e) ≤ с(е) - f(е), а если g(e) < f(e), тo h(ē) = f(e) - g(e) ≤ f(e). Отсюда видно, что поток h допустим. Из div (gѲf) (v) = div (g-f) (v) вытекает, что мощность потока h равна γ(g - f) = γ(g) - γ(f). Далее, из определения h следует, что для любой дуги е ∈ Е выполняется равенство (g(e) - f(e))d(e) = h(e)df(e)+h(ē)df(ē) (в правой части которого одно из слагаемых нулевое или вообще отсутствует). Поэтому S(h)= h(e')df(e')= (g(e) - f(e))d(e) = = S(g - f)=S(g) - S(f). ■
Slaidy.com
