第六章 图与网络最大流问题运筹学基础及其应用胡运权第五版.ppt

1、2020年9月4日星期五,基本概念,容量：在某时期内弧(i，j)上的最大通过能力。记为C (i，j)或Cij 在上图中，C12=4，C138，C234等，怎样安排运输方案，才能使在某一时期内从v1运到v6的物资最多，这样的问题就是最大流问题，,网络中所有流起源于一个叫做发点的节点（源）,所有的流终止于一个叫做收点的节点,其余所有的节点叫做中间点（转运点）,通过每一条弧的流只允许沿着弧的箭头方向流动,目标是使得从发点到收点的总流量最大,2020年9月4日星期五,流量：弧(i，j)的实际通过量，记为f (i，j)或f ij,可行流：如果f ij满足： 1.对于所有弧(i，j)有0f ijCij 2

2、.对于发点vs有：,3.对于收点vt有：,则称流量集合f ij为网络的一个可行流，简记为 f , v称为可行流的流量或值，记为v(f).,以下假设网络是一个简单连通图。,4.对于中间点点vm有：,2020年9月4日星期五,截集 将图G（V，E）的点集分割成两部分,称为一个截集，截集中所有弧的容量之和称为截集的截量。,下图所示的截集为,请看演示,2020年9月4日星期五,又如下图所示的截集为,上图所示的截集为,所有截量中此截量最小且等于最大流量，此截集称为最小截集。,【定理】最大流量等于最小截集的截量。,2020年9月4日星期五,链：从发点到收点的一条路线（弧的方向不一定都同向）称为链。从发点到

3、收点的方向规定为链的方向。,前向弧：与链的方向相同的弧称为前向弧。,后向弧：与链的方向相反的弧称为后向弧。,增广链 设 f 是一个可行流，如果存在一条从vs到vt的链，满足：,1.所有前向弧上fijCij,2.所有后向弧上fij0,则该链称为增广链,容量,流量,2020年9月4日星期五,【定理】设网络G的一个可行流f，如果存在一条从vs到vt的增广链，那么就可改进一个值更大的可行流f1，并且val f1val f,【证】设val fv,对改进的可行流f1 ：,2020年9月4日星期五,最大流的标号算法,步骤 1. 找出第一个可行流，例如所有弧的流量fij =0,2. 用标号的方法找一条增广链

4、A1：发点标号（），,A2：选一个点 vi 已标号并且另一端未标号的弧沿着某条链向收点检查： 如果弧的方向向前并且有fij0，则vj标号（fji),当收点不能得到标号时，说明不存在增广链，计算结束。,当收点已得到标号时，说明已找到增广链。,【定理】可行流是最大流当且仅当不存在发点到收点的增广链,2020年9月4日星期五,4. 调整流量,得到新的可行流，去掉所有标号，从发点重新标号寻找增广链，直到收点不能标号为止。,3. 依据vi 的第一个标号反向跟踪得到一条增广链； 依据vi 的第二个标号求最小值得到调整量,2020年9月4日星期五,4,2,2,0,2,2,2,2,0,4,6,2,1,7,【例】求下图v1 到v6 的最大流及最大流量,【解】1. 通过观察得到初始可行流,2.标号,3. 得到增广链,2020年9月4日星期五,4,2,1,1,3,2,2,3,0,4,2,2,3,得到增广链,4.求调整量,5.调整可行流,去掉所有标号，重新标号,2020年9月4日星期五,求调