第二講圖論模型

第二講圖論模型第一頁，共九十八頁，編輯于2023年，星期一1.問題引入與分析1)98年全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽B題“最佳災(zāi)今年(1998年)夏天某縣遭受水災(zāi).為考察災(zāi)情、組織自救，縣領(lǐng)導(dǎo)決定，帶領(lǐng)有關(guān)部門負(fù)責(zé)人到全縣各鄉(xiāng)（鎮(zhèn)）、村巡視.巡視路線指從縣政府所在地出發(fā)，走遍各鄉(xiāng)（鎮(zhèn)）、村，又回到縣政府所在地的路線.情巡視路線”中的前兩個(gè)問題是這樣的：第二頁，共九十八頁，編輯于2023年，星期一1）若分三組（路）巡視，試設(shè)計(jì)總路程最短且各組盡可能均衡的巡視路線.2）假定巡視人員在各鄉(xiāng)（鎮(zhèn)）停留時(shí)間T=2小時(shí)，在各村停留時(shí)間t=1小時(shí)，汽車行駛速度V=35公里/小時(shí).要在24小時(shí)內(nèi)完成巡視，至少應(yīng)分幾組；給出這種分組下最佳的巡視路線.第三頁，共九十八頁，編輯于2023年，星期一第四頁，共九十八頁，編輯于2023年，星期一2)問題分析：本題給出了某縣的公路網(wǎng)絡(luò)圖，要求的是在不同的條件下，災(zāi)情巡視的最佳分組方案和路線.將每個(gè)鄉(xiāng)（鎮(zhèn)）或村看作一個(gè)圖的頂點(diǎn)，各鄉(xiāng)鎮(zhèn)、村之間的公路看作此圖對(duì)應(yīng)頂點(diǎn)間的邊，各條再回到點(diǎn)O，使得總權(quán)（路程或時(shí)間）最小.公路的長(zhǎng)度（或行駛時(shí)間）看作對(duì)應(yīng)邊上的權(quán)，所給公路網(wǎng)就轉(zhuǎn)化為加權(quán)網(wǎng)絡(luò)圖，問題就轉(zhuǎn)化圖論中一類稱之為旅行售貨員問題，即在給定的加權(quán)網(wǎng)絡(luò)圖中尋找從給定點(diǎn)O出發(fā)，行遍所有頂點(diǎn)至少一次第五頁，共九十八頁，編輯于2023年，星期一如第一問是三個(gè)旅行售貨員問題，第二問是四本題是旅行售貨員問題的延伸－多旅行售貨員問題.本題所求的分組巡視的最佳路線，也就是m條眾所周知，旅行售貨員問題屬于NP完全問題，顯然本問題更應(yīng)屬于NP完全問題.有鑒于此，經(jīng)過同一點(diǎn)并覆蓋所有其他頂點(diǎn)又使邊權(quán)之和達(dá)到最小的閉鏈（閉跡）.個(gè)旅行售貨員問題.即求解沒有多項(xiàng)式時(shí)間算法.一定要針對(duì)問題的實(shí)際特點(diǎn)尋找簡(jiǎn)便方法，想找到解決此類問題的一般方法是不現(xiàn)實(shí)的，對(duì)于規(guī)模較大的問題可使用近似算法來求得近似最優(yōu)解.第六頁，共九十八頁，編輯于2023年，星期一2.圖論的基本概念1)圖的概念2)賦權(quán)圖與子圖3)圖的矩陣表示4)圖的頂點(diǎn)度5)路和連通第七頁，共九十八頁，編輯于2023年，星期一1)圖的概念

定義

一個(gè)圖G是指一個(gè)二元組(V(G),E(G))，其中:其中元素稱為圖G的頂點(diǎn).組成的集合，即稱為邊集,其中元素稱為邊.

定義圖G的階是指圖的頂點(diǎn)數(shù)|V(G)|,用來表示；圖的邊的數(shù)目|E(G)|用來表示.也用來表示邊是非空有限集，稱為頂點(diǎn)集，1)2)

E(G)是頂點(diǎn)集V(G)中的無序或有序的元素偶對(duì)表示圖，簡(jiǎn)記用第八頁，共九十八頁，編輯于2023年，星期一

定義若一個(gè)圖的頂點(diǎn)集和邊集都是有限集，則稱其為有限圖.只有一個(gè)頂點(diǎn)的圖稱為平凡圖，其他的所有圖都稱為非平凡圖.第九頁，共九十八頁，編輯于2023年，星期一

