Section-5 Network Flow
第5节 网络流
网络流(Network Flow)/最大流(Max Flow)
一片区域中有很多个城市,彼此间用公路相连,每条公路有自己能够运输的最大重量。城市A生产货物,城市B消费货物,通过公路将城市A产生的货物运送到城市B消费,经过其他城市。
上图是一个有向图DG=<V,E>,假设城市A每天产生的货物数量无穷多,城市B每天能够消费的货物数量无穷多,每条边的数字表示该公路每天最多运送的货物数量,红色弧边的数字表示当整个运输网络充满时一条公路实际每天运送的货物数量。所有的红色弧边组成一组解,表示城市A,B之间每天最多能够运输的货物。显然这样的解可以有多个。
网络流(Network Flow)是指在一个每条边都有容量(Capacity)的有向图分配流,使一条边的流量不会超过它的容量。运筹学中通常将有向图称为网络,顶点称为节点(Node)而边称为弧(Arc)。一道流必须匹配一个结点的进出的流量相同的限制,除非这是一个源点(s)──有较多向外的流,或是一个汇点(t)──有较多向内的流。一个网络可以用来模拟道路系统的交通量、管中的液体、电路中的电流或类似一些东西在一个结点的网络中游动的任何事物。上面两个城市之间运输货物的例子就是典型的网络流问题,每个城市是一个节点,城市A是源点s,城市B是汇点t,公路是弧。
有向图DG=<V,E>的边eu,v∈E都有一个容量cu,v(若eu,v∈/E则认为cu,v=0),设源点为s汇点为t。一道网络流是对于有向图DG中所有节点u,v都有以下特性的实数函数:
f:V×V→R 满足:
(1) 容量限制(Capacity Constraints):f(u,v)≤c(u,v),表示一条边的流不能超过其容量;
(2) 反对称(Skew Symmetry):f(u,v)=−f(v,u),表示由u到v的净流必须是由v到u的净流的相反;
(3) 流守恒(Flow Conservation):除非u=s或u=t,否则∑w∈Vf(u,w)=0,表示节点u的净流是0,除了s和t;
(4) 网络流中除了源点汇点外的任意节点,都满足流守恒:
(u,v)∈E∑f(u,v)=(v,z)∈E∑f(v,z) 表示对于除源点汇点外任意节点u,v,z∈V\s,t,所有流向节点v的流等于从节点v流出的流;
(5) 若由u到v有4单位的流,而由v到u有3单位的流,那么实际f(u,v)=1,f(v,u)=−1;
(6) 边的剩余容量(Residual Capacity)是
cf(u,v)=c(u,v)−f(u,v) 边的剩余容量定义了剩余网络(Residual Network)Gf=<V,Ef>,表示该网络的可用容量。
网络中的增广路径是剩余网络中的一条路径(u1,u2,…,un),其中u1是源点s,un是汇点t,且其中每条边的剩余容量都满足cfui,ui+1>0(其中1≤i<i+1≤n)。
最大流(Max Flow)是单源点、单汇点、边的容量为正整数的网络,其剩余网络无法找出更多增广路径的流。
Introduction To Algorithms
图论术语