例要在這六個(gè)居民點(diǎn)之間設(shè)置通信線路網(wǎng)以保證居民點(diǎn)的ppt課件

1、例1 要在這六個(gè)居民點(diǎn)之間設(shè)置通訊線路網(wǎng)，以保證居民點(diǎn)的聯(lián)絡(luò)。每條邊代表兩居民點(diǎn)的道路，數(shù)字代表路長(zhǎng)。問(wèn)如何建立該通訊網(wǎng)，使聯(lián)網(wǎng)代價(jià)最小。51342v6v5v4v3v2v1 v6v4v5v3v2v12431556566根本概念和名詞圖：由假設(shè)干個(gè)不同的點(diǎn)頂點(diǎn)或節(jié)點(diǎn)與其中某些頂點(diǎn)的連線所組成的圖形權(quán)：圖中的每條邊都有一個(gè)詳細(xì)的數(shù)與之對(duì)應(yīng)，這些數(shù)為權(quán)，帶權(quán)的圖為賦權(quán)圖或網(wǎng)絡(luò)。邊與?。簝牲c(diǎn)之間不帶箭頭的連線稱(chēng)為邊，帶箭頭的連線稱(chēng)為弧。無(wú)向圖：一個(gè)圖G是由頂點(diǎn)和邊構(gòu)成的。有向圖：一個(gè)圖G是由頂點(diǎn)和弧構(gòu)成的。V和E分別是圖的頂點(diǎn)的集合和邊的集合，V=v1,v2,vn，E=e1,e2,em鏈：在無(wú)向圖中，

2、點(diǎn)與邊的交錯(cuò)序列vi1, ei1,vi2,vik-1,eik-1,vik稱(chēng)為連結(jié)vi1和vik的鏈。(eit為連結(jié)vit和vit+1的邊)途徑:vi1,ai1,vi2,vik-1,aik-1,vik是有向圖中一條鏈ait為從vit指向vit+1的弧，稱(chēng)之為從vi1到vik的途徑。弧的集合，A=a1,a2,am 回路：閉合的途徑稱(chēng)為回路。圈：閉合的鏈稱(chēng)為圈。連通圖：圖G中任何兩個(gè)點(diǎn)之間至少有一條鏈，稱(chēng)G為連通圖。樹(shù)：一個(gè)無(wú)圈的連通圖稱(chēng)為樹(shù)生成樹(shù)：假設(shè)G1=(V1,E1)是連通圖G2=(V2,E2)的生成子圖(即V1=V2，E1E2)，且G1本身是樹(shù)，那么稱(chēng)G1為G2的生成樹(shù)。鄰接矩陣：bij表示

3、圖G中從頂點(diǎn)vi到vj的弧無(wú)向圖只思索vi與vj間的邊的數(shù)目,那么矩陣B = (bij)稱(chēng)為圖G的鄰接矩陣。帶權(quán)鄰接矩陣：以wij表示網(wǎng)絡(luò)G中從頂點(diǎn)vi到vj的弧的權(quán)(無(wú)向網(wǎng)只思索vi與vj間的邊的權(quán)),當(dāng)vi到vj無(wú)弧或邊時(shí) ,wij=,那么矩陣W = (wij)稱(chēng)為圖G的帶權(quán)鄰接矩陣。算法步驟如下：1)把賦權(quán)圖G中的邊按權(quán)的非減次序陳列。最小生成樹(shù)：在賦權(quán)圖G中，求一棵生成樹(shù)使其總權(quán)最小，稱(chēng)此為圖G的最小生成樹(shù)。Kruskal算法思想及步驟：每次添加權(quán)盡量小的邊，使新的圖無(wú)圈，直到生成一棵樹(shù)為止，便得最小生成樹(shù)。最小生成樹(shù)與Kruskal算法思想2)按1)陳列的次序檢查G中的每一條邊,假設(shè)

