图论及算法充：最大流.doc

《图论及算法充：最大流.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、图论及算法最大流问题1概念1.1运输网络一个赋权有向图，若满足下列条件，称为运输网络。①连通，无自回路；②恰有一个结点入度为0的结点，称为源点；③恰有一个结点出度为0的结点，称为汇点；④每条弧的权称为该弧的容量，弧的容量记作。示例：弧的权：道路的运输容量。1.2流为研究网络的运输容量，提出“流”的概念。流：代表一个合理的运输方案。流中的弧值：代表在该弧上的运输量。运输网络中流的定义：对每条弧给定一个非负实数，满足下列条件：①若不存在，②对每一条弧，有③除源点、汇点外，对每一个结点，有。即对于结点j，所有流进量等于流出量。示例：流的值：

2、8流的值：14流的值：整个运输方案的运输量。1.3割设N=(V,E)是一个运输网络，S是V的子集，且源点∈S，汇点∈V-S。可称S为源子集，V-S为目标子集。割：弧尾在S、弧头在V-S的弧集，用(S,V-S)表示。即是源子集和目标子集交界处的弧集。割的容量C(S，V-S)：设：C1=弧尾在S、弧头在V-S的所有弧的容量和。C2=弧尾在V-S、弧头在S的所有弧的容量和。则：C(S,V-S)=C1-C2C1=9C2=1C(S,V-S)=8C1=14C2=0C(S,V-S)=14定理：在运输网络中，流的值=割的容量。2增载轨算法（Ford，F

3、ulkerson，1956）2.1源点到汇点的道路定义从源到汇的道路。道路记作v0,v1,…,vm-1,vm。性质：对于，或是网络的一条弧。前向边：与道路方向一致的有向边。后向边：与道路方向相反的有向边。2.2标记法的标记过程设为道路的运输容量，为道路上的运输量。标记过程如下：①给源点标记(-,∞)，表示从源点流出的流量可以任意。δx=∞②选择一个已标记结点x，对与x邻接的所有未标记结点y按下列规则处理：①若，令δy＝min{,δx}，给结点ｙ以标记(+x,δy)（即前向边未饱和）②若，令δy＝min{,δx}，给结点ｙ以标记(-x,δ

4、y)（即后向边有回流）③④⑤重复步骤㈡，直到收点ｚ被标记：说明存在一条可增广道路，转向增广过程；若ｚ点不能获得标记，且不存在其他可标记的结点：所得的流是最大流。3、标记法的增广过程㈠令u=z。㈡若u的标记为(+v,δu)，则f(v,u)←f(v,u)+δz若u的标记为(-v,δu)，则f(u,v)←f(u,v)-δz㈢若v=a，则把全部标记去掉转向标记过程；否则，令u=v并回到增广过程第㈡步。3示例3.1示例13.2示例2