网络流的资料

PASCAL 求网络流资料~

可以看一下百度百科：

http://baike.baidu.com/view/165435.html?wtp=tt

或者这个（图片复制不下来）：

5.1 基本概念

在实际生活中有许多流量问题，例如在交通运输网络中的人流、车流、货物流，供水网络中的水流，金融系统中的现金流，通讯系统中的信息流，等等。50年代以福特(Ford)、富克逊(Fulkerson)为代表建立的“网络流理论”，是网络应用的重要组成部分。在最近的奥林匹克信息学竞赛中，利用网络流算法高效地解决问题已不是什么稀罕的事了。本节着重介绍最大流(包括最小费用)算法，并通过实际例子，讨论如何在问题的原型上建立—个网络流模型，然后用最大流算法高效地解决问题。

1.问题描述 如图5-1所示是联结某产品地v1和销售地v4的交通网，每一弧(vi,vj)代表从vi到vj的运输线，产品经这条弧由vi输送到vj，弧旁的数表示这条运输线的最大通过能力。产品经过交通网从v1到v4。现在要求制定一个运输方案使从v1到v4的产品数量最多。





图5-1 图5-2

2.网络与网络流

给一个有向图N=(V，E)，在V中指定一点，称为源点(记为vs，和另一点，称为汇点(记为vt)，其余的点叫中间点，对于E中每条弧(vi，vj)都对应一个正整数c(vi，vj)≥O(或简写成cij)，称为f的容量，则赋权有向图N=(V，E，c，vs，vt)称为一个网络。如图5-1所给出的一个赋权有向图N就是一个网络，指定v1是源点，v4为汇点，弧旁的数字为cij。 所谓网络上的流，是指定义在弧集合E上一个函数f={f(vi，vj)}，并称f(vi，vj)为弧(vi，vj)上的流量(下面简记为fij)。如图5-2所示的网络N，弧上两个数，第一个数表示容量cij，第二个数表示流量fij。

3.可行流与最大流
在运输网络的实际问题中，我们可以看出，对于流有两个显然的要求：一是每个弧上的流量不能超过该弧的最大通过能力(即弧的容量)；二是中间点的流量为0，源点的净流出量和汇点的净流入量必相等且为这个方案的总输送量。因此有：
(1)容量约束：0≤fij≤cij，(vi,vj)∈E，
(2)守恒条件
对于中间点：流入量=流出量；对于源点与汇点：源点的净流出量vs(f)=汇点的净流入量（-vt(f)）
的流f，称为网络N上的可行流，并将源点s的净流量称为流f的流值v(f)。
网络N中流值最大的流f*称为N的最大流。

4.可增广路径
所谓可增广路径，是指这条路径上的流可以修改，通过修改，使得整个网络的流值增大。

设f是一个可行流，P是从源点s到汇点t的一条路，若p满足下列条件：
(1)在p上的所有前向弧(vi→vj)都是非饱和弧，即0≤fij<cij
(2)在p上的所有后向弧(vi←vj)都是非零弧，即0<fij≤cij
则称p为(关于可行流f的)一条可增广路径。

5.最大流定理
当且仅当不存在关于f*的增广路径，可行流f*为最大流。



5. 2 最大流算法

算法思想:最大流问题实际上是求一可行流{fij}，使得v(f达到最大。若给了一个可行流f，只要判断N中有无关于f的增广路径，如果有增广路径，改进f， 得到一个流量增大的新的可行流；如果没有增广路径，则得到最大流。
1.寻求最大流的标号法(Ford,Fulkerson)
从一个可行流(一般取零流)开始，不断进行以下的标号过程与调整过程，直到找不到关于f的可增广路径为止。
(1)标号过程
在这个过程中，网络中的点分为已标号点和未标号点，已标号点又分为已检查和未检查两种。每个标号点的标号信息表示两个 部分：第一标号表明它的标号从哪一点得到的，以便从vt开始反向追踪找出也增广路径；第二标号是为了表示该顶点是否已检查过。
标号开始时，给vs标上(s，0)，这时vs是标号但末检查的点，其余都是未标号的点，记为(0，0)。
取一个标号而未检查的点vi，对于一切未标号的点vj：
A．对于弧(vi，vj)，若fij<cij，则给vj标号(vi，0)，这时，vj点成为标号而未检查的点。
B．对于弧(vi，vj)，若fji>0，则给vj标号(-vi，0)，这时，vj点成为标号而未检查的点。
于是vi成为标号且已检查的点，将它的第二个标号记为1。重复上述步骤，一旦vt被标上号，表明得到一条从vi到vt的增广路径p，转入调整过程。
若所有标号都已检查过去，而标号过程进行不下去时，则算法结束，这时的可行流就是最大流。
(2)调整过程
从vt点开始，通过每个点的第一个标号，反向追踪，可找出增广路径P。例如设vt的第一标号为vk(或-vk)，则弧(vk，vt)(或 相应地(vt，vk))是p上弧。接下来检查vk的第一标号，若为vi(或-vi)，则找到(vi，vk)(或相应地(vk，vi))。再检查vi的第一 标号，依此类推，直到vs为止。这时整个增广路径就找到了。在上述找增广路径的同时计算Q：
Q=min{min(cij-fij)，minf*ij}
对流f进行如下的修改：
f'ij = fij+Q (vi，vj)∈ P的前向弧的集合
f'ij = fij-Q (vi，vj)∈ P的后向弧的集合
f'ij = f*ij (vi，vj)不属于P的集合
接着，清除所有标号，对新的可行流f’，重新进入标号过程。

例1:下图表示一个公路网,V1是某原材料产地,V6表示港口码头,每段路的通过能力(容量)如图上的各边上的数据,找一运输方案,使运输到码头的原材料最多?



程序如下:

Program Max_Stream;
Const Maxn=20;
type
nettype=record
C,F:integer;
end;
nodetype=record
L,P:integer;
end;
var
Lt:array[0..maxn] of nodetype;
G:Array[0..Maxn,0..Maxn] of Nettype;
N,S,T:integer;
F:Text;

Procedure Init;{初始化过程，读人有向图，并设置流为0}
Var Fn :String;
I,J :Integer;
Begin
Write( 'Graph File = ' ); Readln(Fn);
Assign(F,Fn);
Reset(F);
Readln(F,N);
Fillchar(G,Sizeof(G) ,0);
Fillchar(Lt,Sizeof(Lt),0);
For I:=1 To N Do
For J:=1 To N Do Read(F,G[I,J].C);
Close(F);
End;

Function Find: Integer; {寻找已经标号未检查的顶点}
Var I: Integer;
Begin
I:=1;
While (I0)And(Lt[I].P=0)) Do Inc(I);
If I>N Then Find:= 0 Else Find:= I;
End;

Function Ford(Var A: Integer):Boolean;
Var {用标号法找增广路径，并求修改量A}
I,J,M,X:Integer;
Begin
Ford:=True;
Fillchar(Lt,Sizeof(Lt),0);
Lt[S].L:=S;
Repeat
I:= Find;
If i=0 Then Exit;
For J:=1 To N Do
If (Lt[J].L= 0)And((G[I,J].C0)or(G[J,I].C0)) Then
Begin
if (G[I,J].F<G[I,J].C) Then Lt[J].L:= I;
If (G[J,I].F>0) Then Lt[J].L:=-I;
End;
Lt[I].P:=1;
Until (Lt[T].L0);
M:=T;A:=Maxint;
Repeat
J:=M;M:=Abs(Lt[J].L);
If Lt[J].L<0 Then X:= G[J,M].F;
If Lt[J].L>0 Then X:= G[M,J].C- G[M,J].F;
If X<A Then A:= X;
Until M= S;
Ford:=False;
End;

Procedure Change(A: Integer);{调整过程}
Var M, J: Integer;
Begin
M:= T;
Repeat
J:=M;M:=Abs(Lt[J].L);
If Lt[J].L<0 Then G[J,M].F:=G[J,M].F-A;
If Lt[J].L>0 Then G[M,J].F:=G[M,j].F+A;
Until M=S;
End;

Procedure Print; {打印最大流及其方案}
VAR
I ,J: Integer;
Max: integer;
Begin
Max:=0;
For I:=1 To N DO
Begin
If G[I,T].F0 Then Max:= Max + G[I,T].F;
For J:= 1 To N Do
If G[I,J].F0 Then Writeln( I, '-> ' ,J,' ' ,G[I,J].F);
End;
Writeln('The Max Stream=',Max);
End;

Procedure Process;{求最大流的主过程}
Var Del:Integer;
Success:Boolean;
Begin
S:=1;T:=N;
Repeat
Success:=Ford(Del);
If Success Then Print
Else Change(Del);
Until Success;
End;

Begin {Main Program}
Init;
Process;
End.

测试数据文件(zdl.txt)如下:

6
0 3 5 0 0 0
0 0 1 4 0 0
0 0 0 0 2 0
0 0 0 0 0 5
0 1 0 3 0 2
0 0 0 0 0 0

运行结果如下:

Graph File=zdl.txt

1->2 3

1->3 2

2->4 3

3->5 2

4->6 3

5->6 2

The Max Stream=5

5.3最小费用最大流及算法

上面的网络，可看作为辅送一般货物的运输网络，此时，最大流问题仅表明运输网络运输货物的能力，但没有考虑运送货物的费用。在实际问题中，运送同样数量货物的运输方案可能有多个，因此从中找一个输出费用最小的的方案是一个很重要的问题，这就是最小代价流所要讨论的内容。

1.最小费用最大流问题的模型
给定网络N=(V，E，c，w，s，t)，每一弧(vi,vj)属于E上，除了已给容量cij外，还给了一个单位流量的费用w(vi,vj)≥O(简记为wij)。所谓最小费用最大流问题就是要求一个最大流f，使得流的总输送费用取最小值。
W(f)=∑wijfij

2.用对偶法解最小费用最大流问题
定义：已知网络N=(V，E，c，w，s，t)，f是N上的一个可行流，p为vs到vt(关于流f)的可增广路径，称W(p)=∑wij（p+）-∑wij（p-）为路径p的费用。
若p*是从vs到vt所有可增广路径中费用最小的路径，则称p*为最小费用可增广路径。
定理：若f是流量为v(f)的最小费用流，p是关于f的从vs到vt的一条最小费用可增广路径，则f经过p调整流量Q得到新的可行流f’(记为f’=f+Q)，一定是流量为v(f)+Q的可行流中的最小费用流。
3.对偶法的基本思路
①取f={0}
②寻找从vs到vt的一条最小费用可增广路径p。
若不存在p，则f为N中的最小费用最大流，算法结束。
若存在p，则用求最大流的方法将f调整成f*，使v(f*)=v(f)+Q，并将f*赋值给f，转②。

4.迭代法求最小费用可增广路径

在前一节中，我们已经知道了最大流的求法。在最小费用最大流的求解中，每次要找一条最小费用的增广路径，这也是与最大流求法唯一不同之处。于是，对于求最小费用最大流问题余下的问题是怎样寻求关于f的最小费用增广路径p。为此，我们构造一个赋权有向图b(f)，它的顶点是原网络N中的顶点，而把N中每一条弧(vi，vj)变成两个相反方向的弧(vi，vj)和(vj，vi)。定义w(f)中的弧的权如下：
如果(fij<cij)，则bij=wij ；如果(fij=cij)，则bij=+oo
如果(fij>0)，则bji=-wij ；如果(fij=cij)，则bji=+oo
于是在网络N中找关于f的最小费用增广路径就等价于在赋权有向图b(f)中，寻求从vs到vt的最短路径。求最短路有三种经典算法，它们分别是Dijkstra算法、Floyd算法和迭代算法(ford算法）。由于在本问题中，赋权有向图b(f)中存在负权，故我们只能用后两种方法求最短路，其中对于本问题最高效的算法是迭代算法。为了程序的实现方便，我们只要对原网络做适当的调整。将原网络中的每条弧(vi，vj)变成两条相反的弧：
前向弧(vi,vj)，其容量cij和费用wij不变，流量为fij；
后向弧(vj,vi)，其容量0和费用-wij，流量为-fij。

事实上，对于原网络的数据结构中，这些单元已存在，在用标号法求最大流时是闲置的。这样我们就不必产生关于流f的有向图b(f)。同时对判断(vi,vj)的流量可否改时，可以统一为判断是否“fij0，则fji=-fij<0=cji。
例2：求输送量最大且费用最小的运输方案？

如下图是一公路网，v1是仓库所在地（物资的起点），v5是某一工地（物资的终点）每条弧旁的两个数字分别表示某一时间内通过该段路的最多吨数和每吨物资通过该段路的费用。



程序如下：

{最小费用最大流参考程序}
program Maxflow_With_MinCost;
const
name1='flow.in';
name2='flow.out';
maxN=100;{最多顶点数}
type
Tbest=record {数组的结构}
value,fa:integer;
end;{到源点的最短距离，父辈}
Nettype=record
{网络邻接矩阵类型}
c,w,f:integer;
{弧的容量，单位通过量费用，流量}
end;
var
Net:array[1..maxN,1..maxN] Of Nettype;
{网络N的邻接矩阵}
n,s,t:integer;{顶点数，源点、汇点的编号}
Minw:integer;{最小总费用}
best:array[1..maxN] of Tbest;{求最短路时用的数组}

procedure Init;{数据读人}
var inf:text;
a,b,c,d:integer;
begin
fillchar(Net,sizeof(Net),0);
Minw:=0;
assign(inf,name1);
reset(inf);
readln(inf,n);
s:=1;t:=n;{源点为1，汇点n}
repeat
readln(inf,a,b,c,d);
if a+b+c+d>0 then
begin
Net[a,b].c:=c;{给弧(a,b)赋容量c}
Net[b,a].c:=0;{给相反弧(b,a)赋容量0}
Net[a,b].w:=d;{给弧(a,b)赋费用d}
Net[b,a].w:=-d;{给相反孤(b，a)赋费用-d}
end;
until a+b+c+d=0;
close(inf);
end;

function Find_Path:boolean;
{求最小费用增广路函数,若best[t].valueMaxInt,
则找到增广路，函数返回true，否则返回false}
var Quit:Boolean;
i,j:Integer;
begin
for i:=1 to n do best[i].value:=Maxint;best[s].value:=0;
{寻求最小费用增广路径前，给best数组赋初值}
repeat
Quit:=True;
for i:=1 to n do
if best[i].Value < Maxint then
for j:=1 to n do
if (Net[i,j].f < Net[i,j].c) and
(best[i].value + Net[i,j].w <
best[j].value) then
begin
best[j].value:=best[i].value + Net[i,j].w;
best[j].fa := i;
Quit:= False;
end;
until Quit;
if best[t].value<Maxint then find_path:=true else find_path:=false;
end;

procedure Add_Path;
var i,j: integer;
begin
i:= t;
while i s do
begin
j := best[i].fa;
inc(Net[j,i].f); {增广路是弧的数量修改，增量1}
Net[i,j].f:=-Net[j,i].f;{给对应相反弧的流量赋值-f}
i:=j;
end;
inc(Minw,best[t].value); {修改最小总费用的值}
end;

procedure Out;{输出最小费用最大流的费用及方案}
var ouf: text;
i,j: integer;
begin
assign(ouf,name2);
rewrite(ouf);
writeln(ouf,'Min w = ',Minw);
for i := 1 to n do
for j:= 1 to n do
if Net[i,j].f > 0 then
writeln(ouf,i, ' -> ',j,': ',
Net[i,j].w,'*',Net[i,j].f);
close(ouf);
end;

Begin {主程序}
Init;
while Find_Path do Add_Path;
{当找到最小费用增广路，修改流}
Out;
end.

flow.in如下：

5
1 2 10 4
1 3 8 1
2 4 2 6
2 5 7 1
3 2 5 2
3 4 10 3
4 5 4 2
0 0 0 0

运行结果flow.out如下：

Min w = 55
1 -> 2: 4*3
1 -> 3: 1*8
2 -> 5: 1*7
3 -> 2: 2*4
3 -> 4: 3*4
4 -> 5: 2*4

2.网络与网络流

给一个有向图N=(V，E)，在V中指定一点，称为源点(记为vs，和另一点，称为汇点(记为vt)，其余的点叫中间点，对于E中每条弧(vi，vj)都对应一个正整数c(vi，vj)≥O(或简写成cij)，称为f的容量，则赋权有向图N=(V，E，c，vs，vt)称为一个网络。如图5-1所给出的一个赋权有向图N就是一个网络，指定v1是源点，v4为汇点，弧旁的数字为cij。 所谓网络上的流，是指定义在弧集合E上一个函数f={f(vi，vj)}，并称f(vi，vj)为弧(vi，vj)上的流量(下面简记为fij)。如图5-2所示的网络N，弧上两个数，第一个数表示容量cij，第二个数表示流量fij。

3.可行流与最大流
在运输网络的实际问题中，我们可以看出，对于流有两个显然的要求：一是每个弧上的流量不能超过该弧的最大通过能力(即弧的容量)；二是中间点的流量为0，源点的净流出量和汇点的净流入量必相等且为这个方案的总输送量。因此有：
(1)容量约束：0≤fij≤cij，(vi,vj)∈E，
(2)守恒条件
对于中间点：流入量=流出量；对于源点与汇点：源点的净流出量vs(f)=汇点的净流入量（-vt(f)）
的流f，称为网络N上的可行流，并将源点s的净流量称为流f的流值v(f)。
网络N中流值最大的流f*称为N的最大流。

4.可增广路径
所谓可增广路径，是指这条路径上的流可以修改，通过修改，使得整个网络的流值增大。

设f是一个可行流，P是从源点s到汇点t的一条路，若p满足下列条件：
(1)在p上的所有前向弧(vi→vj)都是非饱和弧，即0≤fij<cij
(2)在p上的所有后向弧(vi←vj)都是非零弧，即0<fij≤cij
则称p为(关于可行流f的)一条可增广路径。

5.最大流定理
当且仅当不存在关于f*的增广路径，可行流f*为最大流。



5. 2 最大流算法

算法思想:最大流问题实际上是求一可行流{fij}，使得v(f达到最大。若给了一个可行流f，只要判断N中有无关于f的增广路径，如果有增广路径，改进f， 得到一个流量增大的新的可行流；如果没有增广路径，则得到最大流。
1.寻求最大流的标号法(Ford,Fulkerson)
从一个可行流(一般取零流)开始，不断进行以下的标号过程与调整过程，直到找不到关于f的可增广路径为止。
(1)标号过程
在这个过程中，网络中的点分为已标号点和未标号点，已标号点又分为已检查和未检查两种。每个标号点的标号信息表示两个 部分：第一标号表明它的标号从哪一点得到的，以便从vt开始反向追踪找出也增广路径；第二标号是为了表示该顶点是否已检查过。
标号开始时，给vs标上(s，0)，这时vs是标号但末检查的点，其余都是未标号的点，记为(0，0)。
取一个标号而未检查的点vi，对于一切未标号的点vj：
A．对于弧(vi，vj)，若fij<cij，则给vj标号(vi，0)，这时，vj点成为标号而未检查的点。
B．对于弧(vi，vj)，若fji>0，则给vj标号(-vi，0)，这时，vj点成为标号而未检查的点。
于是vi成为标号且已检查的点，将它的第二个标号记为1。重复上述步骤，一旦vt被标上号，表明得到一条从vi到vt的增广路径p，转入调整过程。
若所有标号都已检查过去，而标号过程进行不下去时，则算法结束，这时的可行流就是最大流。
(2)调整过程
从vt点开始，通过每个点的第一个标号，反向追踪，可找出增广路径P。例如设vt的第一标号为vk(或-vk)，则弧(vk，vt)(或 相应地(vt，vk))是p上弧。接下来检查vk的第一标号，若为vi(或-vi)，则找到(vi，vk)(或相应地(vk，vi))。再检查vi的第一 标号，依此类推，直到vs为止。这时整个增广路径就找到了。在上述找增广路径的同时计算Q：
Q=min{min(cij-fij)，minf*ij}
对流f进行如下的修改：
f'ij = fij+Q (vi，vj)∈ P的前向弧的集合
f'ij = fij-Q (vi，vj)∈ P的后向弧的集合
f'ij = f*ij (vi，vj)不属于P的集合
接着，清除所有标号，对新的可行流f’，重新进入标号过程。

编辑本段定义
图论中的一种理论与方法，研究网络上的一类最优化问题 。1955年 ，T.E. 哈里斯在研究铁路最大通量时首先提出在一个给定的网络上寻求两点间最大运输量的问题。1956年，L.R. 福特和 D.R. 富尔克森等人给出了解决这类问题的算法，从而建立了网络流理论。所谓网络或容量网络指的是一个连通的赋权有向图 D＝ （V、E、C） ， 其中V 是该图的顶点集，E是有向边(即弧)集，C是弧上的容量。此外顶点集中包括一个起点和一个终点。网络上的流就是由起点流向终点的可行流，这是定义在网络上的非负函数，它一方面受到容量的限制，另一方面除去起点和终点以外，在所有中途点要求保持流入量和流出量是平衡的。如果把下图看作一个公路网，顶点v1…v6表示6座城镇，每条边上的权数表示两城镇间的公路长度。现在要问 ：若从起点v1将物资运送到终点v6去 ，应选择那条路线才能使总运输距离最短�这样一类问题称为最短路问题 。 如果把上图看作一个输油管道网 ， v1 表示发送点，v6表示接收点，其他点表示中转站 ，各边的权数表示该段管道的最大输送量。现在要问怎样安排输油线路才能使从v1到v6的总运输量为最大。这样的问题称为最大流问题。
最大流理论是由福特和富尔克森于 1956 年创立的 ，他们指出最大流的流值等于最小割(截集)的容量这个重要的事实，并根据这一原理设计了用标号法求最大流的方法，后来又有人加以改进，使得求解最大流的方法更加丰富和完善 。最大流问题的研究密切了图论和运筹学，特别是与线性规划的联系，开辟了图论应用的新途径。
目前网络流的理论和应用在不断发展，出现了具有增益的流、多终端流、多商品流以及网络流的分解与合成等新课题。网络流的应用已遍及通讯、运输、电力、工程规划、任务分派、设备更新以及计算机辅助设计等众多领域。

网络流算法
一、网络流的基本概念
先来看一个实例。
现在想将一些物资从S运抵T，必须经过一些中转站。连接中转站的是公路，每条公路都有最大运载量。如下图：
每条弧代表一条公路，弧上的数表示该公路的最大运载量。最多能将多少货物从S运抵T？
这是一个典型的网络流模型。为了解答此题，我们先了解网络流的有关定义和概念。
若有向图G=(V,E)满足下列条件：
1、 有且仅有一个顶点S，它的入度为零，即d-(S) = 0，这个顶点S便称为源点，或称为发点。
2、 有且仅有一个顶点T，它的出度为零，即d+(T) = 0，这个顶点T便称为汇点，或称为收点。
3、 每一条弧都有非负数，叫做该边的容量。边(vi, vj)的容量用cij表示。
则称之为网络流图，记为G = (V, E, C)
譬如图5-1就是一个网络流图。
1．可行流
对于网络流图G，每一条弧(i,j)都给定一个非负数fij，这一组数满足下列三条件时称为这网络的可行流，用f表示它。
1、 每一条弧(i,j)有fij≤cij。
2、 除源点S和汇点T以外的所有的点vi，恒有：
该等式说明中间点vi的流量守恒，输入与输出量相等。
3、 对于源点S和汇点T有：
这里V(f)表示该可行流f的流量。
例如对图5-1而言，它的一个可行流如下：
流量V(f) = 5。
2．可改进路
给定一个可行流f=。若fij = cij，称<vi, vj>为饱和弧；否则称<vi, vj>为非饱和弧。若fij = 0，称<vi, vj>为零流弧；否则称<vi, vj>为非零流弧。
定义一条道路P，起点是S、终点是T。把P上所有与P方向一致的弧定义为正向弧，正向弧的全体记为P+；把P上所有与P方向相悖的弧定义为反向弧，反向弧的全体记为P-。
譬如在图5-1中，P = (S, V1, V2, V3, V4, T)，那么
P+ = {<S, V1>, <V1, V2>, <V2, V3>, <V4, T>}
P- = {<V4, V3>}
给定一个可行流f，P是从S到T的一条道路，如果满足：
那么就称P是f的一条可改进路。（有些书上又称：可增广轨）之所以称作“可改进”，是因为可改进路上弧的流量通过一定的规则修改，可以令整个流量放大。具体方法下一节会重点介绍，此不赘述。
3．割切
要解决网络最大流问题，必须先学习割切的概念和有关知识。
G = (V, E, C)是已知的网络流图，设U是V的一个子集，W = V\U，满足S U，T W。即U、W把V分成两个不相交的集合，且源点和汇点分属不同的集合。
对于弧尾在U，弧头在W的弧所构成的集合称之为割切，用（U，W）表示。把割切（U，W）中所有弧的容量之和叫做此割切的容量，记为C（U，W），即：
例如图5-1中，令U = {S, V1}，则W = {V2, V3, V4, T}，那么
C(U, W) = <S, V2> + <V1, V2> + <V1, V3>+<V1, V4>=8+4+4+1=17
定理：对于已知的网络流图，设任意一可行流为f，任意一割切为(U, W)，必有：V(f) ≤ C(U, W)。
通俗简明的讲：“最大流小于等于最小割”。这是“流理论”里最基础最重要的定理。整个“流”的理论系统都是在这个定理上建立起来的，必须特别重视。
下面我们给出证明。
网络流、可改进路、割切都是基础的概念，应该扎实掌握。它们三者之间乍一看似乎风马牛不相干，其实内在联系是十分紧密的。
二、求最大流
何谓最大流？首先它必须是一个可行流；其次，它的流量必须达到最大。这样的流就称为最大流。譬如对图5-1而言，它的最大流如下：
下面探讨如何求得最大流。
在定义“可改进路”概念时，提到可以通过一定规则修改“可改进路”上弧的流量，可以使得总流量放大。下面我们就具体看一看是什么“规则”。
对可改进路P上的弧<vi, vj>，分为两种情况讨论：
第一种情况：<vi, vj>∈P+，可以令fij增加一个常数delta。必须满足fij + delta ≤ cij，即delta ≤ cij – fij。
第二种情况：<vi, vj>∈P-，可以令fij减少一个常数delta。必须满足fij - delta ≥ 0，即delta ≤ fij
根据以上分析可以得出delta的计算公式：
因为P+的每条弧都是非饱和弧，P-的每条弧都是非零流弧，所以delta > 0。
容易证明，按照如此规则修正流量，既可以使所有中间点都满足“流量守恒”（即输入量等于输出量），又可以使得总的流量有所增加（因为delta > 0）。
因此我们对于任意的可行流f，只要在f中能找到可改进路，那么必然可以将f改造成为流量更大的一个可行流。我们要求的是最大流，现在的问题是：倘若在f中找不到可改进路，是不是f就一定是最大流呢？
答案是肯定的。下面我们给出证明。
定理1 可行流f是最大流的充分必要条件是：f中不存在可改进路。
证明：
首先证明必要性：已知最大流f，求证f中不存在可改进路。
若最大流f中存在可改进路P，那么可以根据一定规则（详见上文）修改P中弧的流量。可以将f的流量放大，这与f是最大流矛盾。故必要性得证。
再证明充分性：已知流f，并且f中不存在可改进路，求证f是最大流。
我们定义顶点集合U, W如下：
（a） S∈U，
（b） 若x∈U，且fxy<cxy，则y∈U;
若x∈U，且fyx>0，则y∈U。
（这实际上就是可改进路的构造规则）
（c） W = V \ U。
由于f中不存在可改进路，所以T∈W；又S∈U，所以U、W是一个割切（U, W）。
按照U的定义，若x∈U，y∈W，则fxy = cxy。若x∈W，y∈U，则fxy = 0。
所以，
又因 v(f)≤C(U,W)
所以f是最大流。得证。
根据充分性证明中的有关结论，我们可以得到另外一条重要定理：
最大流最小割定理：最大流等于最小割，即max V(f) = min C(U, W)。
至此，我们可以轻松设计出求最大流的算法：
step 1. 令所有弧的流量为0，从而构造一个流量为0的可行流f（称作零流）。
step 2. 若f中找不到可改进路则转step 5；否则找到任意一条可改进路P。
step 3. 根据P求delta。
step 4. 以delta为改进量，更新可行流f。转step 2。
step 5. 算法结束。此时的f即为最大流。
三、最小费用最大流
1．问题的模型
流最重要的应用是尽可能多的分流物资，这也就是我们已经研究过的最大流问题。然而实际生活中，最大配置方案肯定不止一种，一旦有了选择的余地，费用的因素就自然参与到决策中来。
图5-8是一个最简单的例子：弧上标的两个数字第一个是容量，第二个是费用。这里的费用是单位流量的花费，譬如fs1=4，所需花费为3*4=12。
容易看出，此图的最大流（流量是8）为：fs1 = f1t = 5, fs2 = f2t = 3。所以它的费用是：3*5+4*5+7*3+2*3 = 62。
一般的，设有带费用的网络流图G = (V, E, C, W)，每条弧<Vi, Vj>对应两个非负整数Cij、Wij，表示该弧的容量和费用。若流f满足：
(a) 流量V(f)最大。
(b) 满足a的前提下，流的费用Cost(f) = 最小。
就称f是网络流图G的最小费用最大流。
2．算法设计
我们模仿求最大流的算法，找可改进路来求最小费用最大流。
设P是流f的可改进路，定义 为P的费用（为什么如此定义？）。如果P是关于f的可改进路中费用最小的，就称P是f的最小费用可改进路。
求最小费用最大流的基本思想是贪心法。即：对于流f，每次选择最小费用可改进路进行改进，直到不存在可改进路为止。这样的得到的最大流必然是费用最小的。
算法可描述为：
step 1. 令f为零流。
step 2. 若无可改进路，转step 5；否则找到最小费用可改进路，设为P。
step 3. 根据P求delta（改进量）。
step 4. 放大f。转step 2。
step 5. 算法结束。此时的f即最小费用最大流。
至于算法的正确性，可以从理论上证明。读者可自己思考或查阅有关运筹学资料。
2．最小费用可改进路的求解
求“最小费用可改进路”是求最小费用最大流算法的关键之所在，下面我们探讨求解的方法。
设带费用的网络流图G = (V, E, C, W)，它的一个可行流是f。我们构造带权有向图B = (V’, E’)，其中：
1、 V’ = V。
2、 若<Vi, Vj>∈E，fij<Cij，那么<Vi, Vj>∈E’，权为Wij。
若<Vi, Vj>∈E，fij>0，那么<Vj, Vi>∈E’，权为-Wij。
显然，B中从S到T的每一条道路都对应关于f的一条可改进路；反之，关于f的每条可改进路也能对应B中从S到T的一条路径。即两者存在一一映射的逻辑关系。
故若B中不存在从S到T的路径，则f必然没有可改进路；不然，B中从S到T的最短路径即为f的最小费用可改进路。
现在的问题变成：给定带权有向图B = (V’, E’)，求从S到T的一条最短路径。
考虑到图中存在权值为负数的弧，不能采用Dijkstra算法；Floyd算法的效率又不尽如人意——所以，这里采用一种折衷的算法：迭代法。
设Short[k]表示从S到k顶点的最短路径长度；从S到顶点k的最短路径中，顶点k的前趋记为Last[k]。那么迭代算法描述如下：（为了便于描述，令n = |V’|，S的编号为0，T的编号为n+1）
step 1. 令Short[k]  +∞（1≤k≤n+1），Short[0]  0。
step 2. 遍历每一条弧<Vk, Vj>。若Short[k] + <k, j> < Short[j]，则令Short[j]  Short[k] + <k, j>，同时Last[j]  k。倘不存在任何一条弧满足此条件则转step 4。
step 3. 转step 2.
step 4. 算法结束。若Short[n + 1]= +∞，则不存在从S到T的路径；否则可以根据Last记录的有关信息得到最短路径。
一次迭代算法的时间复杂度为O(kn2)，其中k是一个不大于n的变量。在费用流的求解过程中，k大部分情况下都远小于n。
3．思维发散与探索
1）可改进路费用：“递增！递增？”
设f从零流到最大流共被改进了k次，每i次选择的可改进路的费用为pi，那么会不会有p1≤p2≤p3≤……≤pk呢？
2）迭代法：“小心死循环！嘿嘿……”
迭代法会出现死循环吗？也就是说，构造的带权有向图B中会存在负回路吗？
3）费用：“你在乎我是负数吗？”
网络流图中的费用可以小于零吗？
4）容量：“我管的可不仅是弧。”
网络流图中的“容量”都是对弧而言的，但若是给每个顶点也加上一个容量限制：即通过此顶点的流量的上限；任务仍然是求从S到T的最小费用最大流。你能解决吗？
四、有上下界的最大流
上面讨论的网络流都只对每条弧都限定了上界（其实其下界可以看成0），现在给每条弧<Vi, Vj>加上一个下界限制Aij（即必须满足Aij≤fij）。
例如图5-9：
弧上数字对第一个是上界，第二个是下界。若是撇开下界不看，此图的最大流如图5-10(a)所示，流量是6；但若是加入了下界的限制，它的最大流量就只有5了，具体方案见图5-10(b)。
那么有上下界的网络最大流怎么求呢？
一种自然的想法是去掉下界，将其转化为只含上界的网络流图。这种美好的愿望是可以实现的。具体方法如下：
设原网络流图为G = (V, E, C, A)，构造不含下界的网络流图G’ = (V’, E’, C’)：
1、 V’ = V∪{S’, T’}
2、 对每个顶点x，令 ，若h-(x)≠0，就添加一条弧<S’, x>，其上界为h-(x)。
3、 对每个顶点x，令 ，若h+(x)≠0，就添加一条弧<x, T’>，其上界为h+(x)。
4、 对于任何<Vi, Vj>∈E，都有<Vi, Vj>∈E’，其上界C’ij = Cij – Aij。
5、 新增<T, S>∈E’，其上界CTS = +∞。
在G’中以S’为源点、T’为汇点求得最大流f’。若f’中从S’发出的任意一条弧是非饱和弧，则原网络流图没有可行流。否则可得原图的一个可行流f = f’ + A，即所有的fij = f’ij + Aij。（其正确性很容易证明，留给读者完成）
然后再求可改进路（反向弧<Vi, Vj>必须满足fij≥Aij，而非fij≥0），不断放大f，直到求出最大流。
我们看到，上几节所讨论的一种可行网络流实际上是{Aij = 0}的一种特殊网络流，这里提出的模型更一般化了。解决一般化的复杂问题，我们采取的思路是将其转化为特殊的简单问题，加以研究、推广，进而解决。这是一种重要的基本思想：化归——简单有效。基于这种思想，请读者自行思考解决：
1、 有上下界的最小流。
2、 有上下界的最小费用最大流。
五、多源点、多汇点的最大流
已知网络流图有n个源点S1、S2、……、Sn，m个汇点T1、T2、……、Tm，，求该图的最大流。这样的问题称为多源点、多汇点最大流。
它的解决很简单：
1、 增设一个“超级源”S’，对每个源点Si，新增弧<S’, Si>，容量为无穷大。
2、 增设一个“超级汇”T’，对每个汇点Ti，新增弧<Ti, T’>，容量为无穷大。
3、 以S’为源点、T’为汇点求最大流f。
4、 将f中的S’和T’去掉，即为原图的最大流。
算法正确性显然。
六、顶点有容量限制的最大流
上一节已经提出了这个问题，即对于进出每个顶点的流量也规定一个上限，这样的最大流如何求？
既然我们已经解决了“边限制”问题，现在何不把“点限制”问题转化为“边限制”呢？具体办法如下：
1、 对除源点和汇点之外的每个顶点i拆分成两个顶点i’和i’’。新增一条弧<i’, i’’>，其容量为点i的流量限制。
2、 对于原图中的弧<i, j>，我们将其变换成<i’’, j’>。
3、 对变换后的图求最大流即可。
这里我们又一次运用到了化归的思想：将未知的“点限制”问题转化为已知的“边限制”问题。
七、网络流与二部图的匹配
{二部图和匹配的定义可参见本书专门介绍二部图匹配的章节}
设二部图为G = (X, Y, E)。
增设点S’，对于所有i∈X，新增弧<S’, Xi>，容量为1；增设点T’，对于所有i∈Y，新增一条弧<Yi, T’>，容量也为1。原图中所有的弧予以保留，容量均为+∞。对新构造出来的网络流图以S’为源点、T’为汇点求最大流：流量即为最大匹配数；若弧<Xi, Yj>（i∈X，j∈Y）的流量非零，它就是一条匹配边。
二部图最大匹配问题解决。
那么二部图的最佳匹配问题又如何？
仍然按照上述方法构图。同时令原图中弧的费用保持不变；新增弧的费用置为0。然后以S’为源点、T’为汇点求最小费用最大流即可。最大流的费用即为原二部图最佳匹配的费用。

复制的我快吐了~

---

汉源县19695719686： 网络流 - 搜狗百科？
归些希路： 编辑本段定义 图论中的一种理论与方法,研究网络上的一类最优化问题 .1955年 ,T.E. 哈里斯在研究铁路最大通量时首先提出在一个给定的网络上寻求两点间最大运输量的问题.1956年,L.R. 福特和 D.R. 富尔克森等人给出了解决这类问题的...

汉源县19695719686： 算法中的网络流是什么意思?请简单介绍一下啊? - ？
归些希路： 现在想将一些物资从S运抵T,必须经过一些中转站.连接中转站的是公路,每条公路都有最大运载量.如下图: 每条弧代表一条公路,弧上的数表示该公路的最大运载量.最多能将多少货物从S运抵T? 这是一个典型的网络流模型.为了解答...

汉源县19695719686： 在线等,急,谁知道网络流的定义,送上20分我想知道网络流的定义, ？
归些希路： 网络流:图论中的一种理论与方法,研究网络上的一类最优化问题 .1955年 ,T.E. 哈里斯在研究铁路最大通量时首先提出在一个给定的网络上寻求两点间最大运输量的...

汉源县19695719686： 什么叫网络流行语 - ？
归些希路： 网络流行语一般指网络语言,指产生并运用于网络的语言.网络流行语与网络语言为同义词,指从网络中产生或应用于网络交流的一种语言,包括中英文字母、标点、符号、拼音、图标(图片)和文字等多种组合.这种组合,往往在特定的网络...

汉源县19695719686： 网络流的最大流和最小流是什么算法 - ？
归些希路： 首先是网络流中的一些定义:V表示整个图中的所有结点的集合.E表示整个图中所有边的集合.G = (V,E) ,表示整个图.s表示网络的源点,t表示网络的汇点.对于每条边(u,v),有一个容量c(u,v) (c(u,v)>=0),如果c(u,v)=0,则表示(u,v)不存在...

汉源县19695719686： 什么是增广路?网络流的.给个详细清楚的定义和解释,搜资料的免了 - ？
归些希路： 2.网络与网络流 给一个有向图N=(V,E),在V中指定一点,称为源点(记为vs,和另一点,称为汇点(记为vt),其余的点叫中间点,对于E中每条弧(vi,vj)都对应一个正整数c(vi,vj)≥O(或简写成cij),称为f的容量,则赋权有向图N=(V,E,c,vs,vt)称...

汉源县19695719686： 最近的网络流行语有哪些? - ？
归些希路： 【知道你过得不好,我也就安心了】 【这位帅哥,你好像我下一任男友】 【伯母你好,我是你儿子的男朋友】 【不要叫我宅女,请叫我居里夫人】 【真羡慕你这么年轻就认识我了.】 【最近总是失眠,16小时就醒一次.】 【大叔,帮我在配...

汉源县19695719686： 网络流行语是什么? - ？
归些希路： 年度十大网络流行语: 【最无耻】一个非常艰难的决定. 【最炫耀】我爸是李刚. 【最主流】给力. 【最佳美术】神马都是浮云. 【最佳汉语语法】我勒个去. 【最佳修辞】杯具. 【最感同身受】蛋疼. 【最文明】你妹. 【最废话】你懂的. 【最简洁有力】擦.

汉源县19695719686： 2014年十大网络流行语的词汇出处 - ？
归些希路： 且行且珍惜 出处:2014年3月底,演员文章首次回应“出轨门”承认了“劈腿”传闻.3分钟后,马伊琍在微博写了句“恋爱虽易,婚姻不易,且行且珍惜”回应.于是“且行且珍惜”开始流行. 也引得网友纷纷跟风造句,延伸出了诸如减肥版...