网络流量中的流通

Question

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

注意：“s”是源代码，“t”是坦克。

Augument任何流网络与来自“T”，以“s”用流量和 容量等于网络的值的边缘，并且知道流入等于 到流出对augumented网络中的任何节点集。这样的流程被称为循环，并且这种构造表明最大流问题降低为寻找循环的问题，该循环使沿给定边的流最大化。

给定一组周期和每个周期的流量值，很容易通过跟随每个周期 并将指示的流量添加到每个边沿来计算相应的循环。相反的属性是 更令人惊讶;我们可以找到一组循环（每个循环的流量值为 ），与任何给定的循环相当。沿着一组最E阶定向循环，任何循环都可以表示为流程 。

我上面的解释问题

1. 请求用例子来解释什么作者的意思是，我们如何能减少“maxflow问题简化为找到一个循环 沿着一个最大化流的问题给予优势。“？

2. 可以用下面的段落简单的例子来解释。

“给定一组的周期和每个循环的流量值，很容易 通过每个循环 以下以及将所述指示流动到每个边缘计算相应的循环，相反的性质是 更令人惊讶;我们可以找到一组周期（每个流量值为 ），这相当于任何给定的循环。“

谢谢！

Answer 1

1. 如果你有源S和汇吨maxflow问题，你可以在这个问题只需添加一个边缘的T>取值转换成最大流通问题。从s到t的原始最大流量现在转换成最大循环s→t→s。

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

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

相应周期是：abeda与流量值1，并且流量值2超过。这两个循环一起定义了如上所示的最大循环。