最短路最大流练习题.doc

7求图7.58中各图从到各点的最短路742917315682 214611 1923 (a) 448732232564 551532 2642 (b) ，k=5.i=2)，令对已经标号v3，（v3,v7）S,但v7已经标号。对已经标号v11，有（v10,v11）S,则T(v11)修改为P(v10)+w10-11=15+4=19,(v11)=10,所以P(v11)=19, S9= v1,v2,v5,v9,v4,v6,v8,v7,v3,v10,v11 d(v1,v2)=2, 最短路为（v1,v2）; d(v1,v5)=3, 最短路为（v1,v2,v5）; d(v1,v9)=4, 最短路为（v1,v2,v5,v9）; d(v1,v7)=14 ,最短路为（v1,v2,v5,v9,v6,v7）; d(v1,v8)=11, 最短路为（v1,v2,v5,v9,v8）; d(v1,v4)=8, 最短路为（v1,v2,v4）或（v1,v4）; d(v1,v6)=10, 最短路为（v1,v2,v5,v9,v6）; d(v1,v3)=15, 最短路为（v1,v2,v4,v3）或（v1,v4,v3）; d(v1,v10)=15, 最短路为（v1,v2,v5,v9,v6,v7,v10）; d(v1,v11)=19, 最短路为（v1,v2,v5,v9,v6,v7,v10,v11）;结果标在图7.58(a)上。P(19,10) P(14,6) P(10,9) P(4,5) P(3,2) P(8,1) P(0,0) 42917315682 214611 17923 P(2,1) P(11,9) P(15,4) P(15,7) 图7.58(a) 解 结果见图7.58(b).P(17,8) P(11,7) P(9,3) P(8,4) P(7,2) P(6,1) P(0,0) 448732232564 551532 2642 图7.58(b)P(4,1) P(3,1) P(10,6) P(14,7) 12 求图7.62中各图从到的最大流34148235679 45532 157 (a) (3,2)(3,2)(10,4)(2,2)(1,1)(4,3)(3,2)(4,3) (4,2)(5,3)(8,3)(7,6)(b) 图7.62(s,7)(1,3)(3,0)(5,3)(4,4)(1,0)(7,1)(2,3)(1,4)(4,4)(8,2)(2,2)(3,0)(6,2)(7,2)(0,+)(9,2) (4,0)(5,4)(5,4)(3,0)(2,2) (1,0)(5,0)(7,4) (5,1)(a) (3,3)(3,3)(10,7)(s,3)(2,2)(1,1)(4,4)(3,3)(0,+)(4,4) (4,4)(5,5)(8,7)(7,7)(b) 图7.6213 两家工厂和生产同一种商品，商品通过图7.63表示的网络送到市场求从工厂到市场所能运送的最大总量1876281319324242471271574522图7.63解 加上点，点同时给中间点加上名称，令所有弧的可行流都为0，如图7.63(1)所示，(19,0)(19,0)(6,0)(7,0)(16,0)(30,0)(18,0)(7,0)(6,0)(2,0)(8,0)(13,0)(19,0)(3,0)(24,0)(24,0)(2,0)(4,0)(7,0)(12,0)(15,0)(7,0)(4,0)(5,0)(22,0)图7.63(1)（1）标号过程用标号法找出增广链.(0,+),(,30),(,18),(,7),(,7),因已标号,故转入调整过程.(19,0)(19,0)(6,0)(7,0)(16,0)(30,0)(18,0)(7,0)(6,0)(2,0)(8,0)(13,0)(19,0)(3,0)(24,0)(24,0)(2,0)(4,0)(7,0)(12,0)(15,0)(7,0)(4,0)(5,0)(22,0)图7.63(2)(2)调整过程按点的第一标号找到一条增广链,如图7.63(2)中粗箭头表示.按照=7,在上调整由于本题图形复杂,调整过程次数过多,这里不再一步步进行计算,把进行几步计算后的结果直接写在图7.63(3)上.(19,4)(19,13)(6,6)(7,0)(16,10)(30,13)(18,9)(7,4)(6,6)