网络流（Flow Networks）

一.基本术语 Basic Terminology

A sourcenode in a directed graph is a node with no incoming edges. 入度为0

A sink node in a directed graph is a node with no outgoingedges. 出度为0

A flow network is a directed graph (V,E,c,s,t) where (V,E,c)forms a weighted graph with positive edge weights, s ∈ V is asource node and t ∈ V is a sink node.

二.最大流算法的理解

其实感觉这个跟数学建模里面的单目标优化问题类似，就是在源点一定的情况下，尽可能多的将物品传到终点，限制条件是每条路径上的最大值。

下面图是网上随便找的。

Flow Graph:实际上运输上传送的值。

Residual Graph:经过变化一次次传输，现在还剩余的图，即SG-FG，感觉作用就是是因为SG画的太乱了，分一个好判断一点。

具体的过程：

1）在SG中找到一条S->T的路径，找到最小的限制，即流上的最小值（bottom neck）。

2）在RG图中减去这次运输的值，得到RG；在FG中加上相应的值

3）LOOP 1)2)直到无路可走。

这样会有错误，因为最大流存在先后顺序？先驱顺序？？（待确定名称）这样得不到最大流。

引入返回路径

每当我们选择了一个运输路径后，都要在RG中新画一个反向的路径，即这条路径传递了3，反向传递3。

为什么这么做的完整解释，后补。

三.Cuts

A cut in a graph is a set C of edges such that removing them woulddisconnect the graph into left(C) (nodes reachable from s) and theright part right(C) (nodes that may reach t).

左边的不包括右到左方向的箭头

The capacity of a cut C in a flow network is the sum of the capacity ofedges that goes from left to right

A minimal cut is a cut with minimal capacity.