网络流算法及例解.ppt

第六章 网络流图问题 §1 网络流图问题和最大流 §2 割切 §3 Ford-Fulkerson最大流最小割切定理 §4 2F最大流最小割切标号算法 §5 Edmonds-Karp修正算法，Dinic算法 §1 网络流图问题和最大流 把一种产品从产地通过铁路或公路网运往市场，交通网络中每一段的运输能力有一定限度，问如何安排，使得运输最快？ 这个问题在运输调度工作中是重要内容之一，同时也是运筹学许多问题的模型。 §1 网络流图问题和最大流-例 §1 网络流图问题和最大流－1 定义：带权的有向图G=(V,E)，满足以下条件，则称为网络流图(flow network)。 （1）仅有一个入度为0的顶点s，称s为源点(source)或发点； （2）仅有一个出度为0的顶点t，称S为汇点(sink)或沟或收点； （3）每条边的权值都为非负数，称为该边的容量，记作c(i,j)。 §1 网络流图问题和最大流-例 下图所示就是一个网络流图： §1 网络流图问题和最大流-2 对于网络流图G，每条边都给定一个非负数fij，这组数满足下面条件，称为网络的容许流(flow)，记作f。 （1）0≤fij≤ c(i,j)； （2）除源点s和汇点t，其余顶点vi恒有： ∑fij＝∑ fki j k 即每个点流入和流出量相同； （3）对于源点s和汇点t有： ∑fsi＝∑ fjt＝w i j w称为网络流的流量。 §1 网络流图问题和最大流-3 下图所示就是一个网络流图上的容许流： §1 网络流图问题和最大流-4 对于下图，根据各点能量守恒的关系，可分别得下列各式： fsa+fsb+fsc=w (1) fat+fbt+fdt=w (2) fsa+fba＝fat+fab (3) fsb+fcb+fab＝fba+fbt+fbd (4) fsc＝fcb+fcd (5) fbd+fcd＝fdt (6) 0≤fsa≤4， 0≤fsb≤3， 0≤fsc≤4， 0≤fab≤2， 0≤fba≤3， 0≤fat≤3， 0≤fbt≤2， 0≤fbd≤2， 0≤fcb≤1， 0≤fcd≤2， 0≤fdt≤2， w≥0 §2 割切 图G=(V,E)是已知的网络流图，假设S是V的一个子集，而且S满足以下条件： （1）s∈S （2）t∈S §2 割切-2 在边集(S, )中，把从S到 的边的容量之和称为割切的容量，记作C(S, ) ，即 C(S, )= §2 割切-定理6.1 网络容许流量和切割容量之间存在下述关系： 定理6.1：网络流的最大流量小于等于的任意的割切容量，即：max w≤ C(S, )。 §2 割切-定理6.1证明 当i点既不是源点s，也不是汇点t的任意点时，恒有：∑fij－∑fji＝0 (1) j∈V j∈V 但i为源点s时有∑fsj＝w (2) j∈V 从(1)、(2)