第十章 (圖與網(wǎng)絡(luò)分析)

1、第十章 圖與網(wǎng)絡(luò)分析精典習(xí)題10.1 證明如下序列不可能是某個(gè)簡(jiǎn)單圖的次的序列：（1）7,6,5,4,3,2（2）6,6,5,4,3,2,1（3）6,5,5,4,3,2,110.2 已知9個(gè)人中，和兩個(gè)人握過(guò)手， 各和四個(gè)人握過(guò)手，各和五個(gè)人握過(guò)手，各和六個(gè)人握過(guò)手，證明這九個(gè)人中一定可以找出三個(gè)人互相握過(guò)手。10.3 有八種化學(xué)藥品A、B、C、D、P、R、S、T要放進(jìn)儲(chǔ)藏室保管。出于安全原因，下列各組藥品不能儲(chǔ)存在同一室內(nèi)：A-R、A-C、A-T、R-P、P-S、S-T、T-B、T-D、B-D、D-C、R-S、R-B、P-D、S-C、S-D問(wèn)儲(chǔ)存這八種藥品至少需要多少間儲(chǔ)藏室。圖10-110

2、.4 已知有十六個(gè)城市及他們之間的道路聯(lián)系（見(jiàn)圖10-1）。某旅行者從城市A出發(fā)，沿途依次經(jīng)過(guò)J、N、H、K、G、B、M、I、E、P、F、C、L、D、O、C、G、N、H、K、O、D、L、P、E、I、F、B、J、A，最后到達(dá)城市M。由于疏忽，該旅行者忘了在圖上標(biāo)明各城市的位置，請(qǐng)應(yīng)用圖的基本概念及理論，在圖101中標(biāo)明各城市AP的位置。10.5 十名研究生參加六門(mén)課程的考試。由于選修的課程不同，考試門(mén)數(shù)也不一樣。表101給出了每個(gè)研究生應(yīng)參加考試的課程（打號(hào)的）。規(guī)定考試應(yīng)在三天內(nèi)結(jié)束，每天上下午各安排一門(mén)。研究生們提出希望每人每天最多考一門(mén)，又課程A必須安排在每一天上午考，課程F安排在最后一門(mén)

3、，課程B只能安排在中午考，試列出一張滿(mǎn)足各方面要求的考試日程表。表10-1考試課程研究生ABCDEF1234567891010.6 用破圈法和避圈法找出圖10-2的一個(gè)支撐樹(shù)。 e1v1v2v3v4v5v6v7v8v9v10e2e3e7e4e5e6e8e9e10e11e12e13e14e15圖10-210.7 用破圈法和避圈法求圖103中各圖的最小樹(shù)。(a)728232443613654174312223425(b)223221533522422536474536321(c)(d)圖10-310.8 已知世界6大城市：（Pe）、（N）、（Pa）、（L）、（T）、（M）。試在由表101所示交通網(wǎng)

4、絡(luò)的數(shù)據(jù)中確定最小樹(shù)。表10-2城市PeTPaMNLPe×1351776850T13×60706759Pa5160×57362M777057×2055N68673620×34L505925534×10.9 有九個(gè)城市,其公路網(wǎng)如圖104所示?；∨詳?shù)字是該段公路的長(zhǎng)度，有一批貨物從運(yùn)到，問(wèn)走那條路最短？343323122.5542V1V2V3V4V5V6V7V8V93圖10-410.10 用標(biāo)號(hào)法求圖105中V1到各點(diǎn)的最短路。2261304202047105101515751030420V1(a)(b)圖10-5V1985218374

5、310710.11 用Dijksrea方法求圖106中V1到各點(diǎn)的最短距離。V12847615129143216317924V2V3V4V5V6V7V8V9V10V11圖10-610.12 求圖10-7中從V1到各點(diǎn)的最短路。12445331222V1V2V4V323V5V6圖10-710.13 在圖108中(1) 用Dijkstra 方法求從V1到各點(diǎn)的最短路；(2) 指出對(duì)V1來(lái)說(shuō)那些頂點(diǎn)是不可到達(dá)的。V4413341624367V1V2V7V5V6V8V3圖10-810.14 已知八口海上油井，相互間距離如表10-2所示。已知1號(hào)井離海岸最近，位5浬。問(wèn)從海岸經(jīng)1號(hào)井鋪設(shè)油管將各油井連接

6、起來(lái)，應(yīng)如何鋪設(shè)使輸油管線(xiàn)長(zhǎng)度為最短（為便于計(jì)算和檢修，油管只準(zhǔn)在各井位處分叉）。表10-2 各油井間距離 單位：km從 到234567811.32.10.90.71.82.01.520.91.81.22.62.91.132.61.72.51.91.040.71.61.50.950.91.10.860.61.070.510.15 設(shè)某公司在六個(gè)城市c1, , c6 有分公司，從ci 到cj 的直達(dá)航線(xiàn)票價(jià)記在下面矩陣的（i，j）位置上（表明無(wú)直達(dá)航線(xiàn)，需經(jīng)其他城市中轉(zhuǎn)）。請(qǐng)幫助該公司設(shè)計(jì)一張任意兩城市的票價(jià)最便宜的路線(xiàn)表。10.16 在如圖10-9 所示的網(wǎng)格中，每弧旁的數(shù)字是（cij，fij