定義若圖G中的邊均為有序偶對(duì),稱G為有向邊為無向邊，稱e連接和，頂點(diǎn)和稱圖.稱邊為有向邊或弧,稱是從連接，稱為e的尾，稱為e的頭.若圖G中的邊均為無序偶對(duì)，稱G為無向圖.稱為e的端點(diǎn).既有無向邊又有有向邊的圖稱為混合圖.第十頁，共九十八頁，編輯于2023年，星期一

常用術(shù)語1)邊和它的兩端點(diǎn)稱為互相關(guān)聯(lián).2)與同一條邊關(guān)聯(lián)的兩個(gè)端點(diǎn)稱為相鄰的頂點(diǎn)，與同一個(gè)頂點(diǎn)點(diǎn)關(guān)聯(lián)的兩條邊稱為相鄰的邊.3)端點(diǎn)重合為一點(diǎn)的邊稱為環(huán)，端點(diǎn)不相同的邊稱為連桿.4)若一對(duì)頂點(diǎn)之間有兩條以上的邊聯(lián)結(jié)，則這些邊稱為重邊．5)既沒有環(huán)也沒有重邊的圖，稱為簡(jiǎn)單圖．第十一頁，共九十八頁，編輯于2023年，星期一

常用術(shù)語6)任意兩頂點(diǎn)都相鄰的簡(jiǎn)單圖,稱為完全圖.記為Kv.7)若，

，且X中任意兩頂點(diǎn)不，

相鄰，Y中任意兩頂點(diǎn)不相鄰，則稱為二部圖或偶圖；若X中每一頂點(diǎn)皆與Y中一切頂點(diǎn)相鄰,稱為完全二部圖或完全偶圖,記為(m=|X|,n=|Y|)．8)圖叫做星.二部圖第十二頁，共九十八頁，編輯于2023年，星期一2)賦權(quán)圖與子圖

定義若圖的每一條邊e

都賦以一個(gè)實(shí)數(shù)w(e)，稱w(e)為邊e的權(quán)，G連同邊上的權(quán)稱為賦權(quán)圖.

定義設(shè)和是兩個(gè)圖.1)若,稱是的一個(gè)子圖,記2)若，，則稱是的生成子圖.

3)若，且，以為頂點(diǎn)集，以兩端點(diǎn)均在中的邊的全體為邊集的圖的子圖，稱為的由導(dǎo)出的子圖，記為.4)若，且，以為邊集，以的端點(diǎn)集為頂點(diǎn)集的圖的子圖，稱為的由導(dǎo)出的邊導(dǎo)出的子圖，記為.第十三頁，共九十八頁，編輯于2023年，星期一3)若，且，以為頂點(diǎn)集，以兩端點(diǎn)均在中的邊的全體為邊集的圖的子圖，稱4)若，且，以為邊集，以的端點(diǎn)集為頂點(diǎn)集的圖的子圖，稱為的由導(dǎo)出的邊導(dǎo)出的子圖，記為.為的由導(dǎo)出的子圖，記為.第十四頁，共九十八頁，編輯于2023年，星期一3)圖的矩陣表示

鄰接矩陣:1)對(duì)無向圖，其鄰接矩陣，其中：(以下均假設(shè)圖為簡(jiǎn)單圖).第十五頁，共九十八頁，編輯于2023年，星期一2)對(duì)有向圖,其鄰接矩陣,其中：第十六頁，共九十八頁，編輯于2023年，星期一其中：3)對(duì)有向賦權(quán)圖,其鄰接矩陣,對(duì)于無向賦權(quán)圖的鄰接矩陣可類似定義.第十七頁，共九十八頁，編輯于2023年，星期一關(guān)聯(lián)矩陣1)對(duì)無向圖，其關(guān)聯(lián)矩陣,其中：第十八頁，共九十八頁，編輯于2023年，星期一2)對(duì)有向圖，其關(guān)聯(lián)矩陣,其中：第十九頁，共九十八頁，編輯于2023年，星期一4)圖的頂點(diǎn)度定義1)在無向圖G中，與頂點(diǎn)v關(guān)聯(lián)的邊的數(shù)目(環(huán)算兩次),稱為頂點(diǎn)v的度或次數(shù)，記為d(v)或dG(v).稱度為奇數(shù)的頂點(diǎn)為奇點(diǎn)，度為偶數(shù)的頂點(diǎn)為偶點(diǎn).2)在有向圖中，從頂點(diǎn)v引出的邊的數(shù)目稱為頂點(diǎn)

v的出度，記為d+(v)，從頂點(diǎn)v引入的邊的數(shù)目稱為

