关于网络流量均衡属性

Question

我正在阅读有关图形算法的Robert Sedwicks书中的网络流算法。以下是该书的文本片段。

性质：任何st流都具有流出s的属性等于 流入t。

证明：Augument与边缘网络从虚设顶点为s， 与流和容量等于从“S”中流出，并与边缘 从“T”到另一虚设顶点，具有流量和容量等于流入“t”的 。然后，我们可以通过 归纳证明一个更一般的属性：入口等于任何一组顶点的流出（不包括包含虚拟顶点的 ）。

这个属性对任何单个顶点都是真实的，通过局部平衡。 现在，假设对于给定的一组顶点“S”它是对的，并且我们添加单个顶点“v”来使集合S1 = S U {v}。为了计算S1的流入和流出，注意S中从“v”到某顶点 的每条边减少流出（从V）减少与减少流入 （到S）相同的量;从S中的某个顶点到v的每个边减少流入（到v）与减少流出（从S）相同的量;并且所有其他边缘 为S1提供流入或流出当且仅当它们为S或v时这样做 因此，流入和流出对于S1是相等的，并且流量 的值等于v和S的流量减去在边缘上的流量连接到S中的顶点（方向为 方向）之和。

应用这个属性来设置所有的网络顶点，我们 发现，从其关联的虚拟顶点源的流入是 等于汇的流出assicated虚拟顶点山雀。

我对以上的证明问题：

1. 什么是笔者的“从各个边缘‘V’，以S中一些顶点减少相同量流出（从V），因为它减少意味着流入（对S）“？ 可以用任何一个简单的例子来解释。

2. 作者的意思是“从S中的某个顶点到v的每个边减少流入量（到v）相同的量，因为它减少流出量（从S）;所有其他边为S1提供流入或流出当且仅当他们这样做S或V“？请用简单的例子来解释。

3. 作者的意思是“流入和流出对于S1是相等的，而流 的值等于v和S的流的值减去边缘上的流的总和connectin v到S中的顶点（任一方向）。“ ？请用例子来解释。

谢谢！

Answer 1

该段落写得不是很好，但如果我把它写得很对，作者意味着从v到S顶点的流（名为this vertex t）会增加从给定值到v的流出量，但它也是以相同的值增加t的流入量。因此，添加这样一个优势，我们仍然认为总和流入等于总和流出量。类似地，对于从S到V的顶点的边，我们增加v的流入和S中顶点的流出具有相同的值。所有其他边缘连接来自S的两个顶点，并且通过归纳假设，它们的总和流入等于它们的总和流出。请注意，而不是术语减少顶点v的流出，我用“增加流出量”，因为它对我来说似乎更自然。 我不敢猜测作者第二到最后一段的最后一句是什么意思。

希望至少有一点帮助。

我相信有一些书籍，这个特定的定理似乎更好地解释了例如Thomas H. Cormen，Charles E. Leiserson，Ronald L. Rivest，Clifford Stein所写的“算法导论”。