7、）。(1) 確定所有的數(shù)集；(2) 求最小截集的容量；(3) 證明指出的流是最大流。(2,2)(4,3)(3,3)(1,0)(2,2)(5,2)(3,1)圖 10-910.17求如圖10-10 所示的網(wǎng)絡(luò)的最大流（每弧旁的數(shù)字是（cij，fij）。VsVt（1,1）（4,3）（7,6）（4,3）（3,2）（3,2）（3,2）（4,3）（4,2）（5,3）（8,3）（2,2）圖10-1010.18用Ford-Fulkerson的標(biāo)號(hào)算法求圖10-11中所示各容量網(wǎng)絡(luò)中從Vs到Vt的最大流，并標(biāo)出個(gè)網(wǎng)絡(luò)的最小割集。圖中各弧旁數(shù)字為容量cij，括弧中為流量fij。5(5)4(3)3(2)2(2)1(

8、1)5(4)5(5)5(2)1(1)2(2)3(3)4(4)5(3)1(1)2(1)2(2)1(2)2(1)2(1)2(2)2(0)1(0)2(2)2(0)1(1)(a)(b)3(2)5(5)3(3)3(3)2(0)6(4)4(4)2(2)5(4)2(0)8(6)6(6)(c)12(10)6(5)3(3)5(4)4(3)3(3)5(4)4(4)2(2)5(4)2(2)9(9)9(6)(d)圖10-1110.19 某單位招收懂俄、英、日、德、法文的翻譯各一人。有5人應(yīng)聘。已知乙懂俄文，甲、乙、丙、丁懂英文，甲、丙、丁懂日文，乙、戊懂德文，戊懂法文。問(wèn)最多有幾人能得到招聘，有分別被聘任從事那一文種

9、的翻譯。10.20求圖10-12中從st的最小費(fèi)用最大流，各弧旁數(shù)字為（cij，bij）。（4,1）（7,6）（5,2）（2,3）（3,2）（8,4）（6,1）st（a）（b）（7,7）（5,3）（5,1）（7,2）（10,9）（5,3）（8,4）（10,10）（7,2）st圖10-1210.21 圖10-13中，A、B為出發(fā)點(diǎn)，分別有50 和40 單位物資往外發(fā)運(yùn)，D、E為收點(diǎn)，分別需要物資30 和60 單位，C為中轉(zhuǎn)點(diǎn)，各弧旁數(shù)字為（cij，bij）。求滿(mǎn)足上述收發(fā)量要求最小費(fèi)用流。ABCDE(20,90)(80,10)(10,30)(30,20)(40,30)(50,40)(10,20)

10、圖10-1310.22 設(shè)G=（V,E）是一個(gè)簡(jiǎn)單圖，令（G）=vVmind(v)(稱(chēng)（G）為G的最小次)。證明：（1）若（G） 2，則G必有圖；（2）若（G） 2，則G必有包含至少（G）+1條邊的圖。10.23 設(shè)G是一個(gè)連通圖，不含奇點(diǎn)。證明：G中不含割邊。10.24 給一個(gè)聯(lián)通賦權(quán)圖G，類(lèi)似于求G的最小支撐樹(shù)的Kruskal方法，給出一個(gè)求G的最大支撐樹(shù)的方法。10.25 下述論斷正確與否：可行流f的流量為零，即v(f)= 0，當(dāng)且僅當(dāng)f是零流。55習(xí)題答案及詳解10.1 證明（1）由圖的性質(zhì)定理知，任一個(gè)圖中，奇點(diǎn)的個(gè)數(shù)為偶數(shù)。7，6，5，4，3，2中存在3個(gè)奇數(shù)，所以不可能是某個(gè)圖的

11、次的序列，更不是某個(gè)簡(jiǎn)單圖的次的序列?！净蛘摺考僭O(shè)7，6，5，4，3，2為某個(gè)簡(jiǎn)單圖的次的序列，則圖中有6個(gè)點(diǎn)，作為簡(jiǎn)單圖點(diǎn)的最大次數(shù)為n-1，即最大次數(shù)為5，顯然與存在點(diǎn)的次數(shù)為7矛盾。所以，7，6，5，4，3，2又是簡(jiǎn)單圖的次的序列。（2）由定理知，任一個(gè)圖G=(V，E)中，所有點(diǎn)的次數(shù)之和是邊數(shù)的兩倍，即圖中點(diǎn)次的和為偶數(shù)。序列6，6，5，4，3，2，1的和為27，所以它不可能是一個(gè)圖的次的序列，更不可能是某個(gè)簡(jiǎn)單圖的次的序列?！净蛘摺考僭O(shè)6，6，5，4，3，2，1為某個(gè)簡(jiǎn)單圖的次的序列，則圖中存在7個(gè)點(diǎn)，不妨設(shè)為，其中 ，次為6，表明，與除自身外的剩余6個(gè)點(diǎn)均相連。即，的次不少于2，與

