algorithm - 为什么从开始流到某个点等于从某个点流到结束？

Question

来自 page3 of the slide , 第二点声称 |f| = f(s,v) 的总和，其中 s 属于 V = f(v,t) 的总和，其中 v 属于 V。(抱歉，我不知道如何在 markdown 中输入它。)

我不明白为什么等式成立。

Answer 1

从标题看，你好像读错了等式。第一个和中的顶点 v 是与 s 相邻的顶点。它们不与第二个总和中的顶点v相同。这些是与 t 相邻的那些。

该等式表示流出 s 的总流量(来自 s 的边上流量的总和)等于流入 t 的总流量。

这一定是真的，因为流入每个其他顶点的总流量必须等于流出的总流量(这就是流量守恒约束)。因此，如果在 s 的边上有流量，那么如果它到达一个不是 t 的顶点，那么它必须再次从该顶点流出，等等。 , 直到达到 t。

所有从s流出的流量最终必须到达t，因为t是唯一的顶点可以食用它。