v的入度，記為d-(v).稱d(v)=d+(v)+d-(v)為頂點(diǎn)v的

度或次數(shù)．定理的個(gè)數(shù)為偶數(shù)．推論任何圖中奇點(diǎn)第二十頁，共九十八頁，編輯于2023年，星期一5)路和連通定義1)無向圖G的一條途徑（或通道或鏈）是指一個(gè)有限非空序列，它的項(xiàng)交替

地為頂點(diǎn)和邊，使得對(duì)，的端點(diǎn)是和,稱W是從到的一條途徑，或一條途徑.整數(shù)k稱為W的長(zhǎng).頂點(diǎn)和分別稱為起點(diǎn)和終點(diǎn),而稱為W的內(nèi)部頂點(diǎn).2)若途徑W的邊互不相同但頂點(diǎn)可重復(fù)，則稱W為跡或簡(jiǎn)單鏈.3)若途徑W的頂點(diǎn)和邊均互不相同，則稱W為路或路徑.一條起點(diǎn)為,終點(diǎn)為的路稱為路記為第二十一頁，共九十八頁，編輯于2023年，星期一定義1)途徑中由相繼項(xiàng)構(gòu)成子序列稱為途徑W的節(jié).

2)起點(diǎn)與終點(diǎn)重合的途徑稱為閉途徑.

3)起點(diǎn)與終點(diǎn)重合的的路稱為圈(或回路)，長(zhǎng)為k的圈稱為k階圈，記為Ck.

4)若在圖G中存在(u,v)路，則稱頂點(diǎn)u和v在圖G中連通.

5)若在圖G中頂點(diǎn)u和v是連通的，則頂點(diǎn)u和v之之間的距離d(u,v)是指圖G中最短(u,v)路的長(zhǎng)；若沒沒有路連接u和v，則定義為無窮大.第二十二頁，共九十八頁，編輯于2023年，星期一

6)圖G中任意兩點(diǎn)皆連通的圖稱為連通圖．

7)對(duì)于有向圖G，若，且有類似地，可定義有向跡，有向路和有向圈.頭和尾，則稱W為有向途徑.例在右圖中：途徑或鏈：跡或簡(jiǎn)單鏈：路或路徑：圈或回路：第二十三頁，共九十八頁，編輯于2023年，星期一3．最短路問題及算法最短路問題是圖論應(yīng)用的基本問題，很多實(shí)際問題，如線路的布設(shè)、運(yùn)輸安排、運(yùn)輸網(wǎng)絡(luò)最小費(fèi)用流等問題,都可通過建立最短路問題模型來求解.最短路的定義最短路問題的兩種方法：Dijkstra和Floyd算法.1)求賦權(quán)圖中從給定點(diǎn)到其余頂點(diǎn)的最短路.2)求賦權(quán)圖中任意兩點(diǎn)間的最短路.第二十四頁，共九十八頁，編輯于2023年，星期一

2)在賦權(quán)圖G中，從頂點(diǎn)u到頂點(diǎn)v的具有最小權(quán)定義1)若H是賦權(quán)圖G的一個(gè)子圖，則稱H的各邊的權(quán)和為H的權(quán).類似地，若稱為路P的權(quán)．若P(u,v)是賦權(quán)圖G中從u到v的路,稱的路P*(u,v)，稱為u到v的最短路．

3)把賦權(quán)圖G中一條路的權(quán)稱為它的長(zhǎng)，把(u,v)路的最小權(quán)稱為u和v之間的距離，并記作d(u,v).第二十五頁，共九十八頁，編輯于2023年，星期一1)賦權(quán)圖中從給定點(diǎn)到其余頂點(diǎn)的最短路假設(shè)G為賦權(quán)有向圖或無向圖，G邊上的權(quán)均非負(fù)．若，則規(guī)定最短路是一條路，且最短路的任一節(jié)也是最短路．求下面賦權(quán)圖中頂點(diǎn)u0到其余頂點(diǎn)的最短路．第二十六頁，共九十八頁，編輯于2023年，星期一Dijkstra算法:求G中從頂點(diǎn)u0到其余頂點(diǎn)的最短路.

1)置，對(duì)，，且.

2)對(duì)每個(gè)，用代替，計(jì)算，并把達(dá)到這個(gè)最小值的一個(gè)頂點(diǎn)記為，置

3)若，則停止；若，則用i+1代替i，并轉(zhuǎn)2).第二十七頁，共九十八頁，編輯于2023年，星期一Dijkstra算法:求G中從頂點(diǎn)u0到其余頂點(diǎn)的最短路.