12、的次為1矛盾。所以，6，6，5，4，3，2，1不是某個(gè)簡(jiǎn)單圖的次的序列。（3）假設(shè)6，5，4，3，2，1為某個(gè)簡(jiǎn)單圖的次的序列，則圖中存在7個(gè)點(diǎn)，不妨設(shè)為，因?yàn)?6, =1,所以與其他6個(gè)點(diǎn)相連，而僅與相連，又因?yàn)?，則，與除和自身之外的所有點(diǎn)相連，則必須與，相連，所以與，相連，與矛盾，所以6，6，5，4，3，2，1不是某個(gè)簡(jiǎn)單圖的次的序列。10.2 解：設(shè)9個(gè)人，為9個(gè)點(diǎn)，兩人握手設(shè)為兩點(diǎn)之間存在相連邊，握手問(wèn)題轉(zhuǎn)化為一個(gè)簡(jiǎn)單圖，其中，次的序列為2，4，4，5，5，5，5，6，6。這9個(gè)人中一定可以找到3個(gè)互相握過(guò)手，轉(zhuǎn)化為在圖中一定存在3個(gè)點(diǎn)彼此相連。因?yàn)?，之間一定存在兩點(diǎn)相連。假如，互相均

13、不相連，因?yàn)榇尉鶠?，所以，均與剩余的4個(gè)點(diǎn)，相連，這與 =2矛盾。不妨設(shè)，中存在，之間相連。必可以找到第三點(diǎn)均與，相連。假設(shè)不存在第3點(diǎn)均與，相連，分別與定義不同的4個(gè)點(diǎn)相連，即存在8個(gè)不同的點(diǎn)分別與或相連，加上，共計(jì)10個(gè)點(diǎn)，這與圖中9個(gè)點(diǎn)矛盾。所以在圖中，必存在3個(gè)點(diǎn)彼此相連。（a）BATCRPSD10.3 解：將8種化學(xué)藥品A，B，C，D，P，R，S，T設(shè)定為8個(gè)點(diǎn)，兩種藥品不能貯存同一室內(nèi)狀態(tài)，設(shè)定為兩點(diǎn)之間存在一邊相連，畫(huà)出藥品關(guān)系圖如下：（圖10-3（a）（B）BATCRPSD圖10-3 在圖（a）中，兩點(diǎn)之間相連的藥品均不能存貯在一起。對(duì)于由點(diǎn)A，B，C，D，P，R，S，T的完

14、全圖，求圖（a）的補(bǔ)圖，得圖（b）,在（b）圖中，彼此相連的藥品均可以為存貯莊點(diǎn)，因?yàn)?，從S，D開(kāi)始搜索，（S，A，B）彼此相連，（D，R）相連，（T，C，P）彼此相連。所以至少需要3間貯存室，存效組合為（S，A，B），（T，C，P），（D，R）。10.4 解：依據(jù)旅行者的路線(xiàn)統(tǒng)計(jì)城市間的相互關(guān)系。點(diǎn)（城市）相鄰城市（相鄰點(diǎn)）次點(diǎn)相鄰點(diǎn)次AJ，M2IM，E，F(xiàn)3BG，M，F(xiàn)，J4JA，N，B3CF，I，O，G4KH，G，O3DL，O2LC，D，P3EL，P2MB，I，A3FP，C，I，B4NJ，H，G3GK，M，C，N4OD，C，K3HM，K2PE，F(xiàn)，L3A M I E J B F PN G

15、 C LC K O D圖10-4由點(diǎn)的次可知，A，D，E，H為2，則為4個(gè)頂點(diǎn)；B，C，F(xiàn)，G的次為4，則為4個(gè)頂點(diǎn)；某系為邊點(diǎn)，城市布局圖為圖10-4。 DAEBF圖10-5 （b）10.5 解：將課程A，B，C，D，E，F(xiàn)設(shè)定為6個(gè)點(diǎn)，同時(shí)學(xué)生選某課程認(rèn)為存在相鄰邊。依據(jù)學(xué)生1-10的選課劃分課程關(guān)系圖10-5（a），要求學(xué)生一天最多考1門(mén)，即圖（a）中相連的課程不能排在同一天。對(duì)于點(diǎn)ABCDEF的關(guān)系圖，求圖（a）的補(bǔ)圖（b）。CABDEF圖10-5 （a） 那么，圖（b）中相鄰的課程可以安排在同一天，可保證學(xué)生一天最多考一門(mén)，所以（A，E），（F，D），（C，B）分別各為一天，安排如下

16、：天上午下午123ACDEBF10.6 解：（破圈法）尋找圖中的圈，去掉圈中的一邊。（1）圈（）去掉；圈（）去掉；圈（）去掉。（2）圈（）去掉；圈（）去掉，得到支撐樹(shù)(c)。e1v1v2v3v4v5v6v7v8v9v10e2e3e7e4e5e6e8e9e10e11e12e13e14e15(a) v1v2v3v4v5v6v7v8v9v10e2e3e7e5e6e8e9e10e11e12e14e15(b) v1v2v3v4v5v6v7v8v9v10e2e3e7e8e10e11e12e14e15(b) (避圈法)(1) 從點(diǎn)出發(fā)，邊相鄰邊增加邊和點(diǎn)，保證不構(gòu)成回路。出發(fā)，增加。(2) 相鄰邊，增加，相

