残余图中流动的引理证明

Question

在clrs 3'rd版本中，有一个引理26.2，它指出：

let $ g=（v，e）$ 是一个流量网络，让 $ f $ 在 $ g，$ 中，让 $ p $ 是 $ g_ {f} $ 。定义函数 $ f_ {p} \ colon v \ time v \ lightarrow \ mathbb {r} $ by $$ f_ {p}（u，v）= \左\ {\ begin {array} {ll} c_ {f}（p）＆\ text {if}（u， v）\ text {in} p \\ 0＆\ text {否则} \ end {array} \ right。$$ 然后， $ f_ {p} $ 是 $ g_ {f} $ 的流量 $ \ left | f_ {p} \ light |= c_ {f}（p）> 0 $

你怎么样证明这个？

我了解我们需要检查流动节约和容量约束。我们知道<跨度类=“math-container”> $ 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 $ 以及增强路径的定义，在 $ P $ 中边缘的定义是正的。所以，你的最低限度是最少的许多积极数字。这导致正数。