圖與網(wǎng)絡(luò)規(guī)劃ppt課件-資料下載頁
2025-01-17 17:00本頁面
【正文】 市都可以互相通話，并且電話線的根數(shù)最少。 ? 用五個點代表五個城市，如果在某兩個城市之間架設(shè)電話線，則在相應(yīng)的兩個點之間連一條邊，這樣一個電話線網(wǎng)就可以用一個圖來表示了。為了使任何兩個城市都可以通話，這樣的圖必須是連通的。其次，若圖中有圈的話，從圈上任意去掉一條邊，余下的圖仍是連通的，這樣可以省去一條電話線。因而，滿足要求的電話線網(wǎng)所對應(yīng)的圖必定是不含圈的連通圖。圖 74代表了滿足要求的一個電話線網(wǎng)。 如果 G1是 G2的部分圖，又是樹圖，則稱其是的支撐樹。圖（ b）是（ a）的一個支撐樹。樹圖的各條邊稱為樹枝（假定各邊都有權(quán)重），一般圖含有多個支撐樹，設(shè) T是 G的一棵支撐子樹，稱 T中所有邊的權(quán)之和為支撐樹 T的權(quán)，記為 w(T)，如果支撐樹 T*權(quán) w(T*)是 G所有支撐樹的權(quán)中最小的，則T*稱為 G的 最小支撐樹 (簡稱為最小樹 minimum spanning tree）。 求一個賦權(quán)連通圖 G的最小支撐樹問題稱為最小樹問題。求最小樹的方法有 : ?破圈法： 從網(wǎng)絡(luò)圖 N任取一回路，去掉這個回路中權(quán)數(shù)最大的一條邊，得一子網(wǎng)絡(luò)圖N1，在 N1中再取任一回路，再去掉回路中權(quán)數(shù)最大的一條邊，如此繼續(xù)下去，一直到剩下的子圖中 不再含回路 為止，該子圖就是 N的最小支撐樹。 ? 例 如圖 76， v1， v2， v3， v4， v5， v6， v7代表村鎮(zhèn)，它們之間連線表明各村鎮(zhèn)間現(xiàn)有道路交通情況，連線旁數(shù)字代表道路的長度?，F(xiàn)要求沿圖中道路架設(shè)電線，使每個村莊都通上電，應(yīng)如何架設(shè)使總的線路長度為最短。 ? 分析：要使村鎮(zhèn)都通上電，各點之間必須連通。又圖中必不存在圈，否則從圖中去掉一條邊，圖仍連通，原圖就一定不是最短線路。故架設(shè)長度最短的線路就是從圖 76中尋找一顆最小支撐樹。 總線路長度 =1+4+9+3+17+23=57。 6 V2 V3 V5 V6 V4 2 3 8 5 3 V1 9 3 1 練習(xí) 用破圈法求下面網(wǎng)絡(luò)的最小樹 紅線邊及相連頂點構(gòu)成最短樹 最短樹長等于 2+3+3+1+3=12 作業(yè) P224~P225： 2， 3；
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1