第七章图与网络优化练习题答案

1、第八章 图与网络优化练习题答案一、判断下列说法是否正确1.在任一图G中，当点集V确定后，树图是G中边数最少的连通图。( P )2.若图中某点vi有若干个相邻点，与其距离最远的相邻点为vj，则边vi，vj必不包含在最小支撑树内。( O )3.若图中从v1至各点均有惟一的最短路，则连接v1至其他各点的最短路在去掉重复部分后，恰好构成该图的最小支撑树。( O )4.求网络最大流的问题可归结为求解一个线性规划模型。( P )二、有一项工程，要埋设电缆将中央控制室与15个控制点连通。下图中标出了允许挖电缆沟的地点和距离（单位：hm）。若电缆线100元/m，挖电缆沟（深1m，宽0.6m）土方30元/m3，

2、其它材料和施工费用50元/m，请作出该项工程预算的最少费用。答案：求出其最小支撑树为：埋设电缆的最优方案为总长6200m所以最少工程预算费为6200×(100+0.6×30+50)=1041600元三、用Dijkstra标号法求出下图中v1到各点的最短距离与最短路径。答案：图中的粗线即为v1到各点的最短路径；v1到各点的最短距离为图中带 的数字。四、所给网络中弧旁数字为该弧容量，求网络最大流与最小截集。答案：第一次迭代：vsv1v2v3v4vt(13,7)2663344(7,7)15(0,+)(vs,13)(vs,6)(vs,2)(v1,4)(v1,7)得增广链：(vs,

3、v1, vt)；按=7调整，如上图。第二次迭代：vsv1v2v3v4vt(13,11)266334(4,4)(7,7)(15,4)(0,+)(vs,5)(vs,6)(vs,2)(v1,4)(v4,4)得增广链：(vs, v1, v4, vt)；按=4调整，如上图。第三次迭代：vsv1v2v3v4vt(13,11)(2,2)6(6,2)334(4,4)(7,7)(15,6)(0,+)(vs,2)(vs,6)(vs,2)(v2,2)(v4,2)得增广链：(vs, v2, v4, vt)；按=2调整，如上图。第四次迭代：vsv1v2v3v4vt(13,13)(2,2)6(6,4)(3,2)34(4,

4、4)(7,7)(15,8)(0,+)(vs,2)(vs,6)(v1,2)(v2,2)(v4,2)得增广链：(vs, v1, v2, v4, vt)；按=2调整，如上图。第五次迭代：vsv1v2v3v4vt(13,13)(2,2)(6,4)(6,4)(3,2)3(4,4)(4,4)(7,7)(15,12)(0,+)(vs,6)(-v4,4)(v3,4)(v4,4)得增广链：(vs, v3, v4, vt)；按=4调整，如上图。第六次迭代：vsv1v2v3v4vt(13,13)(2,2)(6,6)(6,6)(3,2)(3,2)(4,4)(4,4)(7,7)(15,14)(0,+)(vs,2)(v3,2)(v2,2)(v4,2)(-v2,2)得增广链：(vs, v3, v2, v4, vt)；按=2调整，如上图。第七次迭代：vsv1v2v3v4vt(13,13)(2,2)(6,6)(6,6)(3,2)(3,2)(4,4)(4,4)(7,7)(15,14)(0,+