1)置，對(duì)，，且.

2)對(duì)每個(gè)，用代替，計(jì)算，并把達(dá)到這個(gè)最小值的一個(gè)頂點(diǎn)記為，置

3)若，則停止；若，則用i+1代替i，并轉(zhuǎn)2).第二十八頁，共九十八頁，編輯于2023年，星期一Dijkstra算法:求G中從頂點(diǎn)u0到其余頂點(diǎn)的最短路.

1)置，對(duì)，，且.

2)對(duì)每個(gè)，用代替，計(jì)算，并把達(dá)到這個(gè)最小值的一個(gè)頂點(diǎn)記為，置

3)若，則停止；若，則用i+1代替i，并轉(zhuǎn)2).第二十九頁，共九十八頁，編輯于2023年，星期一Dijkstra算法:求G中從頂點(diǎn)u0到其余頂點(diǎn)的最短路.

1)置，對(duì)，，且.

2)對(duì)每個(gè)，用代替，計(jì)算，并把達(dá)到這個(gè)最小值的一個(gè)頂點(diǎn)記為，置

3)若，則停止；若，則用i+1代替i，并轉(zhuǎn)2).第三十頁，共九十八頁，編輯于2023年，星期一Dijkstra算法:求G中從頂點(diǎn)u0到其余頂點(diǎn)的最短路.

1)置，對(duì)，，且.

2)對(duì)每個(gè)，用代替，計(jì)算，并把達(dá)到這個(gè)最小值的一個(gè)頂點(diǎn)記為，置

3)若，則停止；若，則用i+1代替i，并轉(zhuǎn)2).第三十一頁，共九十八頁，編輯于2023年，星期一Dijkstra算法:求G中從頂點(diǎn)u0到其余頂點(diǎn)的最短路.

1)置，對(duì)，，且.

2)對(duì)每個(gè)，用代替，計(jì)算，并把達(dá)到這個(gè)最小值的一個(gè)頂點(diǎn)記為，置

3)若，則停止；若，則用i+1代替i，并轉(zhuǎn)2).第三十二頁，共九十八頁，編輯于2023年，星期一Dijkstra算法:求G中從頂點(diǎn)u0到其余頂點(diǎn)的最短路.

1)置，對(duì)，，且.

2)對(duì)每個(gè)，用代替，計(jì)算，并把達(dá)到這個(gè)最小值的一個(gè)頂點(diǎn)記為，置

3)若，則停止；若，則用i+1代替i，并轉(zhuǎn)2).第三十三頁，共九十八頁，編輯于2023年，星期一Dijkstra算法:求G中從頂點(diǎn)u0到其余頂點(diǎn)的最短路.

1)置，對(duì)，，且.

2)對(duì)每個(gè)，用代替，計(jì)算，并把達(dá)到這個(gè)最小值的一個(gè)頂點(diǎn)記為，置

3)若，則停止；若，則用i+1代替i，并轉(zhuǎn)2).第三十四頁，共九十八頁，編輯于2023年，星期一Dijkstra算法:求G中從頂點(diǎn)u0到其余頂點(diǎn)的最短路.

1)置，對(duì)，，且.

2)對(duì)每個(gè)，用代替，計(jì)算，并把達(dá)到這個(gè)最小值的一個(gè)頂點(diǎn)記為，置

3)若，則停止；若，則用i+1代替i，并轉(zhuǎn)2).第三十五頁，共九十八頁，編輯于2023年，星期一Dijkstra算法:求G中從頂點(diǎn)u0到其余頂點(diǎn)的最短路.

1)置，對(duì)，，且.

2)對(duì)每個(gè)，用代替，計(jì)算，并把達(dá)到這個(gè)最小值的一個(gè)頂點(diǎn)記為，置

3)若，則停止；若，則用i+1代替i，并轉(zhuǎn)2).第三十六頁，共九十八頁，編輯于2023年，星期一Dijkstra算法:求G中從頂點(diǎn)u0到其余頂點(diǎn)的最短路.

1)置，對(duì)，，且.

2)對(duì)每個(gè)，用代替，計(jì)算，并把達(dá)到這個(gè)最小值的一個(gè)頂點(diǎn)記為，置

3)若，則停止；若，則用i+1代替i，并轉(zhuǎn)2).第三十七頁，共九十八頁，編輯于2023年，星期一Dijkstra算法:求G中從頂點(diǎn)u0到其余頂點(diǎn)的最短路.

1)置，對(duì)，，且.

2)對(duì)每個(gè)，用代替，計(jì)算，并把達(dá)到這個(gè)最小值的一個(gè)頂點(diǎn)記為，置

