圖與網(wǎng)絡(luò)規(guī)劃ppt課件(參考版)
2025-01-20 17:00本頁(yè)面
【正文】 6 V2 V3 V5 V6 V4 2 3 8 5 3 V1 9 3 1 練習(xí) 用破圈法求下面網(wǎng)絡(luò)的最小樹(shù) 紅線邊及相連頂點(diǎn)構(gòu)成最短樹(shù) 最短樹(shù)長(zhǎng)等于 2+3+3+1+3=12 作業(yè) P224~P225： 2， 3； 。故架設(shè)長(zhǎng)度最短的線路就是從圖 76中尋找一顆最小支撐樹(shù)。 ? 分析：要使村鎮(zhèn)都通上電，各點(diǎn)之間必須連通。 ? 例 如圖 76， v1， v2， v3， v4， v5， v6， v7代表村鎮(zhèn)，它們之間連線表明各村鎮(zhèn)間現(xiàn)有道路交通情況，連線旁數(shù)字代表道路的長(zhǎng)度。 求一個(gè)賦權(quán)連通圖 G的最小支撐樹(shù)問(wèn)題稱為最小樹(shù)問(wèn)題。圖（ b）是（ a）的一個(gè)支撐樹(shù)。圖 74代表了滿足要求的一個(gè)電話線網(wǎng)。其次，若圖中有圈的話，從圈上任意去掉一條邊，余下的圖仍是連通的，這樣可以省去一條電話線。 ? 用五個(gè)點(diǎn)代表五個(gè)城市，如果在某兩個(gè)城市之間架設(shè)電話線，則在相應(yīng)的兩個(gè)點(diǎn)之間連一條邊，這樣一個(gè)電話線網(wǎng)就可以用一個(gè)圖來(lái)表示了。管理組織機(jī)構(gòu)、學(xué)科分類和一些決策過(guò)程往往都可以用樹(shù)圖的形式表示。樹(shù)圖的定義是無(wú)圈的連通圖。 ),( EVG ? （ 4） 賦權(quán)圖 — 圖 連同邊上的權(quán)總體。 指從 ； ),( ji vva ? ji vv ? （ 5） 網(wǎng)絡(luò) —— 指定了 起點(diǎn)、終點(diǎn)和中間點(diǎn) 的 連通 的 賦權(quán)有向圖 。根據(jù)實(shí) 際背景可賦予不同含義，如距離、時(shí)間、 費(fèi)用、容量等。 ( , )G V E?4. 余樹(shù) ：若 T是圖 G的部分樹(shù)，則從 G中去掉 T中所有的邊，所得到的子圖稱為 G中的 T的余樹(shù)，記為 。 2. 樹(shù) ：一個(gè)連通的無(wú)圈圖稱為樹(shù)；一個(gè)林的每個(gè)連通子圖都是一棵樹(shù)。 7. 強(qiáng)連通與非強(qiáng)連通 ：若在 D的任意兩點(diǎn)之間存在互通的路，則稱 D為強(qiáng)連通，否則稱為非強(qiáng)連通圖。除起點(diǎn)和終點(diǎn)外點(diǎn)均不相同的回路稱為 初等回路 。頂點(diǎn)都不相同的路稱為 初等路
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1