圖與網(wǎng)絡(luò)-西安電子科技大學(xué)經(jīng)濟(jì)管理學(xué)院(編輯修改稿)
2025-02-27 03:15 本頁面
【文章內(nèi)容簡(jiǎn)介】 ， 此中 n= |V|⑸ T無圈，但在 T中任兩個(gè)不相鄰的頂點(diǎn)間添加 一條邊，則可構(gòu)成一條回路⑹ T連通，但去掉任一條邊后就不連通，即樹 T 是連通且邊數(shù)最小的圖（二） Kruskal算法（加邊法，破圈法）1. 算法思想：① 由 Th1(4)結(jié)論：若 |V| = n ， 則樹 T有 n1條邊且 無圈② 由 def 8， 最小生成樹 T*是具有最小權(quán)的生成樹 故可 E中各邊按權(quán)大小排列設(shè)為 W 1≤ W 2≤ … ≤ W m， 對(duì)應(yīng)？邊依次為 a1,a2, … am， 然后將 a1,a2, … 依次進(jìn)入集合 S， 直到獲得 S的生成樹 T為止（樹的判斷可由 Th1(4)結(jié)論），則此樹 T必為最小生成樹。設(shè) G=(V,A,W) ， |V| = n ， |A| = m S— 待生成的集合i — S 中進(jìn)入最小生成樹的邊序號(hào)j — 逐個(gè)進(jìn)入 S的 G的邊序號(hào)ei+1 — S 中進(jìn)入最小生成樹的邊j W j aj akl1 W 1 a1 a232 W 2 a2 a55… … … …m W m am a76 表 11對(duì) G中各邊按權(quán)大小順序排列，不妨設(shè)為 W 1≤ W 2≤ … ≤ W m填寫 W j對(duì)應(yīng)的各邊 aj 表 11S=φ ， i = 0， j=1{aj} ∪ S構(gòu)成回路？|S| = n1ei+1=aj S={ei+1} ∪ Si=i +1 j=j+1j=j+1T*=S打印 T*ENDYYNN圖 六例 5（教材 P218） 某大學(xué)準(zhǔn)備對(duì)其所屬的 7 個(gè)學(xué)院辦公室計(jì)算機(jī)聯(lián)網(wǎng)．這個(gè)網(wǎng)絡(luò)的可能聯(lián)通的途徑如圖七所示，圖中 V1， … ， V7表示 7個(gè)學(xué)院辦公室，邊 eij為可能聯(lián)網(wǎng)的途徑。邊上所賦的權(quán)數(shù)為這條路線的長(zhǎng)度（單位：百米）。試設(shè)計(jì)一局域網(wǎng)既能聯(lián)結(jié)七個(gè)學(xué)院辦公室，又能使網(wǎng)絡(luò)線路總長(zhǎng)度為最短。W j aj akl T*W 1 a1 a23 *W 2 a2 a35 *W 3 a3 a27 *W 4 a4 a17 *W 5 a5 a67 *W 6 a6 a37W 7 a7 a56W 8 a8 a57W 9 a9 a43 *W 10 a10 a45W 11 a11 a16G={V,E,W}, |V| =7, |E| = 11W =(ωij) ωij見圖解：依據(jù)各邊權(quán)自小到大排列建立表 12，求解過程見表 13，由表 13得知最小生成樹T*={a1,a2,a3,a4,a5,a9}W(T*)=1+2+3+3+7=19圖七表 12表 13 （例 5求解過程）例 6. 利用加邊法求圖八所示的無向圖 G之最小生成樹W j aj akl T*W 1 a1 a12 *W 2 a2 a13 *W 3 a3 a45 *W 4 a4 a23W 5 a5 a25 *W 6 a6 a24W 7 a7 a34W 8 a8 a35解： G={V,E,V}， |V| = 5 |E| = 8表 14V1V2V5V3V412234442圖 八表 15 （例 6求解過程）（三）丟邊法（破圈法）1. 算法原理： 丟邊法與加邊法相反，加邊法是以不形成回路為準(zhǔn)則將 S=φ 逐步加邊以形成樹，而由于按邊權(quán)愈小愈優(yōu)先加進(jìn)去，故為最小生成樹，而丟邊法則是 S= E以不形成回路為準(zhǔn)則逐步丟邊以形成樹，由于是按邊權(quán)愈大愈優(yōu)先丟掉，故同樣為最小生成樹。 設(shè) G=(V,E,W) ， |V| = n， |E| = m，l S — 待生成的集合（逐步丟邊） i — S 中丟掉邊的序號(hào) j — S 中保留邊的序號(hào) ei+1 — S 中丟到的邊 e1— S 中丟到的邊的全體（集合） fj+1 — S 中保留的邊 D — S 中保留邊的集合l 由于邊個(gè)數(shù)為 m， 樹含邊的個(gè)數(shù)為 n1， 故丟掉（形成回路）邊的個(gè)數(shù)為 m(n1)=mn+1， 以此為程序出口，標(biāo)志著最小生成樹形成l 依次從大到小按列同例 5表 12。G=(V,E,W) ， |V| = n， |E| = m， S= E， i=0， j=0， E1=φ, D=φ選 S中最大權(quán)之邊S中是否有包含 al的一個(gè)回路i=i +1 ei=al S= S {ei} E1=E1∪ {ei} T*=SE1打印 T*的邊序列j=j +1 fj=al D=D∪ {fi+1} i≥ mn1ENDNNYY圖 九例 6. （同例 5）用丟邊法求解求解過程見表 16，由于 mn+1=11(71)=5故 i=5時(shí)程序終止，由表知T*=S{e1~e5}={a1,a2,a3,a4,a5,a9}與前加邊法求解相同，詳可參考教材 P218的六個(gè)圖。表 16 （例 6求解價(jià)格）5=i=mn+1167。 最大流問題 由前知，一個(gè)指定了收點(diǎn)和發(fā)點(diǎn)的賦權(quán)圖 G 稱為網(wǎng)絡(luò)，在網(wǎng)絡(luò)設(shè)計(jì)中研究網(wǎng)絡(luò)的流量具有現(xiàn)實(shí)意義，如交通網(wǎng)絡(luò)的車流流量，通信網(wǎng)絡(luò)中的話務(wù)流量，金融網(wǎng)絡(luò)中的現(xiàn)金流量，控制網(wǎng)絡(luò)中的信息流量，供電網(wǎng)絡(luò)中的電流流量等。人們也常常希望知道在既定網(wǎng)絡(luò)中能允許通過的最大流量，以便對(duì)該網(wǎng)絡(luò)的利用程序作出評(píng)價(jià)，這就是所謂的網(wǎng)絡(luò)最大流問題。求解方法有雙標(biāo)號(hào)法，對(duì)偶圖法等。1．網(wǎng)絡(luò)中弧的容量與流量 def9：對(duì)于一個(gè)指定收、發(fā)點(diǎn)的賦權(quán)有向（無向）圖或網(wǎng)絡(luò) N＝（ V， A， C），弧 aij∈A 的最大允許通過能力稱為該弧的容量，記為 cij（ cij≥0 ），全體 cij構(gòu)成之集合記為 C；而通過邊 aij的實(shí)際流量成為流量，記為 fij，故有 0≤f ij≤c ij。顯然若fij≥c ij則網(wǎng)絡(luò) N在 aij邊將發(fā)生堵塞現(xiàn)象，這是人們希望能避免的現(xiàn)象。（一）基本概念（一）基本概念2．可行流與最大流 def10：設(shè)有網(wǎng)絡(luò) N＝（ V， A， C），稱f ={fij∣a ij∈A} 為網(wǎng)絡(luò) N上的流函數(shù)，簡(jiǎn)稱網(wǎng)絡(luò)流；滿足如下條件的網(wǎng)絡(luò)流稱為可行流，其中 v（ f）為網(wǎng)絡(luò) N可行流的總流量（凈流入量）。（ 1）容量限制條件：（ 2）流量守恒條件：說明：進(jìn)入節(jié)點(diǎn) vj的流量＝自節(jié)點(diǎn) vj流出的流量； fij≡0 之零流亦滿足上述條件，故零流以為可行流。3．順向弧、逆向弧與可增路 def11：設(shè) f是網(wǎng)絡(luò) N的一可行流， P是
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1