17、鄰邊，增加點(diǎn) ，。(3) 相鄰邊，增加，相鄰邊，增加點(diǎn)，。將點(diǎn)均包含在圖中，且不存在回路，構(gòu)成一個(gè)支撐樹(shù)（f）。(e)e1v1v2v3v4v5v10e12e2e7e6v6v8e1v1v2v3v5e2e7(d)v1v2v3v4v5v6v7v8v9v10e2e3e7e8e10e11e12e14e15(f)10.7 解：a）（破圈法）在圖中尋找圈，去除圈中權(quán)值最大的邊（V1 ，V2 ，V3）去除（V1 ,V3 ）邊；（V1 ，V4 ，V7）去除（V4 ,V7 ）邊；（V2 ，V5 ，V8）去除（V2 ,V8 ）邊；（V6 ，V8 ，V9）去除（V7 ,V8 ）邊，得到圖（a2）（V2 ，V5 ，V3

18、）去除（V2 ,V5 ）邊；（V3 ，V6 ，V4）去除（V3 ,V6）邊；（V5 ，V6 ，V8）去除（V5 ,V6 ）邊，得到圖（a3）（V1 ，V2，V3 ,V4）去除（V1 ,V2）邊，( V3 ，V4，V6 ,V8，V5) 去除（V4 ，V6）邊, 得到圖（a4）。( V1 ，V4，V3 ,V5，V8，V7)去掉（V3 ,V4）邊，得到圖（a5）,圖中不再有回路，則為最小樹(shù)，其權(quán)值和為(a2)v1v2v5v4v7v8v3v6722124431357(a1)v1v2v5v4v7v8v3v672823244361365417 (a3)v1v2v5v4v7v8v3v6721244313(a

19、4)v8v1v2v5v4v7v3v62124313(a5)v1v8v2v5v4v7v3v62124313圖10-7 （1） (避圈法)從V1 出發(fā)，即V =V1其余點(diǎn)為，與間有邊（V1 ，V2），（V1 ，V3），（V1 ，V7），（V1 ，V4），權(quán)值分別為7，8，3，2，權(quán)值最短邊為（V1 ，V4）。則加粗邊（V1 ，V4），令。與間最短邊為（V1 ，V7），加粗邊（V1 ，V7），令。依次按照上述規(guī)則操作，直到。則得到最小樹(shù)為圖（a3）, 其權(quán)值和為16。 (a1)v1v2v5v4v7v8v3v672823244361365417(a2)v1v2v5v4v7v8v3v6728232443

20、61365417 (a5)v1v8v2v5v4v7v3v62124313圖10-7 （2）（b）依圖（a）中的步驟，得到圖b）的最小樹(shù)圖為10-4 （b），其權(quán)值和為222132222圖10-7 （c）122232圖10-7 （b） 3421334圖10-7 （d）（c）依圖（a）中的步驟，得到圖c）的最小樹(shù)圖為10-7 （c），其權(quán)值和為 （d）依圖（a）中的步驟，得到圖d）的最小樹(shù)圖為10-7 （d），其權(quán)值和為 10.8解：6城市（Pe），（N），（Pa），（L），（T），（M）對(duì)應(yīng)6個(gè)點(diǎn)，依表中數(shù)據(jù)得到交通網(wǎng)絡(luò)圖為：TLPaNMPe135177685060705967345736552

21、02按照避圈法，V=Pe，=T，L，Pa，M，N，與的最短邊為（Pe，T），加粗（Pe，T）邊，即V=Pe，T，=L，Pa，M，N，依次推導(dǎo)。逐次加入邊（Pe，L），（L，Pa），（L，N），（N，M），得到最小樹(shù)圖：PeTLPaN9解：利用雙標(biāo)號(hào)法，求的最短路線(xiàn)。（1）從出發(fā)，標(biāo)號(hào)為（，0），=，其余點(diǎn)為。（2）中點(diǎn)相鄰的未標(biāo)號(hào)的點(diǎn)有，則對(duì)進(jìn)行標(biāo)號(hào)（，3），令，。（3）中點(diǎn)，與未標(biāo)號(hào)的，=，給標(biāo)號(hào)（，），令343323122.5542V1(V1,0)(V1,3)V2(V2,6)V3V4(V1,4)V5(V2,5)(V2,6)V6V7(V4,7)V8(V6,8.5)V

22、93(4) 依（3）中的原理，與相鄰邊累計(jì)最小為（，），（5）按照上述原則，依次標(biāo)號(hào)順序?yàn)椋航o標(biāo)號(hào)（，6），=；給標(biāo)號(hào)（，6），=，；給標(biāo)號(hào)（，7），=，；給標(biāo)號(hào)（，8.5），=，；已標(biāo)號(hào)，因此，的最短路線(xiàn)為，最短路長(zhǎng)為8.5。10.10解：（a） 2261304202047105101515751030420V1(V1,0)V2(V1,30)V3(V2,31)(V5,29)V4V5(V6,27)V6(V1,20)V7(V6,24)V8(V7,28)(V8,33)V9(V9,34)V10V11(V8,34)V12(V11,44) （1）從出發(fā)，令=，其余點(diǎn)為，給標(biāo)號(hào)為（，0）。（2）與相鄰邊有

