关于网络流量均衡性质
我正在 Robert Sedwicks 关于图算法的书中阅读有关网络流算法的内容。以下是书中的文字片段。
性质：任何 st-flow 都具有以下性质：从 s 流出的流量等于 流入t。
证明：使用从虚拟顶点到 s 的边来增强网络， 流量和容量等于“s”的流出量，并且有边缘 从“t”到另一个虚拟顶点，流量和容量等于 流入“t”。然后，我们可以证明一个更一般的性质 归纳：对于任何一组顶点，流入等于流出（不是 包括虚拟顶点）。
通过局部平衡，此属性对于任何单个顶点都成立。 现在，假设对于给定的一组顶点“S”来说这是正确的，并且 我们添加单个顶点“v”以使集合 S1 = SU {v}。计算 S1 的流入和流出，注意从“v”到某个顶点的每条边 S 中减少的流出量（来自 V）与减少的流入量相同 （对S）；从 S 中某个顶点到 v 的每条边都会减少（到 v）的流入 与减少流出量（从 S）相同的量；和所有其他边缘 为 S1 提供流入或流出当且仅当它们为 S 或 v 提供流入或流出。 因此，S1 的流入和流出相等，并且流量值 等于 v 和 S 的流量值之和减去 将 v 连接到 S 中的顶点的边上的流（或者 方向）。
将此属性应用于所有网络顶点的集合，我们 发现源从其关联的虚拟顶点的流入是 等于汇流到山雀相关虚拟顶点的流出量。
我对上述证明的问题：
作者所说的“从“v”到 S 中某个顶点的每条边减少（从 V ）流出的量与减少（到 S ）流入的量相同”是什么意思？ 任何人都可以用简单的例子解释一下。
作者所说的“从 S 中某个顶点到 v 的每条边减少（到 v）的流入量与减少（从 S）流出的量相同；” 并且所有其他边为 S1 提供流入或流出当且仅当它们为 S 或 v 提供流入或流出时”？请用简单的示例进行解释。
作者所说的“流入和流出对于 S1 相等，并且 的值”是什么意思流量 等于 v 和 S 的流量值之和减去连接 v 到 S 中的顶点（任一方向）的边上的流量之和。”？请举例说明。
谢谢！
I am reading about network flow algorithms in Robert Sedwicks book on Graph algorithms. Following is text snippet from the book.
Property: Any st-flow has the property that outflow from s is equal to
the inflow to t.Proof: Augument the network with an edge from a dummy vertex into s,
with flow and capacity equal to the outflow from "s", and with an edge
from "t" to another dummy vertex, with flow and capactiy equal to the
inflow to "t". Then, we can prove a more general property by
induction: Inflow is equal to outflow for any set of vertices (not
including the dummy vertices).This property is true for any single vertex, by local equilibrium.
Now, assume that it is true for a given set of vertices "S" and that
we add a single vertex "v" to make the set S1 = S U {v}. To compute
inflow and outflow for S1, note that each edge from "v" to some vertex
in S reduces outflow (from V) by the same amount as it reduces inflow
(to S); each edge to v from some vertex in S reduces inflow (to v) by
the same amount as it reduces outflow (from S); and all other edges
provide inflow or outflow for S1 if and only if they do so for S or v.
Thus, inflow and outflow are equal for S1, and the value of the flow
is equal to the sum of the values of the flows of v and S minus sum of
the flows on the edges connectin v to a vertex in S (either
direction).Applying this property to the set of all the networks vertices, we
find that the source's inflow from its associated dummy vertex is
equal to the sink's outflow to tits assicated dummy vertex.
My question on above proof:
What does author mean by "that each edge from "v" to some vertex in S reduces outflow (from V) by the same amount as it reduces inflow (to S)" ?
can any one explain with simple example.What does author mean by "each edge to v from some vertex in S reduces inflow (to v) by the same amount as it reduces outflow (from S);
and all other edges provide inflow or outflow for S1 if and only if they do so for S or v" ? please explain with simple example.What does author mean by " inflow and outflow are equal for S1, and the value of the flow
is equal to the sum of the values of the flows of v and S minus sum of the flows on the edges connectin v to a vertex in S (either direction)." ? pls explain with example .
Thanks!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
该段写得不是很好，但如果我简而言之，作者的意思是，从 v 到 S 的顶点（将此顶点命名为 t）的流增加了给定值下 v 的流出，但它也增加了t 具有相同的值。因此，添加这样一条边，我们仍然可以得到总流入等于总流出。类似地，对于从 S 到 v 的顶点的边，我们以相同的值增加 v 的流入和 S 中顶点的流出。所有其他边连接来自 S 的两个顶点，并且通过归纳假设，它们的总流入量等于它们的总流出量。请注意，我使用“增加流出”而不是“减少顶点 v 的流出”这个术语，因为这对我来说似乎更自然。
我不敢猜测作者倒数第二段的最后一句是什么意思。
希望这至少有一点帮助。
我相信有些书似乎可以更好地解释这个特定定理，例如 Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest、Clifford Stein 撰写的《算法导论》。
The paragraph is not very well written but if I get it right in short the author means that flow from v to a vertex from S(name this vertex t) increases the outflow from v with a given value, but it also increases the inflow of t with the same value. So adding such an edge we still have that the summar inflow equals the summar outflow. Similarly for an edge from a vertex from S to v we increse the inflow of v and the outflow of the vertex in S with the same value. All othere edges connect two vertices from S and by the inductive assumption their summar inflow equals their summar outflow. Please note that instead of the term reduces the outflow for vertex v I used "increases the outflow" as it seems to be more natural for me.
I would not dare to guess what does the author mean by the last sentence of the second to last paragraph.
Hope that helps at least a little bit.
I believe there are books where this particular theorem seems to be better explained for instance "Introduction to algorithms" written by Thomas H. Cormen,Charles E. Leiserson,Ronald L. Rivest,Clifford Stein.