网络拓扑结构分析.ppt

* cnl.sie.bupt.cn * 定理5.5 (最大流-最小割定理) 可行流 为最大流当且仅当 中不存在从 到 的可增流路。 证明： 必要性： 设 为最大流,如果 中存 在关于 的从 到 的可增流路 。 ·构造一个新流 如下: · 5.3.2 最大流问题 * cnl.sie.bupt.cn * 不难验证新流 为一个可行流,而且 ,矛盾。 充分性: 设 为可行流, G中不存在关于这个流的可增流路。 5.3.2 最大流问题 * cnl.sie.bupt.cn * 令X* = {v|G中存在从 到 的可增流路},从而 。 对于任意边 ，有 对于任意边 ，有 这样, ,那么流 为最大流， 为最小割。证毕。 性质5.8：如果所有边的容量为整数，则必定存在整数最大流。 5.3.2 最大流问题 * * 从一个可行流出发，搜索每一条从源到宿端的路是否可增流。 每找到一条可增流的路，就进行增流，总流量得以扩大。 直至不存在可增流路，即得到源宿端的最大流量值和相应的流量分配。 最大流问题 M算法 从任一可行流开始，通常以零流开始。 标志过程 从vs开始给邻端加标志,加上标志的端称已标端 选查过程 从vs开始选查已标未查端； 查某端，即标其可能增流的邻端； 所有邻端已标，则该端已查。 标志宿端，则找出一条可增流路到宿端，进入增流过程。 增流过程：在已找到的可增流路上增流。 * * M0：初始令 ； M1：标源端 ： ，作为已标未查端 M2：从 始，查已标未查端 ，即标 的邻端 ，方法如下： 若 ，且 ，标 为: 其中前两个符号表示从 i 到 j 有边。 表示这边上可增流的量 为 已标值。 M算法基本步骤 M算法 若 ，且 ，标 为: 其中 这表示从 j 到 i 有边，是反向的，可以减流 在以上两种情况下，称vj已标未查；不满足这些条件的vj就不标，表示已无可增流路通过vj 。 当vi的所有邻端都查完，并标上值或决定不标，则称vi为已查。 * * M3：若宿端 已标，则沿该可增流路增流。返回M1。 M4:倘若所有端已查且宿端未标，则算法终止。 最大流问题 最大流算法举例-1 初始令fij =0 标源端vs :（+,s,∞） 查该端，即标邻端 v1（+,s,5） v2 （+,s,1） v3（+,s,3） vs已查 选查v2： v3（+,2,1） vt（+,2,1） vs→v2→v t增流1 fs2 =1, f2t =1 最大流算法举例-2 标vs ：（+,s,∞） 查vs ： v1 ：（+,s,5） v3 ：（+,s,3） 选查v3： vt ：（+,3,3） 得vs→v3→vt 增流3：fs3 =3， f3t=3 最大流算法举例-3 标vs ：（+,s,∞） v1 ：（+,s,5） 选查v1： v2 ：（+,1,5） 查v2： vt ：（+,2,2） v3 :（+,2,2） vs→v1 →v2→vt 增流2：fs1=2，f12=2, f2t =3 最大流算法举例-4 标vs ：（+,s,∞） v1 （+,s,3） 查v1： v2 （+,1,3） 查v2： v3（+,2,2） 查v3： vt ：（+,3,2） 得vs→v1→v2→v3→vt 增流2：fs1=4，f12=4, f23 =2，f3t=5， Fmax=8 {δij}={ fs1=4,f32=1,fs3=3,f12=4,f23 =2,f2t=3,f3t=5} M算法 M算法所得结果必为最佳解。但由算法过程可知，选择已标而未查的端的次序是任意的，各种次序可能得不同的可行流，因此结果不是唯一的，最大流量的值则一定是一样的。 M算法是针对有向图且端无限制的情况。若是有无向边，端容量及多源多宿的情况，可以进行一些变换，化为上述标准情形。这个算法的复杂度不是多项式的，但是经过简单改进后算法为多项式复杂度。 无向图情况 一般的无向图是指双工通路，所以边容量实际上是正向容量，也是反向容量。 这时可把一条无向边换成两条边，