23、（）,()，給標(biāo)號(hào)（，20），令（3）與相鄰邊有（）,( )，（），（）=，給標(biāo)號(hào)（），令。（4）依次標(biāo)號(hào)：（，27），（，28），；（，29），（，30），；（，31），（，33），； (，34)，（，34），（，44），至此，全部點(diǎn)都已標(biāo)注。V11V12261304202047105101515751030420V2V3V4V5V6V7V8V9V10V126到各點(diǎn)的最短路只需從該點(diǎn)出發(fā)，逆向搜索標(biāo)號(hào)就可得到，且該標(biāo)號(hào)中第2組數(shù)字就是到該點(diǎn)的最短距離。 V2 : V2 ， V3 : ， V4: ， V5: ， V6: ， V7: ， V8: ， V9: ， V10: ， V11: ， V12

24、: ， V1(V1,0)V2(V1,9)V3(V1,8)V4(V2,10)V5(V2,1)V6V7(V4,13)9852183743107(b) (1) 從出發(fā)，令=，其余點(diǎn)為，給標(biāo)號(hào)為（，0）（2）與相鄰邊有（）,( )，累計(jì)距離，給標(biāo)號(hào)（，8），令（3）按照以上規(guī)則，依次標(biāo)號(hào)，直至所有的點(diǎn)均標(biāo)號(hào)為止， 到某點(diǎn)的最短距離為沿該點(diǎn)標(biāo)號(hào)逆向追溯。標(biāo)號(hào)順序?yàn)椋篤3 (V1，8)，V2 (V1，9)，V4 (V2，10)，V1 (V4，13)，V5 (V2，11)，V6 (V5，14)。到各點(diǎn)的最短路見(jiàn)圖中粗線(xiàn)。 10.11 解：2847615129143216317924V1(V1,0)V2(V1

25、,2)V3(V4,15)V4(V1,8)V5(V2,3)V6(V9,10)V7(V6,14)V8(V9,11)V9(V5,4)V10(V7,15)V11(V10,19) (1) 從出發(fā)，令=，其余各點(diǎn)集合為。給標(biāo)號(hào)為（，0）,的所有邊為（），（），累計(jì)距離最小為，給標(biāo)號(hào)為（，2），令 （2）的所有邊為（），（），（），累計(jì)距離最小為，令，（3）按照標(biāo)號(hào)規(guī)則，依次給未標(biāo)號(hào)點(diǎn)標(biāo)號(hào)，直到所有點(diǎn)均已標(biāo)號(hào)，或者不存在有向邊為止。標(biāo)號(hào)順序?yàn)椋篤5 (V2，8)，V9 (V5，9)，V4 (V1，8)，V4 (V1，8)，V6 (V9，10)，V8 (V9，11)，V7 (V6，14)，V3 (V4，15)

26、，V10 (V1，15)，V11 (V10，19)。則到各點(diǎn)的最短路線(xiàn)按照標(biāo)號(hào)進(jìn)行逆向追索（結(jié)果見(jiàn)圖中粗線(xiàn)）。例如，最短路為，權(quán)值和為19。10.12解：求解到各點(diǎn)的最短路。（1）從出發(fā)，標(biāo)號(hào)為（，0），令=，其余各點(diǎn)集合為。（2）的有向弧有（），（），最小累計(jì)權(quán)值，給標(biāo)號(hào)為（，1），令，即=，12445331222V1(V1,0)V2(V1,1)V4(V1,2)V3(V2,4)223V5(V3,5)V6（3）的有向弧有（），（），（）,給標(biāo)號(hào)（，2），。（4）的有向弧有（），（）,給標(biāo)號(hào)（，4），。（5）的有向弧有（），（）,給標(biāo)號(hào)（，4），。（6）不存在有向弧，而還未標(biāo)號(hào)，表明不能到達(dá)，到

27、，的最短路按標(biāo)號(hào)逆向追索可得。10.13 解：（1）(i) 從出發(fā)，標(biāo)號(hào)為（，0），令=，其余各點(diǎn)集合為。(ii) 的有向弧有（），（），（）,給標(biāo)號(hào)（，1），令。（iii）的有向弧有（），（），（）,給標(biāo)號(hào)（，3），令。V4413341624367V1(V1,0)V2(V1,4)V7(V1,3)V5(V1,1)V6(V5,7)V8(V6,10)V3（iv）依據(jù)上述規(guī)則，依次標(biāo)號(hào)（，4），（，7），（，10）。此時(shí)， 。（v）不存在有向弧，標(biāo)號(hào)終止，采用逆向標(biāo)號(hào)追索，得到到各點(diǎn)的最短路為： V2 ： V2 ； V5 ： V5 ； V7 ： V7 ； V6 ： V5 ； V8 ： 。（2）依據(jù)（

