6-3网络最大流.pptVIP

§5 网络最大流 问题的提出 研究网络的流量是很有意义的，例如交通系统中的车流、金融系统中的现金流、控制系统中的信息流、供水系统中的水流等。人们常常需要知道在既定网络中能通过的最大流量，判断设备的充分利用程度，这就提出了最大流问题。 可行流 可行流满足： 最大流 网络总流量 为最大的可行流 饱和弧 1、正向弧 fij＝cij（流量不能再增加） 2、反向弧 fji＝0 （流量增加导致网络流量减少） 零流弧 使fij＝0的弧称为零流弧 注 令所有弧的流量fij＝0，就得到一个流量等于零 的可行流(零流)。因此，可行流总是存在。 流量可增值Δij 1、正向弧 Δij ＝ cij－fij 2、反向弧 Δij ＝ fji 网络最大流 找到一条从1到7的不饱和链 调整流量，f=1。继续求出网络的不饱和边 求出一条从1到7的不饱和链 调整流量，继续求出网络的不饱和边 求出一条从1到7的不饱和链 调整流量，继续求出网络的不饱和边 求出一条从1到7的不饱和链 调整流量，继续求出网络的不饱和边 求出一条从1到7的不饱和链 调整流量，继续求出网络的不饱和边 已求得最大流 最小割集 所有割集中容量最小的一个割集 最大流最小割定理 任一网络G中，Vs到Vt可通过的最大流 量等于分离Vs 和Vs的最小割容量。 标号组成 标号包括两个部分：（①，②） * * 给一个有向图G＝(V,A)指定两个点，一个点称为发点，记为vs，另一个点称为收点，记为vt，其余点称为中间点。 5.1 基本概念 3 5 1 1 4 2 3 5 2 vs v2 v1 v3 v4 vt 容量 对于G中的每一个弧(vi,vj)，相应地给 一个数cij（cij≥0），称为弧(vi,vj)的 容量（表示这条弧的最大通行能力） 流量 通过弧的某种流的实际流量，简记 为fij 3,1 5,2 1,0 1,0 4,1 2,2 3,1 5,2 2,1 vs v2 v1 v3 v4 vt 流入量=流出量 可行流的流量 3,1 5,2 1,0 1,0 4,1 2,2 3,1 5,2 2,1 vs v2 v1 v3 v4 vt 若μ是连结发点vs和收点vt的一条链，我们规定链的方向是从vs到vt，则链上的弧被分成两类：正向弧、反向弧。 弧的方向与链 的方向相反 弧的方向与链 的方向相同 3,1 5,2 1,0 1,0 4,1 2,2 3,1 5,2 2,1 vs v2 v1 v3 v4 vt 流量可增链 对vs到vt的一条链，若其上所有的弧都是非饱和弧（前向弧都是非饱和弧,后向弧都是都是非零流弧）,这条链的流量就可以增加，并称它为流量可增链 2 1 fij=5 cij=5 2 1 fij=3 cij=5 饱和弧、不饱和弧、流量可增值举例 （1，2）是饱和的 2、如果fijcij，弧从i到j的方向是不饱和的； （1，2）是不饱和的 ?12=c12-f12=5-3=2 1、如果fij=cij，弧从i到j的方向是饱和的； 2 1 fij=0 cij=5 2 1 fij=5 cij=5 3、如果fij=0，弧从j到i的方向是饱和的； （2，1）是饱和的 如果fij0，弧从j到i的方向是不饱和的； （2，1）是不饱和的 间隙为?12=f12=5 算法的原理 首先，依据最大流问题的要求，为网络分配一个可行流。所谓可行流，是指所有弧上流量满足容量限制，所有中间点满足平衡条件的流； 若这一可行流的流量就是最大流量，则问题已经解决； 若不是最大流量，则增加流量获得流量更大的可行流。 5.2 求最大流的标号法 ? 求一个初始可行流 ?  是 判断初始可行流是否最优 结 束 ? 不是 ? 求使目标得到改善的可行流 算法原理图示 初始流 初始流 算法的步骤 ①为网络分配初始流xij，标在图中弧旁的( )内 ②寻求可增链，若不存在，则已最优, 否则 ③在增广链上调整流量，产生新的可行流。 重复②、③两步，直到最优。 2 3 5 4 6 7 1 f f u2