algorithm - 带有切口的流网络证明

Question

我目前在大学研究流网络，我的教授向我们提出了这个定理：“给定一个流网络，其中有一个流 B，因此对于每个顶点，除了源和汇：| B(e) 的 ∑(e:u→v) - B(e')的∑(e':v→u) | ≤ε。

注意：这个等式适用于每个 v（不是网络中源或汇的顶点）。e:u→v 意味着我想要在割集中从 u 的集合到 v 的集合的每条边的 B(e) 的总和。然后，e':v→u 意味着我想要从 v 的集合到 u 的集合的每条边的 B(e) 的总和。

存在一个新流 F，对于图中的每条边，|F(e)-B(e)|<ε*N（其中 N 是图中的顶点数）。”</p>

他声称存在证据，但我无法深究。我在考虑 Epsilon 的下限是图的最小切割这一事实，但我所拥有的所有其他想法都是无用的。我会很感激任何帮助。我在网上搜索了证据，但找不到任何东西。

提前致谢，或者

Answer 1

给定对边的数量的反对称分配，顶点的过量是进入的总量减去退出的总量。对于每个带有负超额 -c 的顶点 v，选择从源 s 到 v 的路径，将其乘以 c，然后将其添加到分配中。对于具有正余量 c 的每个顶点 v，选择从 v 到汇 t 的路径，将其乘以 c，并将其添加到分配中。很容易检查 (1) 除了 s 和 t 之外，所有的超额现在都为零 (2) 因为每个超额的绝对值都小于 epsilon，所以边缘的最坏情况变化是它是否涉及每条路径，总共小于 epsilon 乘以 n 的顶点数。