4、這條邊與已得到的邊不產(chǎn)生圈，那么取這一條邊為解的一部分。3)假設(shè)已取到n-1條邊,算法終止。此時(shí)以V為頂點(diǎn)集,以取到的n-1條邊為邊集的圖即為最小生成樹(shù)。 v5v2v3v1v4v6124565566312453最短途徑與Dijkstra算法最短途徑問(wèn)題：在賦權(quán)有向圖G中，求一條總權(quán)最小的vi至vj的途徑的問(wèn)題。算法思想：假設(shè)v1,v2,.,vi,.,vj,.,vn是圖G從v1到vn的最短途徑，那么它的子路vi,.,vj一定是從vi到vj的最短途徑。算法步驟：1)假設(shè)網(wǎng)絡(luò)G有n個(gè)頂點(diǎn),用帶權(quán)的鄰接矩陣W來(lái)表示,W(i,j)表示從頂點(diǎn)vi到vj的弧或邊上的權(quán)值,不存在弧或邊的權(quán)值用表示。 S為已求

5、出的從始點(diǎn)vi出發(fā)的最短途徑的終點(diǎn)集合,初始形狀為空集。那么從vi出發(fā)到圖上其他各頂點(diǎn)vk能夠到達(dá)的最短途徑長(zhǎng)度的初值為:D(k)=minW(i,k)|vkV-i；2)選擇vj，使得：D(j)=minD(k)|vkV-S，vj就是當(dāng)前求得的一條從始點(diǎn)vi出發(fā)的最短途徑的終點(diǎn)。令S = Sj；3)修正從vi出發(fā)到集合V-S上任一頂點(diǎn)vk可達(dá)的最短途徑長(zhǎng)度。假設(shè)D(j)+W(j,k)D(k)，那么修正D(k)為：D(k)=D(j)+W(j,k)；4)反復(fù)操作2)、3)共n-1次，并記錄各最短途徑經(jīng)過(guò)的一切頂點(diǎn)。由此得到從始點(diǎn)vi到圖上其他各頂點(diǎn)的最短途徑是依途徑長(zhǎng)度遞增的序列。v6v1v2v3v4

6、v5510501030206010040例2 某公司運(yùn)用一種設(shè)備,此設(shè)備在一定年限內(nèi)隨時(shí)間推移逐漸損壞。保管此設(shè)備的時(shí)間越長(zhǎng),每年的維修費(fèi)就越大?，F(xiàn)假設(shè)該公司在第一年開(kāi)場(chǎng)時(shí)必需購(gòu)置一臺(tái)此設(shè)備,假設(shè)運(yùn)用此設(shè)備的時(shí)間為五年，設(shè)備的購(gòu)買(mǎi)費(fèi)和維修費(fèi)如下表： 不同運(yùn)用年限設(shè)備的維修費(fèi)(單位:萬(wàn)元)第一年到第五年的購(gòu)買(mǎi)價(jià)錢(qián)(單位:萬(wàn)元)年號(hào)12345價(jià)錢(qián)2020222223運(yùn)用年限0-11-22-33-44-5維修費(fèi)57121825問(wèn)：公司應(yīng)在哪一年購(gòu)買(mǎi)一臺(tái)新設(shè)備，使維修費(fèi)和新設(shè)備的購(gòu)置費(fèi)的總和最小。解 思索六個(gè)點(diǎn)v1、v2、v3、v4、v5、v6,其中vi表示在第i年初要購(gòu)買(mǎi)新設(shè)備。v6是虛設(shè)點(diǎn),表示在第5年底購(gòu)買(mǎi)新設(shè)備。從點(diǎn)vi引出指向點(diǎn)vi+1，vi+2，v6的弧,弧(vi,vj)表示第i年年初購(gòu)進(jìn)的新設(shè)備要運(yùn)用到第j年的年初?；?vi,vj)上所賦的權(quán)為第i年的購(gòu)置費(fèi)加上從第i年初到第j年初的維修總費(fèi)用。比如W(1, 4) = 20 + (5 + 7 + 12) = 44萬(wàn)元，如此計(jì)算可得到一切權(quán)值，見(jiàn)以下圖。本問(wèn)題