最短路最大流练习题.docx
最短路最大流练习题7 求图7.58中各图从v1到各点的最短路 v22 8 1 v5 12 v8 7 9 6 5 3 v4 1 v6 4 6 v9 2 v11 v1 1 2 31 7 4 v3 9 v7 (a) 1 v10 v243 v5 4 v8 2 7 5 2 2 26 v4 2 v6 1 5 v98 v1 23 4 3 5 v11 4 v3 6 v7 (b) 5 v10 解：(a)i=0:S0=v1,P(v1)=0,l(v1)=0,T(vi)=+¥,l(vi)=M(i=2,3¼¼11)k=1(v1,v2)ÎA,v2ÏS0,p(v1)+w12<T(v2),故T(v2)修改为P+w12=2l修改为1ÎA，v4ÏS0，P(v1)+w14<T(v14),故T修改为P(v1)+w14=8l(v4)修改为1minT(v2),T(v4)=T(v2)=2,令P(v2)=T(v2)=2,S1=S0Uv2=v1,v4,v2k=2i=1(v2,v5)ÎA,v5ÏS1,P(v2)+w25<T(v5),故T修改为P+w25=3l修改为2，(v2,v4)ÎA,v4ÏS1,P(v2)+w24=T(v4)=8minT(v4),T(v5)=T(v5)=3,令P(v5)=3,S2=v1.v2,v5,k=5i=2:(v5,v4)ÎA,v4ÏS2,P(v5)+w54=T(v4)=8,(v5,v9)Î，k=5. i=2 (v5,v4)ÎA,v4ÏS2,P(v5)+w54=T(v4)=8,(v5,v9)ÎA,v9ÏS2)， P(v5)+w59<T(v9),故T修改为4，l修改为5。0minT(v4),T(v9)=T(v9)=4,令P(v9)=4,S3=v1,v2,v5,v9,k=9,i=3:修改T(v8)为P+w98=11，修改l=9，修改T=P+w96=10，修改l=9minT(v4),T(v8),T(v6)=T(v4)=8,令P(v6)=10,S4=v1,v2,v5,v9,v4,k=4i=4T(v3)修改为P(v4)+w43=15,l(v3)修改为4minT(v=),T(v6),T(v3)=T(v6)=10,令P=10，l=9；S5=v1，v2，v5，v9，v4，v6，k=6i=5T修改为P+w67=14，l修改为6minT(v8),T(v3),T(v7)=T(v8)=11令P(v8)=11,S6=v1,v2,v5,v9,v4,v6,v8,k=8i=6T(v11)修改为P(v8)+w8,11=20,l(v11)修改为8minT(v3),T(v7),T(v11)=T(v7)=14P(v7)=14,l(v7)=6,S7=v1,v2,v3,v9,v4,v6,v8,v7,k=7i=7令T(v10)修改为15，l修改为7，minT(v3),T(v11),T(v10)=T(v3)=T(v10)=15令P(v3)=15,P(v10)=15,l(v10)=7,S8=v1,v2,v5,v9,v4,v6,v8,v7,v3,v10,k=10i=8对已经标号v3，S,但v7已经标号。对已经标号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, 最短路为; d(v1,v5)=3, 最短路为; d(v1,v9)=4, 最短路为; d(v1,v7)=14 ,最短路为; d(v1,v8)=11, 最短路为; d(v1,v4)=8, 最短路为或; d(v1,v6)=10, 最短路为; d(v1,v3)=15, 最短路为或; d(v1,v10)=15, 最短路为; d(v1,v11)=19, 最短路为; 结果标在图7.58(a)上。 P(2,1) v22 8 1 v5 P(3,2) 2 1v8 P(11,9) 7 9 6 5 3 v4 P(8,1) 7 1 v6 4 6 P(10,9) v9 2 P(4,5) 1 v1 P(0,0) 1 2 v11 P(19,10) 34 9 P(15,4) v3 v7 P(14,6) 1 图7.58(a)v10 P(15,7) 解 结果见图7.58(b). P(4,1) v 2 43 v5 4 P(7,2) 2v8 2 P(10,6) 7 5 2 2 6 v4 P(6,1) 4 2 v6 5 v98 v1 P(0,0) 3 5 P(8,4) 1 23 v11 P(11,7) P(17,8) 4 P(3,1) v 3 6 v7 P(9,3) 5 图7.58(b) v10 P(14,7) 12 求图7.62中各图从vS到vt的最大流 v1 3 96 v4 5 5 7 2 4 1 3 5 72v6 8 vs1 4 v2v7vt 4 v3 5 v5 (a) 3 v8 v1 (4,3) (1,1) v2(7,6) (4,3) (3,2) vs(3,2) v3 (5,3) (2,2) vt(8,3) (10,4) (3,2) v4 (4,2) (b) 图7.62 v5 v1(s,7) (3,0) (9,2) (6,2) (7,2) v4(1,3) (5,0) (2,2) (4,0) (1,0) (2,2) v6(8,2) vs (0,+) (4,4) v2(1,4) (1,0) (3,0) v7(5,1) vt(7,4) (4,4) (5,4) v3(5,3) (5,4) v5(2,3) (a) (3,0) v8(7,1) v1 (4,4) (1,1) v2(7,7) (4,4) (3,3) vs (0,+) (3,3) v3 (5,5) (2,2) vt(8,7) (10,7) (3,3) v4(s,3) (4,4) (b) 图7.62 v5 13 两家工厂x1和x2生产同一种商品，商品通过图7.63表示的网络送到市场y1,y2,y3求从工厂到市场所能运送的最大总量 x1 18 7 5 3 22 8 2 6 4 图7.63 24 19 7 4 2 7 13 7 24 12 15 y1 y2 x2 y3 解 加上vs,vt点，点同时给中间点加上名称，令所有弧的可行流都为0，如图7.63(1)所示， x1 (30,0) (5,0) (18,0) (7,0) (4,0) y1 (2,0) (7,0) (6,0) v1 (19,0) (3,0) (22,0) v3 (7,0) (24,0) (7,0) v4 vs (8,0) (16,0) (2,0) (13,0) (12,0) (19,0) y2 vt v2 (24,0) v5 (4,0) (15,0) (19,0) (6,0) x2 标号过程 图7.63(1) y3 用标号法找出增广链.vs(0,+¥),x1(vs,30),v4(x1,18),y2(v4,7),vt(y2,7),因vt已标号,故转入调整过程. x1(vs,30) (18,0) (30,0) (5,0) (7,0) (4,0) y1 (6,0) v4(x1,18) (2,0) (7,0) (13,0) (12,0) v1 (19,0) (3,0) (22,0) v3 (7,0) (24,0) (7,0) (19,0) vs (8,0) (16,0) (2,0) y2(v4,7) vt(y2,7) (15,0) v2 (24,0) v5 (4,0) (19,0) (6,0) x2 图7.63(2) y3 (2)调整过程 按点的第一标号找到一条增广链,如图7.63(2)中粗箭头表示. 按照q=7,在m上调整 fsx1+7=0+7=7,fx1v4+7=0+7=7,fv4y2+7=0+7=7,fv4vt+7=0+7=7. 由于本题图形复杂,调整过程次数过多,这里不再一步步进行计算,把进行几步计算后的结果直接写在图7.63(3)上. x1 (30,13) (5,0) (18,9) (7,4) (4,4) y1 (2,2) (7,7) (6,6) v1 (19,0) (3,0) (22,4) v3 (7,0) (24,0) (7,0) v4 vs (8,4) (2,0) (16,10) (13,0) (19,13) y2(12,6) (15,0) vt v2 (24,0) v5 (4,4) (19,4) x2 (6,6) 图7.63(3) y3