28、1）中的標(biāo)號(hào)結(jié)果，標(biāo)號(hào)終止時(shí)，依然沒(méi)有標(biāo)號(hào)，表明出發(fā)，不能到達(dá)。10.14 解：尋求鋪油管線(xiàn)最短問(wèn)題，可轉(zhuǎn)化為含有8個(gè)點(diǎn)的賦權(quán)完全圖的最小樹(shù)求解問(wèn)題。可采用破圈法和避圈法求解。以下采用避圈法求解。（1）從出發(fā)，令=，其余各點(diǎn)集合為，從表中劃去第一列。（2）尋求的最短邊，從表中第一行尋找最小值，最小，令，從表中劃去第5列。（3）尋找的最短邊，從表中第一行，第五行尋找最小值，最小值為，令，劃去表中第4列，。V1V2V3V4V5V6V7V8V1V2V3V4X1.32.10.91.3X0.91.82.10.9X2.60.91.82.6X0.71.21.70.71.82.62.51.62.02.31.9

29、1.51.51.11.00.9V5V6V7V8 0.71.82.01.51.22.62.31.11.72.51.91.00.71.61.50.9X0.91.10.80.9X0.61.01.10.6X0.50.81.00.5X(4) 尋找的最短邊，在表中V中元素各行中尋找最小值得到（即從第1，4，5行尋找），令，劃去表中第8行。（5）按照（4）依次進(jìn)行操作，直到為止，得到結(jié)果如下圖：0.90.70.90.80.51.00.9V1V4V5V6V7V8V3V2鋪設(shè)輸油管線(xiàn)全線(xiàn)長(zhǎng)為：S=d01+d15+d54+d56+d58+d87+d83+d32 = 5+0.9+0.7+0.9+0.8+0.5+1.

30、0+0.9=10.7(哩)10.15 解：= （）構(gòu)造= ，其中 同理構(gòu)造=（），=得到=，則矩陣為從到城市的最便宜原價(jià)為，其路線(xiàn)為：10.16解：（1）所有的截集（割集） ； ； ； ； （3，3）（5，2）（1，0）（4，3）（3，1）（3，2）（2，2）（2）對(duì)應(yīng)（1）中所有截集的容量為：6，7，7，5，8，所以最小截集為，其容量為5。（3）圖中指出流的流量為非作歹，由定理最大流等于最小割容量可知當(dāng)前流是最大流。也可用標(biāo)號(hào)法證明不存在增廣鏈，而說(shuō)明當(dāng)前流是最大流。（i）給標(biāo)號(hào)（ii）檢查相鄰的弧，弧已達(dá)容量，不滿(mǎn)足標(biāo)號(hào)條件中，弧，給標(biāo)號(hào)，即標(biāo)號(hào)（iii）檢查，弧不滿(mǎn)足標(biāo)號(hào)條件中，弧，給標(biāo)

31、號(hào)，即標(biāo)號(hào)。（iv）檢查 ，弧，均不滿(mǎn)足標(biāo)號(hào)條件中，標(biāo)號(hào)終止，因?yàn)?，所以不存在的增廣鏈，當(dāng)前流為最大流。10.17解： （1）給標(biāo)號(hào)。（2）檢查，在弧上，給標(biāo)號(hào)，即標(biāo)號(hào)，弧，給標(biāo)號(hào)?；。o標(biāo)號(hào)（1，1）（3，2）（4,3）（5,3）（3,2）（7,6）（8,3）（4,2）（4,3）（3,2）（4,3）（3,2）（4，1）：（3）檢查，弧，；不符合標(biāo)號(hào)條件。檢查，弧，給標(biāo)號(hào)；弧，給標(biāo)號(hào)。檢查，弧，給標(biāo)號(hào)。得到增廣鏈，修改調(diào)整原流量，正向弧流量增加1，反向弧減少1，得到（1，1）（3，2）（4,4）（5,3）（3,2）（7,7）（8,3）（4,2）（4,3）（3,3）（4,3）（3,2）（5，1）

32、：對(duì)流進(jìn)行標(biāo)號(hào)檢查，尋找增廣鏈。給標(biāo)號(hào)；檢查，標(biāo)記，標(biāo)記；檢查，標(biāo)記；檢查，標(biāo)記；檢查，無(wú)滿(mǎn)足條件弧。檢查，標(biāo)記，；得到增廣鏈，調(diào)整流量=1得到流量。（1，1）（3，2）（4,4）（5,3）（3,2）（7,7）（8,4）（4,3）（4,4）（3,3）（4,3）（3,2）（5，1）：對(duì)進(jìn)行標(biāo)號(hào)，尋找增廣鏈，得增廣鏈，調(diào)整流量得。（1，1）（3，3）（4,4）（5,4）（3,2）（7,7）（8,5）（4,3）（4,4）（3,3）（4,4）（3,2）：對(duì)檢查，已不存在增廣鏈，該網(wǎng)絡(luò)的最大流f=15。10.18解：（a）2(2)2(2)2(0)2(1)2(1)2(2)1(1)2(0)1(1)2(1)1

