Доказательство леммы для потока на остаточной графике

Question

в CLRS 3'RD издание Существует лемма 26.2, в которой говорится, что:

Пусть $ g= (v, e) $ - это сеть потока, пусть $ f $ Быть потоком в $ g, $ и пусть $ p $ Будьте дополнительному пути в $ G_ {F} $ . Определите функцию $ f_ {p} \ culon v \ murse v \ prightarrow \ mathbb {r} $ $$ f_ {p} (u, v)=левый \ {\ begin {Array} {ll} c_ {f} (p) & \ text {если} (u, v) \ text {находится на} p \\ 0 & \ Text {В противном случае} \ end {Array} \ Right. $$ Затем $ f_ {p} $ - это поток в $ G_ {F} $ со значением $ \ левый | f_ {p} \ hange |= c_ {f} (p)> 0 $

Как бы вы пошли о доказании этого?

Как я понимаю, нам нужно проверить для сохранения потока и ограничения емкости. Мы знаем, что $ c_f (p) $ - это минимум остаточных емкостей на пути $ p $ который меньше, чем мощности, следовательно, ограничение емкости удовлетворены. Но как насчет ограничения охраны потока и доказательство того, что значение потока на самом деле является $ C_F (P)> 0 $ ?

Answer 1

Соблюдайте, что если $ V $ не является вершиной $ p $ , затем $ F_P (U, V)= 0 $ . Когда $ v $ находится в $ p $ а не источник ни раковины, то есть только два Вершины $ v_1 $ и $ v_2 $ Такие, что кромки $ (v_1, v), (v, v_2) $ находятся в $ p $ . Следовательно, в избытке потока в $ v $ $$ \ sum_u f_p (u, v) $$ имеет только два ненулевых термина $ F_P (V_1, V)= C_F (P) $ и $ f_P (v_2, v)= - f_p (v, v_2)= - c_f (p) $ .

Итак, избыточный поток равен нулю.

Чтобы увидеть, что $ C_F (P)> 0 $ просто вспомнить, что он определяется как минимум остаточных мощностей краев $ p $ . Есть конечное количество ребер в $ P $ , и по определению пути дополнения остаточные емкости его краев являются положительными. Итак, вы принимаете минимум конечно много положительных чисел. Это приводит к положительному числу.