0

我正在阅读 Robert Sedwick 写的算法书。

注：“s”为源，“t”为罐。

用从“t”到“s”的边来扩充任何流网络，流量和容量等于网络的值，并且知道对于扩充网络中的任何节点集，流入等于流出。这样的流称为循环，这种结构表明最大流问题简化为找到使沿给定边缘的流最大化的循环的问题。

给定一组循环和每个循环的流量值，通过跟踪每个循环并将指示的流量添加到每个边缘，很容易计算相应的循环。相反的性质更令人惊讶；我们可以找到一组等效于任何给定循环的循环（每个循环都有一个流量值）。

流动分解定理：任何循环都可以表示为沿着一组最多 E 个有向循环的流动。

我对上述解释的问题

  1. 要求用示例解释作者的意思以及我们如何减少“maxflow 问题简化为找到使给定边缘的流量最大化的循环的问题。”？

  2. 任何人都可以用下面的简单例子来解释。

“给定一组循环和每个循环的流量值，通过跟踪每个循环并将指示的流量添加到每个边缘，很容易计算出相应的循环。相反的性质更令人惊讶；我们可以找到一组循环（每个都有一个流量值）相当于任何给定的流通量。”

谢谢！

4

1 回答 1

3

  1. 如果源 s 和汇 t 存在最大流问题，则只需添加边 t->s 即可将此问题转换为最大循环问题。从 s 到 t 的原始最大流量现在转换为最大循环 s--->t->s。

  2. 如果您有一个循环列表（图中的闭合路径）并且每个循环都与流 N 相关联，那么您可以遍历所有循环并将流值 N 添加到循环经过的那些边缘。以这种方式，图表中的每条边都会有一个为其计算的流量值，这就是图表中的总流通量。相反，该定理说，只要你在总图中有一个循环，它就可以分解成循环。这是最大循环的示例，在每条边上，符号 a(b) 表示流量为 a，边的最大容量为 b：

      3(3)     2(2)
a ----> b -----> c 
^       |1(1)    |
|3(3)   V        V 2(4)
d<------e<-------f
   3(4)     2(3)

对应的循环是：流量值为 1 的 abeda 和流量值为 2 的 abcfed。这两个循环共同定义了最大循环，如上所示。

于 2012-05-11T06:19:22.777 回答