algorithm - 为什么从起点流到某个点等于从某个点流到终点？

Question

从幻灯片的第 3 页，第二点声称 |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是唯一可以消耗它的顶点。