3)若，則停止；若，則用i+1代替i，并轉(zhuǎn)2).第三十八頁，共九十八頁，編輯于2023年，星期一第三十九頁，共九十八頁，編輯于2023年，星期一定義根據(jù)頂點(diǎn)v的標(biāo)號(hào)l(v)的取值途徑，使到v的最短路中與v相鄰的前一個(gè)頂點(diǎn)w，稱為v的先驅(qū)點(diǎn)，記為z(v),即z(v)=w.先驅(qū)點(diǎn)可用于追蹤最短路徑.例5的標(biāo)號(hào)過程也可按如下方式進(jìn)行：首先寫出左圖帶權(quán)鄰接矩陣因G是無向圖，故W是對(duì)稱陣．第四十頁，共九十八頁，編輯于2023年，星期一第四十一頁，共九十八頁，編輯于2023年，星期一第四十二頁，共九十八頁，編輯于2023年，星期一Dijkstra算法：求G中從頂點(diǎn)u0到其余頂點(diǎn)的最短路設(shè)G為賦權(quán)有向圖或無向圖，G邊上的權(quán)均均非負(fù).對(duì)每個(gè)頂點(diǎn)，定義兩個(gè)標(biāo)記（l(v)，z(v)），其中:l(v)：表從頂點(diǎn)u0到v的一條路的權(quán)．

z(v)：v的先驅(qū)點(diǎn)，用以確定最短路的路線.l(v)為從頂點(diǎn)u0到v的最短路的權(quán)．算法的過程就是在每一步改進(jìn)這兩個(gè)標(biāo)記，使最終S：具有永久標(biāo)號(hào)的頂點(diǎn)集.輸入:G的帶權(quán)鄰接矩陣w(u,v)備用-將求最短路與最短路徑結(jié)合起來:第四十三頁，共九十八頁，編輯于2023年，星期一算法步驟：l(v)u0vl(u)uw(u,v)第四十四頁，共九十八頁，編輯于2023年，星期一首先寫出帶權(quán)鄰接矩陣?yán)笙聢D從頂點(diǎn)u0到其余頂點(diǎn)的最短路．因G是無向圖，故W是對(duì)稱陣．第四十五頁，共九十八頁，編輯于2023年，星期一第四十六頁，共九十八頁，編輯于2023年，星期一見Matlab程序-Dijkstra.doc第四十七頁，共九十八頁，編輯于2023年，星期一2)求賦權(quán)圖中任意兩頂點(diǎn)間的最短路算法的基本思想（I）求距離矩陣的方法.（II）求路徑矩陣的方法.（III）查找最短路路徑的方法.Floyd算法：求任意兩頂點(diǎn)間的最短路.舉例說明第四十八頁，共九十八頁，編輯于2023年，星期一

算法的基本思想

第四十九頁，共九十八頁，編輯于2023年，星期一（I）求距離矩陣的方法.第五十頁，共九十八頁，編輯于2023年，星期一（II）求路徑矩陣的方法.在建立距離矩陣的同時(shí)可建立路徑矩陣R．第五十一頁，共九十八頁，編輯于2023年，星期一（III）查找最短路路徑的方法.然后用同樣的方法再分頭查找．若：第五十二頁，共九十八頁，編輯于2023年，星期一（IV）Floyd算法：求任意兩頂點(diǎn)間的最短路.第五十三頁，共九十八頁，編輯于2023年，星期一例求下圖中加權(quán)圖的任意兩點(diǎn)間的距離與路徑.第五十四頁，共九十八頁，編輯于2023年，星期一插入點(diǎn)v1，得：矩陣中帶“=”的項(xiàng)為經(jīng)迭代比較以后有變化的元素.第五十五頁，共九十八頁，編輯于2023年，星期一插入點(diǎn)v2，得：矩陣中帶“=”的項(xiàng)為經(jīng)迭代比較以后有變化的元素.第五十六頁，共九十八頁，編輯于2023年，星期一插入點(diǎn)v3，得：第五十七頁，共九十八頁，編輯于2023年，星期一插入點(diǎn)v4，得：插入點(diǎn)v5，得：第五十八頁，共九十八頁，編輯于2023年，星期一插入點(diǎn)v6，得：第五十九頁，共九十八頁，編輯于2023年，星期一故從v5到v2的最短路為8