33、(1)1(0)(a1)（1）給標(biāo)號(hào)檢查,弧,均已滿(mǎn)容量，不符合標(biāo)記條件，弧，標(biāo)記。（3）檢查，弧，標(biāo)記，弧為逆向弧，不符合標(biāo)記條件。2(2)2(2)2(0)2(1)2(1)2(2)1(1)2(1)1(1)2(2)1(1)1(1)(a2)（4）檢查，弧，給標(biāo)號(hào)。（5）已得到標(biāo)號(hào)，反向追索得增廣鏈，修正調(diào)整流量，正向弧流量增加1，反向弧減少1。得新流對(duì)標(biāo)記，檢查點(diǎn)，已無(wú)符合標(biāo)記條件的弧，表明不存在增廣鏈，當(dāng)前流為最大流，的最大流為5，最小割為（b）5(2)5(4)5(5)5(4)5(3)4(4)3(3)2(2)1(1)1(1)2(2)3(2)4(3)5(5)(1) 給標(biāo)號(hào)(2) 檢查,弧,，均已滿(mǎn)

34、容量，不符合標(biāo)記條件，弧，標(biāo)記。 (3) 檢查，弧，標(biāo)記；弧，已達(dá)容量，不標(biāo)記。檢查，弧，不標(biāo)記，已達(dá)容量；弧，給標(biāo)號(hào)。檢查，弧，不滿(mǎn)足標(biāo)記條件；弧，給標(biāo)號(hào)。檢查，弧，給標(biāo)號(hào)。(4) 已得到標(biāo)號(hào)，反向追索得增廣鏈，增廣鏈正向弧流量+1，反向弧-1，調(diào)整得到新流。5(3)5(5)5(5)5(4)5(4)4(4)3(3)2(2)1(1)1(1)2(2)3(3)4(3)5(5)重新開(kāi)始標(biāo)號(hào)。 標(biāo)記，檢查，標(biāo)記，其它相連弧均不符合條件。 檢查，弧，標(biāo)記。 檢查，所有弧均不符合標(biāo)記條件，標(biāo)記結(jié)束。未標(biāo)記，現(xiàn)流量不存在增廣鏈，現(xiàn)流量為最大流，最小割為。（c）3(2)3(3)4(4)2(2)2(0)8(6)

35、6(6)5(4)6(4)3(3)5(5)_）2(0)（4，1）首先標(biāo)記。檢查,弧,均已滿(mǎn)容量，不符合標(biāo)記條件，弧，標(biāo)記。檢查，弧，標(biāo)記。檢查，反向弧，標(biāo)號(hào)。檢查，反向弧，標(biāo)號(hào)。檢查，弧，標(biāo)記。檢查，弧，標(biāo)記。已得到標(biāo)號(hào)，反向追索得增廣鏈，流量調(diào)整量為 1。得新流。3(3)3(2)4(4)2(1)2(0)8(7)6(6)5(5)6(5)3(3)5(5)_）2(0)重新開(kāi)始標(biāo)號(hào)。 標(biāo)記，檢查，標(biāo)記，檢查，沒(méi)有滿(mǎn)足標(biāo)記條件的弧，標(biāo)記結(jié)束。未標(biāo)記，現(xiàn)流量不存在增廣鏈，現(xiàn)流量為最大流，最小割為。（d）首先標(biāo)記。檢查,弧,標(biāo)記?；?，標(biāo)記。檢查，弧，標(biāo)記?；?，標(biāo)記。檢查，弧，標(biāo)記。檢查，反向弧，標(biāo)記。檢查，

36、弧，標(biāo)號(hào)。12（10）6（5）3（3）5（4）5（4）4（4）3（3）4（3）5（4）2（2）2（2）9（9）9（6）已得到標(biāo)號(hào)，反向追索得增廣鏈，流量調(diào)整量為 1。得新流。12（10）6（6）3（3）5（4）5（5）4（4）3（3）4（3）5（4）2（2）2（2）9（9）9（7）重新開(kāi)始標(biāo)號(hào)。 標(biāo)記，檢查,弧,標(biāo)記。 檢查，弧，標(biāo)記，弧，標(biāo)記。檢查，反向弧，標(biāo)記檢查，反向弧，標(biāo)記 檢查，無(wú)可標(biāo)記點(diǎn)，標(biāo)記終止，未標(biāo)記，當(dāng)前流最大流，最小割為10.19解：將5種語(yǔ)言和5個(gè)人各作為一點(diǎn)，它們的匹配關(guān)系見(jiàn)圖，增加一個(gè)起點(diǎn)s，和一個(gè)終點(diǎn)t，就構(gòu)成一個(gè)網(wǎng)絡(luò)圖戊德S丁丙甲乙日英俄法t招聘人員問(wèn)題就變?yōu)榍笊?/p>

37、述網(wǎng)絡(luò)圖的最大流。圖中所有弧的容量為1，設(shè)定的初始流量1(1) 1(1) 1(1) 1(0) 1(1) 1(1) 161(1) 1(0) 1(1) 1(0) 1(0) 1(0) 1(1) 1(0) 1(1) 1(1) 1(0) 1(1) 1(0) 1(1) S543210987t(9,1)(s,1)(10,1)(4,1)(4,1)1(0) 標(biāo)記。檢查s點(diǎn),弧,標(biāo)記。檢查4點(diǎn)，標(biāo)記9（4，1）。標(biāo)記10（4，1）。檢查9點(diǎn)，標(biāo)記3（9，1）。檢查10點(diǎn)，標(biāo)記5（10，1），檢查3點(diǎn)，5點(diǎn)，無(wú)滿(mǎn)足標(biāo)記條件中的弧，標(biāo)記終止，當(dāng)前流為最大流，只招聘4人，10.20解：（a）（1）從流量開(kāi)始（圖a1），

