我读算法书上写的罗伯特Sedwick。

注：S是源和t是坦克

Augument任何流网络与来自吨到s用流和边缘   容量等于网络的价值，并且知道流入等于   外流在augumented网络中的任何一组节点。这种流动   被称为一个循环，并且这种结构表明，   maxflow问题简化为找到一个循环的问题   最大化沿着一个给定的边缘流动。

给定一组的周期，并为每个周期的流量值，很容易   通过每个周期下计算相应的循环   并加入指定的流的每个边缘。反过来属性   更令人惊讶的;我们可以找到一组循环（与流量值   各自），它等效于任何给定的循环

流分解表示定理：任何循环可再presented如流   沿着一组atmostË执导周期。

我上面的解释问题

要求用例子来解释是什么意思的作者，我们如何能减少maxflow问题简化为找到一个循环的问题 最大化沿着一个给定的边缘流动。

可以用简单的例子下款任何一种解释。

给定一组的周期，并为每个周期的流量值，很容易   通过每个周期下计算相应的循环   并加入指定的流的每个边缘。反过来属性   更令人惊讶的;我们可以找到一组循环（与流量值   各自），它等效于任何给定的循环。

谢谢！

如果你有maxflow问题源S和汇T，则只需添加一个边缘T->秒值进行转换这一问题成最大流通问题。从s原来的最大流量至T现在已经转变成一个最大的循环小号---> T->秒。

如果你有个周期（在图形封闭路径）的列表，每个周期与流动氮相关的，你可以通过所有的循环，并添加流量值N至那些边缘的周期经历。以这种方式，在图中每个边缘具有计算它的流量值，并且这是在图形的总循环。相反地​​，定理说，只要你有在总图中的一个循环，它可以被分解成周期。这里是一个最大循环的一个例子，在每个边缘的表示法（b）一种装置，该流是和边缘最大容量为b

  3（3）2（2）
一个----＆GT; b -----＆GT; C
^ | 1（1）|
| 3（3）V V 2（4）
D＆LT; ------ e控制-------˚F
   3（4）2（3）
 

相应的周期是：abeda与流量值1，并用流动值abcfed 2.这两个周期一起限定的最大循环如上所示

I am reading Algorithms book written by Robert Sedwick.

Note: "s" is source and "t" is tank.

Augument any flow network with an edge from "t" to "s" with flow and capacity equal to the network's value, and know that inflow is equal to outflow for any set of nodes in the augumented network. Such a flow is called a circulation, and this construction demonstrates that the maxflow problem reduces to the problem of finding a circulation that maximizes the flow along a given edge.

Given a set of cycles and a flow value for each cycle, it is easy to compute the corresponding circulation by following through each cycle and adding the indicated flow to each edge. The converse property is more surprising; We can find a set of cycles (with a flow value for each) that is equivalent to any given circulation.

Flow decomposition theorm: Any circulation can be represented as flow along a set of atmost E directed cycles.

My questions on above explanation

Request to explain with example what does author mean and how we can reduce "maxflow problem reduces to the problem of finding a circulation that maximizes the flow along a given edge. "?

Can any one explain with simple example following paragraph.

"Given a set of cycles and a flow value for each cycle, it is easy to compute the corresponding circulation by following through each cycle and adding the indicated flow to each edge. The converse property is more surprising; We can find a set of cycles (with a flow value for each) that is equivalent to any given circulation."

Thanks!

If you have a maxflow problem with source s and sink t, you can convert this problem into a maximum circulation problem by just adding an edge t->s. The original maximum flow from s to t is now converted into a maximum circulation s--->t->s.

If you have a list of cycles (closed paths in your graph) and every cycle is associated with a flow N, you can go through all the cycles and add the flow values N to those edges the cycles go through. In this fashion, every edge in your graph will have a flow value calculated for it, and this is the total circulation in your graph. Conversely, the theorem says that whenever you have a circulation in the total graph, it can be decomposed into cycles. Here is an example of a maximum circulation, on every edge the notation a(b) means that the flow is a and edge maximum capacity is b:

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

The corresponding cycles are: a-b-e-d-a with flow value 1, and a-b-c-f-e-d with flow value 2. Those two cycles together define the maximum circulation as shown above.