由v6向v5追溯:由v6向v2追溯:所以從到的最短路徑為：見Matlab程序-Floyd.doc第六十頁，共九十八頁，編輯于2023年，星期一4．最小生成樹及算法1)樹的定義與樹的特征定義連通且不含圈的無向圖稱為樹．常用T表示.樹中的邊稱為樹枝.樹中度為1的頂點(diǎn)稱為樹葉.孤立頂點(diǎn)稱為平凡樹.平凡樹第六十一頁，共九十八頁，編輯于2023年，星期一定理2設(shè)G是具有n個(gè)頂點(diǎn)的圖，則下述命題等價(jià)：1)G是樹（G無圈且連通）；2)G無圈，且有n-1條邊；3)G連通，且有n-1條邊；4)G無圈，但添加任一條新邊恰好產(chǎn)生一個(gè)圈;5)G連通，且刪去一條邊就不連通了（即G為最最小連通圖）；6)G中任意兩頂點(diǎn)間有唯一一條路.第六十二頁，共九十八頁，編輯于2023年，星期一2）圖的生成樹定義若T是包含圖G的全部頂點(diǎn)的子圖,它又是樹,則稱T是G的生成樹.圖G中不在生成樹的邊叫做弦.定理3圖G=(V,E)有生成樹的充要條件是圖G是連通的.證明

必要性是顯然的.第六十三頁，共九十八頁，編輯于2023年，星期一第六十四頁，共九十八頁，編輯于2023年，星期一（II）找圖中生成樹的方法可分為兩種：避圈法和破圈法A避圈法:深探法和廣探法B破圈法第六十五頁，共九十八頁，編輯于2023年，星期一A避圈法

定理3的充分性的證明提供了一種構(gòu)造圖的生成樹的方法.這種方法就是在已給的圖G中，每步選出一條邊使它與已選邊不構(gòu)成圈，直到選夠n-1條邊為止.這種方法可稱為“避圈法”或“加邊法”在避圈法中，按照邊的選法不同，找圖中生成樹的方法可分為兩種：深探法和廣探法.第六十六頁，共九十八頁，編輯于2023年，星期一a)深探法若這樣的邊的另一端均已有標(biāo)號(hào)，就退到標(biāo)號(hào)為步驟如下：i)在點(diǎn)集V中任取一點(diǎn)u,ii)若某點(diǎn)v已得標(biāo)號(hào)，檢端是否均已標(biāo)號(hào).若有邊vw之w未標(biāo)號(hào),則給w代v，重復(fù)ii).i-1的r點(diǎn),以r代v,重復(fù)ii),直到全部點(diǎn)得到標(biāo)號(hào)為止.給以標(biāo)號(hào)0.查一端點(diǎn)為v的各邊，另一w以標(biāo)號(hào)i+1，記下邊vw.令例用深探法求出下圖10的一棵生成樹

圖10012345678910111213第六十七頁，共九十八頁，編輯于2023年，星期一13a)深探法圖100123456789101112步驟如下：若這樣的邊的另一端均已有標(biāo)號(hào)，就退到標(biāo)號(hào)為i)在點(diǎn)集V中任取一點(diǎn)u,ii)若某點(diǎn)v已得標(biāo)號(hào)，檢端是否均已標(biāo)號(hào).若有邊vw之w未標(biāo)號(hào),則給w代v，重復(fù)ii).i-1的r點(diǎn),以r代v,重復(fù)ii),直到全部點(diǎn)得到標(biāo)號(hào)為止.給u以標(biāo)號(hào)0.查一端點(diǎn)為v的各邊，另一w以標(biāo)號(hào)i+1，記下邊vw.令例用深探法求出下圖10的一棵生成樹

第六十八頁，共九十八頁，編輯于2023年，星期一3b)廣探法步驟如下：i)在點(diǎn)集V中任取一點(diǎn)u,ii)令所有標(biāo)號(hào)i的點(diǎn)集為是否均已標(biāo)號(hào).對(duì)所有未標(biāo)號(hào)之點(diǎn)均標(biāo)以i+1,記下這些iii)對(duì)標(biāo)號(hào)i+1的點(diǎn)重復(fù)步步驟ii)，直到全部點(diǎn)得到給u以標(biāo)號(hào)0.Vi,檢查[Vi,V\Vi]中的邊端點(diǎn)邊.例用廣探法求出下圖10的一棵生成樹

