运筹学第五章-图与网络分析.ppt

解：（1）给出一个可行流f=0， 找到一条从v1到v7的可增广链 （2）调整流量f=1,继续求出网络的一条可增广链。 (7)已求得最大流 f=11 例10：求结点v1至结点v7的最大流，同时写出其最小截集及截量。 v2 v3 v5 v4 v6 v7 v1 f=0 f=0 6 2 4 7 4 3 7 9 3 1 8 8 可增广链为：v7-v6-v3-v1；可调整流量为：? =1 调整链的流量：xij’=xij+ ?；f’=f+1=1 v2 v3 v5 v4 v6 v7 v1 f=0 f=0 (6,0) (2,0) (4,0) (7,0) (4,0) (3,0) (7,0) (9,0) (3,0) (1,0) (8,0) (8,0) [∞，v1] [8,v1] [3,v2] [1,v3] [1,v6] 方法：(1) 给起点vs标号[0，vs]。 （2）把顶点集v分为互补的两部分A和ā 其中：A：已标号点集 ā：未标号点集 （3）考虑所有这样的边[vi, vj], 其中vi ∈A,vj ∈ ā 挑选其中与vs距离最短的点vj标号 [min{αi+cij},vi] (4) 重复（3），直至终点vt标上号[αt,vk]，则α t即为vs至vt的最短距。 反向追踪可求得最短路。 例５：求v1至v8的最短路。 v2 v3 v7 v1 v8 v4 v5 v6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 v2 v3 v7 v1 v8 v4 v5 v6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 (1) v1:[0,v1] 计算min {0+2, 0+1, 0+3} = min {2,1,3}=1 v4:[1.v1] [1,v1] [0,v1] (2)A={v1} 检查边（v1,v2),(v1,v4),(v1,v3) v2 v3 v7 v1 v8 v4 v5 v6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 (3)A={v1,v4} 计算 min{0+2, 0+3, 1+10, 1+2}=min {2,3,11,3} =2 v2:[2,v1] [0,v1] [1,v1] [2,v1] 考虑边（v1,v2),(v1,v6),(v4,v2),(v4,v7) v2 v3 v7 v1 v8 v4 v5 v6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 （4）A={v1,v2,v4} 计算min { 0+3, 2+6, 2+5, 1+2} v6:[3,v1] =min {3,8,7,3}=3 [2,v1] [1,v1] [0,v1] [3,v1] 考虑边（v1,v6),(v2,v3),(v2,v5),(v4,v7) v2 v3 v7 v1 v8 v4 v5 v6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 (5)A={V1,V2,V4,V6} 计算 min { 2+6, 2+5, 1+2, 3+4}=min {8,7,3,7}=3 v7:[3,v4] [2，V1] [1，V1] [0，V1] [3，V1] [3,v4] 考虑边(v2,v3),(v2,v5),(v4,v7),(v6,v7) V2 V3 V7 V1 V8 V4 V5 V6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 (6)A={V1,V2,，V4,V6,V7} 计算min {2+6, 2+5, 3+3, 3+8}=min {8,7,6,11}=6 v5:[6,v7] [2,v1] [1,v1] [0,v1] [3,v1] [3,v4] [6,v7] 考虑边(v2,v3),(v2,v5),(v7,v5),(v7,v8) v2 v3 v7 v1 v8 v4 v5 v6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 (7)A={V1,V2,V4,V6,V7} 计算min { 2+6, 6+9, 6+4, 3+8}=m