38、構(gòu)適費(fèi)用加權(quán)網(wǎng)絡(luò)圖。按照標(biāo)號(hào)法求解s-t的最短路為，根據(jù)各弧容量調(diào)整到，見(jiàn)圖a2。（2）構(gòu)造費(fèi)用加權(quán)網(wǎng)絡(luò)，（見(jiàn)圖a4），求解其最短路線(xiàn)為：，調(diào)整增廣鏈上流量。得到流量，（見(jiàn)圖a5）(3)重復(fù)上述過(guò)程，最短路線(xiàn)，得流量，7(0)4(0)3(0)2(0)5(0)6(0)8(0)ts(a1)：f0=0t(3,6)6123214(2,3)(1,4)s(s,0)(s,1)(a2)：W(f0)7(0)4(3)3(3)2(0)5(3)6(3)8(0)ts(a3)：f1=3t(3,6)6-11-232 -21-14(s,4)(2,4)s(s,0)(s,1)(a4)：W(f1)7(0)4(4)3(3)2(1)5

39、(4)6(3)8(0)ts(a5)：f2=4t(3,7)6-1-23 -32 -21-14(s,4)(1,5)s(s,0)(1,2)(a6)：W(f2)7(0)4(4)3(3)2(1)5(5)6(4)8(1)ts(a7)：f3=5t(2,8)6-1-23 -3-2 1-14 -4(s,4)(2,5)s(s,0)(1,2)(a8)：W(f3)7(3)4(4)3(0)2(1)5(5)6(4)8(4)ts(a9)：f4=8t(2,8)-66-123 -3-2 1-14 -4(s,4)(1,5)s(s,0)(3,2)(a10)：W(f4)7(4)4(4)3(0)2(0)5(5)6(5)8(5)ts(a

40、11)：f5=9t-66-123 -2 1-14 -4(s,4)(1,5)s(s,0)(a12)：W(f5)構(gòu)造的費(fèi)用加權(quán)圖，無(wú)法找到的最短路，即不存在增廣鏈，所以流是網(wǎng)絡(luò)最小費(fèi)用最大流。（b）從流量開(kāi)始（圖b1），構(gòu)造費(fèi)用加權(quán)網(wǎng)絡(luò)圖。按照標(biāo)號(hào)法求解的最短路為，根據(jù)最短路上的最小容量調(diào)整流量得，見(jiàn)圖b3。（2）構(gòu)造費(fèi)用加權(quán)網(wǎng)絡(luò)，（見(jiàn)圖b4），求解其最短路線(xiàn)為：，調(diào)整增廣鏈上流量。得到流量，（見(jiàn)圖b5）7(0)5(0)5(0)8(0)7(0)5(0)10(0)7(0)10(0)st(b1)：f0=07314239210S(s,0)(1,5)(3,8)t(4,11)(b2)：W(f0)(s,2)(

41、2,6)7(0)5(5)5(5)8(0)7(5)5(5)10(0)7(5)10(0)st(b3)：f1=57-3-142 -2-39-2 210S(s,0)(3,8)(3,11)t(3,18)(b4)：W(f1)(s,2)(1,9)7(2)5(5)5(5)8(0)7(5)5(5)10(2)7(7)10(0)st(b5)：f2=7(2,7)(1,14)-77-3-142 -2-39 -9-2 10S(s,0)(s,10)(2,14)t(3,23)(b6)：W(f2)7(7)5(0)5(5)8(0)7(5)5(5)10(7)7(7)10(5)st(b7)：f2=1310.21解：A，B為發(fā)點(diǎn)，有貨

42、物為50和40單位，D，E為收點(diǎn)，需要貨物30和60單位，C為轉(zhuǎn)運(yùn)點(diǎn)，現(xiàn)假設(shè)一個(gè)總的發(fā)點(diǎn)S，向A，B分別送貨50，40單位，費(fèi)用為0，再假設(shè)一個(gè)總收點(diǎn)t，分別收到C，D的貨為30，60單位，運(yùn)輸費(fèi)用為0，那么，轉(zhuǎn)動(dòng)問(wèn)題就轉(zhuǎn)化為求點(diǎn)網(wǎng)絡(luò)圖的最小費(fèi)用最大流問(wèn)題。SABCDET(20,90)(80,10)(60,0)(10,30)(30,20)(30,0)(40,30)(50,40)(10,20)(40,0)(50,0)（1）從流量開(kāi)始，構(gòu)造費(fèi)用網(wǎng)絡(luò)圖（a）,用標(biāo)號(hào)法求得最短路線(xiàn)為，調(diào)整流量得新流量。SABCDET20(0)80(0)60(0)10(0)30(0)30(0)40(0)50(0)10(0)40(0)50(0)(a) ：f0=0SABCDET901003020030402000(b) ：W(f0)(s,0)(s,0)(s,0)(B,30)(C,40)(