圖101012213212234標(biāo)號(hào)為止.圖10第六十九頁，共九十八頁，編輯于2023年，星期一3b)廣探法步驟如下：i)在點(diǎn)集V中任取一點(diǎn)u,ii)令所有標(biāo)號(hào)i的點(diǎn)集為是否均已標(biāo)號(hào).對(duì)所有未標(biāo)號(hào)之點(diǎn)均標(biāo)以i+1,記下這些iii)對(duì)標(biāo)號(hào)i+1的點(diǎn)重復(fù)步步驟ii)，直到全部點(diǎn)得到給u以標(biāo)號(hào)0.Vi,檢查[Vi,V\Vi]中的邊端點(diǎn)邊.例用廣探法求出下圖10的一棵生成樹

圖101012213212234標(biāo)號(hào)為止.顯然圖10的生成樹不唯一.第七十頁，共九十八頁，編輯于2023年，星期一B破圈法相對(duì)于避圈法，還有一種求生成樹的方法叫做“破圈法”.這種方法就是在圖G中任取一個(gè)圈，任意舍棄一條邊，將這個(gè)圈破掉，重復(fù)這個(gè)步驟直到圖G中沒有圈為止.例用破圈法求出下圖的一棵生成樹.第七十一頁，共九十八頁，編輯于2023年，星期一B破圈法例用破圈法求出下圖的另一棵生成樹.不難發(fā)現(xiàn)，圖的生成樹不是唯一的.第七十二頁，共九十八頁，編輯于2023年，星期一3)最小生成樹與算法介紹最小樹的兩種算法：Kruskal算法（或避圈法）和破圈法.第七十三頁，共九十八頁，編輯于2023年，星期一AKruskal算法（或避圈法）步驟如下：1)選擇邊e1，使得w(e1)盡可能小；2)若已選定邊，則從中選取，使得:i)為無圈圖，

ii)是滿足i)的盡可能小的權(quán)，3)當(dāng)?shù)?)步不能繼續(xù)執(zhí)行時(shí)，則停止.定理4由Kruskal算法構(gòu)作的任何生成樹都是最小樹.第七十四頁，共九十八頁，編輯于2023年，星期一例10用Kruskal算法求下圖的最小樹.在左圖中權(quán)值最小的邊有任取一條在中選取權(quán)值最小的邊中權(quán)值最小邊有,從中選任取一條邊會(huì)與已選邊構(gòu)成圈,故停止,得中選取在中選取中選取.但與都第七十五頁，共九十八頁，編輯于2023年，星期一B破圈法算法2步驟如下：1)從圖G中任選一棵樹T1.2)加上一條弦e1，T1+e1中立即生成一個(gè)圈.去掉此圈中最大權(quán)邊，得到新樹T2,以T2代T1,重復(fù)2)再檢查剩余的弦，直到全部弦檢查完畢為止.例11用破圈法求下圖的最小樹.先求出上圖的一棵生成樹.

加以弦e2,得到的圈v1v3v2v1,去掉最大的權(quán)邊e2,得到一棵新樹仍是原來的樹；

