【文章內(nèi)容簡介】 定邊 ，則從 ieee ,..., 21 },...,{\ 21 ieeeE中選取 ，使得 : 1?iei) 為無圈圖， }],...,[{ 121 ?ieeeG ii) 是滿足 i)的盡可能小的權(quán)， )( 1?iew 3) 當(dāng)?shù)?2)步不能繼續(xù)執(zhí)行時，則停止 . 定理 4 由 Kruskal算法構(gòu)作的任何生成樹 }], . . . ,[{ 121* ?? ?eeeGT 都是最小樹 . 最小生成樹與算法 河南城建學(xué)院 例 用 Kruskal算法求下圖的最小樹 . 在左圖中 權(quán)值 },...,{ 821 eee最小的邊有 任取一條 , 51 ee ,1e 在 中選取權(quán)值 },...,{ 832 eee,5e最小的邊 中權(quán)值最小邊有 , 從中選 ：73,ee。3e任取一條邊 會與已選邊構(gòu)成圈 ,故停止 ,得 中選取在中選取 ,7e 中選取 . 但 與 都 }, 86 ee 84,ee 4e 8e},,{ 876432 eeeeee},{ 87642 eeeee,{ 42 ee在河南城建學(xué)院 B 破圈法 任取一個圈，從圈中去掉一條權(quán)最大的邊（如果有兩條或兩條以上的邊都是權(quán)最大的邊，則任意去掉其中一條）。在余下的圖中，重復(fù)這個步驟，直到得到一個不含圈的圖為止，這時的圖便是最小樹。 2 3 4 5 6 7 4 v3 v1 v2 v4 v5 v6 1 5 河南城建學(xué)院 2 3 4 5 6 7 4 v3 v1 v2 v4 v5 v6 1 5 2 3 4 5 6 4 v3 v1 v2 v4 v5 v6 1 5 2 3 4 5 6 4 v3 v1 v2 v4 v5 v6 1 5 2 3 4 5 4 v3 v1 v2 v4 v5 v6 1 5 河南城建學(xué)院 2 3 4 5 4 v3 v1 v2 v4 v5 v6 1 5 2 3 4 4 v3 v1 v2 v4 v5 v6 1 5 2 3 4 4 v3 v1 v2 v4 v5 v6 1 5 2 3 4 v3 v1 v2 v4 v5 v6 1 5 河南城建學(xué)院 最小生成樹實例 :有線電視網(wǎng)最優(yōu)布線問題 單位： 100米 : 衛(wèi)星加密電視的開播 ,受到大 家歡迎 ,要想收看加密電視必 須建一套有線電視網(wǎng)．我們 考慮這樣一個具體問題：設(shè) 某市六個個區(qū)之的相互距離 如下表所示，試確定表數(shù)據(jù) 形成的網(wǎng)絡(luò)中，如何布線能 布線最??？ 1 2 3 4 5 6 1 0 13 51 77 68 50 2 13 0 60 70 67 59 3 51 60 0 57 3 62 4 77 70 57 0 20 55 5 68 67 36 20 0 34 6 50 59 2 55 34 0 河南城建學(xué)院 最小生成樹實例 :有線電視網(wǎng)最優(yōu)布線問題 ２ .問題求解 : 最優(yōu)布線問題，就是要求任何兩地都有鏈相連，而使總線路最短，這個問題在圖論中也稱為最小樹題．作下圖，其中頂點 v1 ， v２ ， v３ ， v４ ， v５ ， v６ 分別表示兩區(qū)之間的距離． V1 V6 V3 V5 V4 V2 60 70 20 13 67 59 77 57 55 68 51 2 34 36 50 河南城建學(xué)院 最小生成樹實例 :有線電視網(wǎng)最優(yōu)布線問題 對于上圖，我們要找使布線最省的網(wǎng)絡(luò)模型．圖論中的破圈法可以解 決這個問題，具體過程如下：在圈 v1v２ v３ v1中，去掉最長邊 v２ v３ ＝ 60，同 樣去掉圈 v1v３ v６ v1， v２ v４ v５ v２ ， v３ v４ v５ v３ ， v3 v5v６ v3， v4v5 v6 v4， v1v3v4v1， v1v6v2v1， v2v5v6v2中最長的邊 v1v３ ＝ 51， v2v4＝ 70， v3v4＝ 57， v3v5＝ 36,v4v6＝ 55， v1v4＝ 77， v1v5＝ 68， v2v6＝ 59， v2v5＝ 67，最后構(gòu) 成的圖（如下）就是最省的 布線圖 ． 13 2 50 34 20 v2 v3 v1 v6 v4 v6 V1 V6 V3 V5 V4 V2 60 70 20 13 67 59 77 57 55 68 51 2 34 36 50 河南城建學(xué)院 167。 8 最短路徑問題及其應(yīng)用 最短路問題就是從給定的網(wǎng)絡(luò)圖中找出任意兩點間 距離最短的一條路，其中距離只是權(quán)數(shù)的代稱（在實際 網(wǎng)絡(luò)中，權(quán)數(shù)可指時間、費用等）。如選址、管道鋪設(shè) 時的選線、設(shè)備更新、投資等都可以歸給為求最短路的 問題。最短路問題有一個重要而明顯的性質(zhì)（ 算法思 想 ）：最短路是一條路徑，且最短路的任一段也是最短 路。 求最短路的方法： (1) 求從一點到其余各點間的 Dijkstra算法 。 (2) 求任意兩點間最短距離的 矩陣算法 (Floyd算法 )。 設(shè) G為賦權(quán)有向圖或無向圖， G邊上的權(quán)均非負(fù)。 河南城建學(xué)院 Dijkstra(標(biāo)號法）的算法： 迪克斯特拉 不妨用 表示圖中兩相鄰點 i和 j的距離；若點 I 和 j不相鄰，則可令 ，顯然 ；用 表示從 點 s到 i點的最短距離?，F(xiàn)要求從點到某一點 t的最 短路。 Dijkstra算法步驟如下 ： （１） 從點 s出發(fā)，因 ，將此值標(biāo)在 s旁，表示此點已標(biāo)號； （２）從 s點出發(fā)，找出與 s點相鄰的點中距離最小的一個，設(shè)為 r， 將 的值標(biāo)在 r旁，表示此點已標(biāo)； （３）從已標(biāo)號的點出發(fā)，找出與這些點相鄰的所有未標(biāo)號點 p。 若有 ，則對 p點標(biāo)號； （４）重復(fù)第三步，一直到 t點得到標(biāo)號為止。 矩陣算法步驟（略） ijdijd ?? 0iid ? siL0ssL ?sr ss srL L d??m in{ 。 }sp ss sp sr rpL L d L d? ? ?河南城建學(xué)院 例 求圖中頂點 v0與 v5的最短路徑 . 解 :可以將計算過程用一張表表示出來 (見下頁表 ) 算法示例 河南城建學(xué)院 由上表可知 ,v5與 v3相鄰 ,v3與 v4相鄰 ,v4與 v2相鄰 ,v2與 v1相鄰 ,v1與 v0相鄰 .這 樣從 v5往前追蹤 ,得 v0到 v5的最短路徑為： Γ=v0v1v2v4v3v5. W(Γ)=9. 河南城建學(xué)院 Dijkstra算法的標(biāo)號法舉例 2 10 7 3 6 4 5 2 10 7 3 6 4 5 2 2 10 7 3 6 4 5 2 10 7 3 6 4 5 10 ? 2 ? ? 9 5 2 2 5 5 9 9 9 9 0 0 0 0 河南城建學(xué)院 最短路徑問題實例：醫(yī)院選址問題 ： 新建居民小區(qū)的醫(yī)院 ， 對該區(qū)每一戶居民都很重要 。 如下圖是一個新 建居民區(qū)的示意圖 ， 醫(yī)院建在哪里為好呢 ？ V2 V1 V3 V5 V10 V7 V6 V4 V9 V8 9 3 2 1 8 2 7 9 5 6 4 8 1 3 1 6 5 河南城建學(xué)院 最短路徑問題實例： 醫(yī)院選址問題 在上圖中 ， v1， v２ ， … ， v10表示各居民點 ， 邊表示兩居民點之間的道路 ， 邊上的數(shù)值表示兩居民 點之間的距離 （ 也就是該邊的權(quán) ） . 現(xiàn)在需要我們考慮的問題是在這 10個居民點中 ， 何 處作為新建醫(yī)院的理想地址 ， 以使所建醫(yī)院到最遠(yuǎn)的 居民點距離盡可能近 （ 即最遠(yuǎn)點的病人到醫(yī)院看病時 走的路盡可能短 ） 。 河南城建學(xué)院 2. 問題求解： 顯然可以看出 ,上圖是一個連通無向圖，記為Ｇ＝｛Ｖ，Ｅ｝ . 任取 vi ∈ V(i=1,2, ……,10) ，考察 vi與Ｖ中其他頂點間的最短路（也稱為距離）：Ｐ ＊ （ vi， v１ ），Ｐ ＊ （ vi，v2）， …… ，Ｐ ＊ （ vi， v１０ ），把這 10個距離中最大的數(shù)稱為頂 vi的最大服務(wù)距離，記為 L(vi). 求出上圖中各點間的距離，如下表所示，這樣就可以把每個頂點 vi對應(yīng)的最大服務(wù)距離 L(vi)求出來 . 最短路徑問題實例： 醫(yī)院選址問題 河南城建學(xué)院 最短路徑問題實例 ： 醫(yī)院選址問題 1 2 3 4 5 6 7 8 9 10 1 0 5 3 6 5 10 10 9 12 13 2 5 0 2 3 4 9 6 8 8 9 3 3 2 0 3 2 7 7 6 9 10 4 6 3 3 0 5 7 5 6 7 8 5 5 4 2 5 0 5 5 4 7 8 6 10 9 7 7 5 0 2 1 4 5 7 10 6 7 5 5 2 0 1 2 3 8 9 8 6 6 4 1 1 0 3 4 9 12 8 9 7 7 4 2 3 0 5 10 13 9 10 8 8 5 3 4 5 0 河南城建學(xué)院 最短路徑問題實例 ： 醫(yī)院選址問題 注：上表中的１，２，３，４，５，６，７，８，９，１０分別代表 v1， v２ ， v３ ， v４ ， v５ ， v６ ， v７ ， v８ ， v９ ， v１０ v1到各頂點的距離就是上表中的第一行各數(shù)，它們中最大的是 13，所以 L(v1)=13，其它各點的最大服務(wù)距離分別為 : L(v2)=9， L(v3)=10， L(v4)=8，