第七章圖與網(wǎng)絡(luò)優(yōu)化練習(xí)題答案

1、第八章 圖與網(wǎng)絡(luò)優(yōu)化練習(xí)題答案一、判斷下列說法是否正確1.在任一圖G中，當點集V確定后，樹圖是G中邊數(shù)最少的連通圖。( P )2.若圖中某點vi有若干個相鄰點，與其距離最遠的相鄰點為vj，則邊vi，vj必不包含在最小支撐樹內(nèi)。( O )3.若圖中從v1至各點均有惟一的最短路，則連接v1至其他各點的最短路在去掉重復(fù)部分后，恰好構(gòu)成該圖的最小支撐樹。( O )4.求網(wǎng)絡(luò)最大流的問題可歸結(jié)為求解一個線性規(guī)劃模型。( P )二、有一項工程，要埋設(shè)電纜將中央控制室與15個控制點連通。下圖中標出了允許挖電纜溝的地點和距離（單位：hm）。若電纜線100元/m，挖電纜溝（深1m，寬0.6m）土方30元/m3，

2、其它材料和施工費用50元/m，請作出該項工程預(yù)算的最少費用。答案：求出其最小支撐樹為：埋設(shè)電纜的最優(yōu)方案為總長6200m所以最少工程預(yù)算費為6200×(100+0.6×30+50)=1041600元三、用Dijkstra標號法求出下圖中v1到各點的最短距離與最短路徑。答案：圖中的粗線即為v1到各點的最短路徑；v1到各點的最短距離為圖中帶 的數(shù)字。四、所給網(wǎng)絡(luò)中弧旁數(shù)字為該弧容量，求網(wǎng)絡(luò)最大流與最小截集。答案：第一次迭代：vsv1v2v3v4vt(13,7)2663344(7,7)15(0,+)(vs,13)(vs,6)(vs,2)(v1,4)(v1,7)得增廣鏈：(vs,

3、v1, vt)；按=7調(diào)整，如上圖。第二次迭代：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調(diào)整，如上圖。第三次迭代：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調(diào)整，如上圖。第四次迭代：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調(diào)整，如上圖。第五次迭代：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調(diào)整，如上圖。第六次迭代：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調(diào)整，如上圖。第七次迭代：vsv1v2v3v4vt(13,13)(2,2)(6,6)(6,6)(3,2)(3,2)(4,4)(4,4)(7,7)(15,14)(0,+