再加上弦e7，得到圈v4v5v2v4,去掉最大的權(quán)邊e6，得到一棵新樹；如此重復(fù)進(jìn)行，直到全全部的弦均已試過,得最小樹.第七十六頁，共九十八頁，編輯于2023年，星期一5.旅行售貨員問題定義設(shè)G=(V,E)是連通無向圖，包含圖G的每個(gè)頂點(diǎn)的路稱為G的哈密爾頓路(Hamilton路或H路).包含圖G的每個(gè)頂點(diǎn)的圈，稱為G的哈密爾頓圈(或Hamilton圈或H圈).含Hamilton圈的圖稱為哈密爾頓圖(或Hamilton圖或H圖).第七十七頁，共九十八頁，編輯于2023年，星期一旅行售貨員問題或貨郎擔(dān)問題.一個(gè)旅行售貨員想去訪問若干城鎮(zhèn)，然后回到出發(fā)地.給定各城鎮(zhèn)之間的距離后，應(yīng)怎樣計(jì)劃他的旅行路線，使他能對(duì)每個(gè)城鎮(zhèn)恰好經(jīng)過一次而總距離最?。克蓺w結(jié)為這樣的圖論問題：在一個(gè)賦權(quán)完全圖中,找出一個(gè)最小權(quán)的H圈,稱這種圈為最優(yōu)圈.但這個(gè)問題是NP-hard問題，即不存在多項(xiàng)式時(shí)間算法.也就是說,對(duì)于大型網(wǎng)絡(luò)(賦權(quán)圖),目前還沒有一個(gè)求解旅行售貨員問題的有效算法，因此只能找一種求出相當(dāng)好（不一定最優(yōu)）的解.第七十八頁，共九十八頁，編輯于2023年，星期一一個(gè)可行的辦法:是先求一個(gè)H圈,然后適當(dāng)修改,以得到具有較小權(quán)的另一個(gè)H圈.第七十九頁，共九十八頁，編輯于2023年，星期一定義若對(duì)于某一對(duì)i和j，有則圈Cij將是圈C的一個(gè)改進(jìn).二邊逐次修正法:在接連進(jìn)行一系列修改之后,最后得一個(gè)圈,不能再用此方法改進(jìn)了，這個(gè)最后的圈可能不是最優(yōu)的,但是它是比較好的，為了得到更高的精度，這個(gè)程序可以重復(fù)幾次，每次都以不同的圈開始.這種方法叫做二邊逐次修正法.第八十頁，共九十八頁，編輯于2023年，星期一例對(duì)下圖16的K6,用二邊逐次修正法求較優(yōu)H圈.較優(yōu)H圈:其權(quán)為W(C3)=192第八十一頁，共九十八頁，編輯于2023年，星期一分析:找出的這個(gè)解的好壞可用最優(yōu)H圈的權(quán)的下界與其比較而得出.即利用最小生成樹可得最優(yōu)H圈的一個(gè)下界，方法如下：設(shè)C是G的一個(gè)最優(yōu)H圈，則對(duì)G的任一頂點(diǎn)v,C-v是G-v的路，也G-v是的生成樹.如果T是G-v的最小生成樹,且e1是e2與v關(guān)聯(lián)的邊中權(quán)最小的兩條邊,則w(T)+w(e1)+w(e2)將是w(C)的一個(gè)下界.取v=v3,得G-v3的一最小生成樹(實(shí)線),其權(quán)w(T)=122,與v3關(guān)聯(lián)的權(quán)最小的兩條邊為w(T)+w(v1v3)+w(v2v3)=178.故最優(yōu)H圈的權(quán)v1v3和v2v3,故w(C)應(yīng)滿足178w(C)192.第八十二頁，共九十八頁，編輯于2023年，星期一6.最佳災(zāi)情巡視路線的模型的建立與求解問題轉(zhuǎn)化為在給定的加權(quán)網(wǎng)絡(luò)圖中尋找從給定點(diǎn)O出發(fā),行遍所有頂點(diǎn)至少一次再回回到點(diǎn)O,使得總權(quán)(路程或時(shí)時(shí)間)最小,即最佳旅行售貨員問題.第八十三頁，共九十八頁，編輯于2023年，星期一最佳旅行售貨員問題是NP—完全問題,采用一種近似算法求其一個(gè)近似最優(yōu)解，來代替最優(yōu)解.算法一求加權(quán)圖的最佳旅行售貨員回路近似算法:1)用圖論軟件包求出G中任意兩個(gè)頂點(diǎn)間的最短路,構(gòu)造出完全圖2)輸入圖的一個(gè)初始H圈；3)用對(duì)角線完全算法（見[3]）產(chǎn)生一個(gè)初始圈;4)隨機(jī)搜索出中若干個(gè)H圈，例如2000個(gè)；5)對(duì)第2)，3)，4)步所得的每個(gè)H圈，用二邊逐次修正法進(jìn)行優(yōu)化，得到近似最優(yōu)H圈；6)在第5)步求出的所有H圈中，找出權(quán)最小的一個(gè),此即要找的最優(yōu)H圈的近似解.因二邊逐次修正法的結(jié)果與初始圈有關(guān),故本算法第2)，3)，4)步分別用三種方法產(chǎn)生初始圈，以保證能得到較優(yōu)的計(jì)算結(jié)果.第八十四頁，共九十八頁，編輯于2023年，星期一問題一若分為三組巡視，設(shè)計(jì)總路程最短且各組盡可能均衡的巡視路線.

此問題是多個(gè)售貨員的最佳旅行售貨員問題.4)第八十五頁，共九十八頁，編輯于2023年，星期一此問題包含兩方面：a)對(duì)頂點(diǎn)分組,b)在每組中求(單個(gè)售貨員)最佳旅行售貨員回路.因單個(gè)售貨員的最佳旅行售貨員回路問題不存存在多項(xiàng)式時(shí)間內(nèi)的精確算法.故多也不第八十六頁，共九十八頁，編輯于2023年，星期一而圖中節(jié)點(diǎn)數(shù)較多，為53個(gè)，我們只能去尋求一種較合理的劃分準(zhǔn)則，對(duì)圖1進(jìn)行粗步劃分后,求出各部分的近似最佳旅行售貨員回路的權(quán),再進(jìn)一進(jìn)一步進(jìn)行調(diào)整，使得各部分滿足均衡性條件3).