版權(quán)說(shuō)明:本文檔由用戶(hù)提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
第6章圖與網(wǎng)絡(luò)分析
圖的基本概念與基本定理
樹(shù)和最小支撐樹(shù)
最短路問(wèn)題
網(wǎng)絡(luò)最大流
本章內(nèi)容重點(diǎn)
在實(shí)際的生產(chǎn)和生活中,人們?yōu)榱朔从呈挛镏g的關(guān)系,常常在紙上用點(diǎn)和線來(lái)畫(huà)出各式各樣的示意圖。
例:公路或鐵路交通圖、管網(wǎng)圖、通訊聯(lián)絡(luò)圖等各節(jié)點(diǎn)及聯(lián)系的邊。如果用點(diǎn)表示研究的對(duì)象,用邊表示這些對(duì)象之間的聯(lián)系,則圖G可以定義為點(diǎn)和邊的集合G={V,E}式中:V—點(diǎn)的集合,E—邊的集合如果給圖中的點(diǎn)和邊賦以具體的含義和權(quán)數(shù),如距離、費(fèi)用、容量等這樣的圖稱(chēng)為網(wǎng)絡(luò)圖。
1.圖的基本概念與模型
用點(diǎn)和點(diǎn)之間的線所構(gòu)成的圖,反映實(shí)際生產(chǎn)和生活中的某些特定對(duì)象之間的特定關(guān)系。一般來(lái)說(shuō),通常用點(diǎn)表示研究對(duì)象用點(diǎn)與點(diǎn)之間的線表示研究對(duì)象之間的特定關(guān)系。由于在一般情況下,圖中的相對(duì)位置如何,點(diǎn)與點(diǎn)之間線的長(zhǎng)短曲直,對(duì)于反映研究對(duì)象之間的關(guān)系,顯得并不重要,因此,圖論中的圖與幾何圖,工程圖等本質(zhì)上是不同的。如圖6-1所示:端點(diǎn),關(guān)聯(lián)邊,相鄰環(huán),多重邊,簡(jiǎn)單圖次,奇點(diǎn),偶點(diǎn),孤立點(diǎn)鏈,圈,路,回路,連通圖完全圖,偶圖子圖,部分圖例12.樹(shù)和最小支撐樹(shù)樹(shù)圖(簡(jiǎn)稱(chēng)樹(shù),記作T(V,E))在各種各樣的圖中,有一類(lèi)圖是十分簡(jiǎn)單又非常具有應(yīng)用價(jià)值的圖,這就是樹(shù)。
性質(zhì)1任何樹(shù)中必存在次為1的點(diǎn)。性質(zhì)2具有n個(gè)頂點(diǎn)的樹(shù)的邊數(shù)恰好為(n-1)條。性質(zhì)3任何具有n個(gè)點(diǎn)、(n-1)條邊的連通圖是樹(shù)圖。2.1樹(shù)的性質(zhì)2.2圖的最小部分樹(shù)如果G1是G2的部分圖,則稱(chēng)G1是G2的部分樹(shù)(或支撐樹(shù))。樹(shù)圖的各條邊稱(chēng)為樹(shù)枝(假定各邊均有權(quán)重),一般圖G2含有多個(gè)部分樹(shù),其中樹(shù)枝總長(zhǎng)最小的部分樹(shù),稱(chēng)為該圖的最小部分樹(shù)(也稱(chēng)最小支撐樹(shù))定理1圖中任一個(gè)點(diǎn)i,若j是與i相鄰點(diǎn)中距離最近的,則邊[i,j]一定必含在該圖的最小部分樹(shù)內(nèi)。推論把圖的所有點(diǎn)分成V和
兩個(gè)集合,則兩集合之間連線的最短邊一定含在最小部分樹(shù)內(nèi)。練習(xí):寫(xiě)下圖的樹(shù)圖v6v5v2v3v4v1v6v5v2v3v4v1練習(xí)用破圈法求出下圖的一個(gè)樹(shù)圖。V5V4V2V3V1e6e5e4e3e2e1e7e8
取一個(gè)圈(v1,v2,v3,v1),在一個(gè)圈中去掉邊e3
。在剩下的圖中,再取一個(gè)圈(v1,v2,v4,v3,v1),去掉邊e4
。再?gòu)娜Γ╲3,v4v5,v3)中去掉邊e6
。再?gòu)娜?/p>
(v1,v2,v5,v4,v3,v1
)中去掉邊e7,這樣,剩下的圖不含圈,于是得到一個(gè)支撐樹(shù),如下圖所示。v2e1e2e5e8v1v3v42.3避圈法和破圈法(1)避圈法從網(wǎng)絡(luò)圖中依次尋找權(quán)數(shù)較小的邊,尋找過(guò)程中,節(jié)點(diǎn)不得重復(fù),即不得構(gòu)成圈。注意在找較小權(quán)數(shù)邊時(shí)不考慮已選過(guò)的邊和可能造成圈的邊。如此反復(fù)進(jìn)行,直到得到最短樹(shù)或證明網(wǎng)絡(luò)不存在最短樹(shù)。在圖中尋找最小部分樹(shù)的步驟:P153(2)破圈法①在網(wǎng)絡(luò)圖中尋找一個(gè)圈。若不存在圈,則已經(jīng)得到最短樹(shù)或網(wǎng)絡(luò)不存在最短樹(shù);②去掉該圈中權(quán)數(shù)最大的邊;反復(fù)重復(fù)①②兩步,直到最短樹(shù)。練習(xí):用破圈法求出下圖的最小部分樹(shù)圖av6v5v2v3v4v1627535441v3v2v1v4v6v553142圖b最短路問(wèn)題最短路問(wèn)題是網(wǎng)絡(luò)理論中應(yīng)用最廣泛的問(wèn)題之一。許多優(yōu)化問(wèn)題都可以使用這個(gè)模型,如設(shè)備更新、管道的鋪設(shè)、線路的安排、廠區(qū)的布局等。最短路問(wèn)題的一般提法是:設(shè)為連通圖,圖中各邊有權(quán)(表示,之間沒(méi)有邊),
為圖中任意兩點(diǎn),求一條道路,使它是從到的所有路中總權(quán)最小的路。即:最小。最短路算法中1959年由(狄克斯特洛)提出的算法被公認(rèn)為是目前最好的方法,我們稱(chēng)之為算法。下面通過(guò)例子來(lái)說(shuō)明此法的基本思想。條件:所有的權(quán)數(shù)思路:逐步探尋。下求到的最短路:1)從出發(fā),向走。首先,從到的距離為0,給標(biāo)號(hào)(0)。畫(huà)第一個(gè)弧。(表明已標(biāo)號(hào),或已走出)從出發(fā),只有兩條路可走,其距離為2)①可能最短路為①給劃成粗線。③劃第二個(gè)弧。②
給標(biāo)號(hào)(4)。①②表明走出后走向的最短路目前看是,最優(yōu)距離是4?,F(xiàn)已考察完畢第二個(gè)圈內(nèi)的路,或者說(shuō),已完成的標(biāo)號(hào)。①②3)接著往下考察,有三條路可走:可選擇的最短路為①給劃成粗線。③劃第3個(gè)弧。②
給標(biāo)號(hào)(6)。③①②4)接著往下考察,有四條路可走:可選擇的最短路為①給劃成粗線。③劃第4個(gè)弧。②
給標(biāo)號(hào)(8)。①②③④5)接著往下考察,有四條路可走:可選擇的最短路為①給劃成粗線。③劃第5個(gè)弧。②
給標(biāo)號(hào)(9)。①②③④⑤6)接著往下考察,有四條路可走:可選擇的最短路為①給劃成粗線。③劃第6個(gè)弧。②
給標(biāo)號(hào)(13)。①②③④⑤⑥7)接著往下考察,有四條路可走:可選擇的最短路為①同時(shí)給劃成粗線。②分別給標(biāo)號(hào)(14)。最后,從逆尋粗線到,得最短路:長(zhǎng)度為14。最短路問(wèn)題的兩個(gè)應(yīng)用最短路問(wèn)題在圖論應(yīng)用中處于很重要的地位,下面舉兩個(gè)實(shí)際應(yīng)用的例子。例1設(shè)備更新問(wèn)題某工廠使用一臺(tái)設(shè)備,每年年初工廠要作出決定:繼續(xù)使用,購(gòu)買(mǎi)新的?如果繼續(xù)使用舊的,要負(fù)維修費(fèi);若要購(gòu)買(mǎi)一套新的,要負(fù)購(gòu)買(mǎi)費(fèi)。試確定一個(gè)5年計(jì)劃,使總支出最小若已知設(shè)備在各年的購(gòu)買(mǎi)費(fèi),及不同機(jī)器役齡時(shí)的殘值與維修費(fèi),如表2所示.項(xiàng)目第1年第2年第3年第4年第5年購(gòu)買(mǎi)費(fèi)1112131414機(jī)器役齡0-11-22-33-44-5維修費(fèi)5681118殘值43210表2解:把這個(gè)問(wèn)題化為最短路問(wèn)題。用點(diǎn)表示第i年初購(gòu)進(jìn)一臺(tái)新設(shè)備,虛設(shè)一個(gè)點(diǎn),表示第5年底。邊表示第i年購(gòu)進(jìn)的設(shè)備一直使用到第j年初(即第j-1年底)。邊上的數(shù)字表示第i年初購(gòu)進(jìn)設(shè)備,一直使用到第j年初所需支付的購(gòu)買(mǎi)費(fèi)、維修的全部費(fèi)用(可由表8-2計(jì)算得到)。這樣設(shè)備更新問(wèn)題就變?yōu)椋呵髲牡降淖疃搪穯?wèn)題.項(xiàng)目第1年第2年第3年第4年第5年購(gòu)買(mǎi)費(fèi)1112131414機(jī)器役齡0-11-22-33-44-5維修費(fèi)5681118殘值43210表2⑴①⑵
給劃成彩線。②⑶①②
給劃成彩線。⑷③
給劃成彩線。④⑸①②③④
給、劃成彩線。⑤①②③④⑤⑹
給劃成彩線。計(jì)算結(jié)果:最短路①②③④⑤最短路路長(zhǎng)為49。即:在第一年、第三年初各購(gòu)買(mǎi)一臺(tái)新設(shè)備為最優(yōu)決策。這時(shí)5年的總費(fèi)用為49。例3(選址問(wèn)題)已知某地區(qū)的交通網(wǎng)絡(luò)如圖所示,其中點(diǎn)代表居民小區(qū),邊代表公路,邊權(quán)為小區(qū)間公路距離,問(wèn)區(qū)中心醫(yī)院應(yīng)建在哪個(gè)小區(qū),可使離醫(yī)院最遠(yuǎn)的小區(qū)居民就診時(shí)所走的路程最近?解求中心的問(wèn)題。解決方法:先求出到其它各點(diǎn)的最短路長(zhǎng)如再求即為所求。比如求⑴⑵
給劃成彩線。⑶
給劃成彩線。給標(biāo)號(hào)20。⑷給劃成彩線。給標(biāo)號(hào)30。⑸分別給劃成彩線。分別給標(biāo)號(hào)33。⑹給劃成彩線。給標(biāo)號(hào)63。其它計(jì)算結(jié)果見(jiàn)下表:
小區(qū)號(hào)030506393456093300203363153063502002050254050633320030183363936350300486393451525184801548603040336315063表1由于最小,所以醫(yī)院應(yīng)建在,此時(shí)離醫(yī)院最遠(yuǎn)的小區(qū)距離為48。第四節(jié)最大流問(wèn)題最大流問(wèn)題是一類(lèi)應(yīng)用極為廣泛的問(wèn)題,例如在交通運(yùn)輸網(wǎng)絡(luò)中有人流、車(chē)流、貨物流、供水系統(tǒng)中有水流,金融系統(tǒng)中有現(xiàn)金流,通信系統(tǒng)中有信息流,等等。一.有關(guān)概念:例:下圖是輸油管道網(wǎng),為起點(diǎn),為終點(diǎn),,,,為中轉(zhuǎn)站,邊上的數(shù)字表示該管道的最大輸油能力(也稱(chēng)容量),記為,問(wèn)應(yīng)如何安排各管道輸油量,才能使從到的總輸油量最大?①分別稱(chēng)為發(fā)點(diǎn)、收點(diǎn)。其余的點(diǎn)稱(chēng)為中間點(diǎn)。②
每一個(gè)邊上都給定一個(gè)容量的網(wǎng)絡(luò)稱(chēng)為容量網(wǎng)絡(luò),記
的每一個(gè)邊上都給定一個(gè)實(shí)際流量的網(wǎng)絡(luò)稱(chēng)為給定了網(wǎng)絡(luò)一個(gè)流。④容量限制條件:對(duì)每一邊上都有⑤平衡條件:a)中間點(diǎn):流入量=流出量。
b)發(fā)收點(diǎn):發(fā)出流量=匯入流量。若,稱(chēng)邊是飽和邊。⑥
可增廣鏈:是指從到有一條鏈,此鏈上有≤的現(xiàn)象出現(xiàn)。(非飽和鏈)這種流稱(chēng)為可行流。上圖就是一個(gè)可行流。使流量達(dá)到最大的流稱(chēng)為最大流。二.求解最大流:先給標(biāo)號(hào)(?,+∞),其中?意思是流入的結(jié)點(diǎn),現(xiàn)沒(méi)有,純屬一個(gè)符號(hào)。+∞表示的流出量。因它上面沒(méi)有結(jié)點(diǎn)來(lái)控制它,故設(shè)為+∞.1)尋找可增廣鏈:b)接著檢查與相鄰接的點(diǎn),,。已飽和,流量不可再增。再檢查,可調(diào)整量為4-2=2,可提供量+∞,取調(diào)整量給標(biāo)號(hào),其中表示的所調(diào)整量2來(lái)自,且為正向流(向前流)。同理,給標(biāo)號(hào)下對(duì)已標(biāo)號(hào)點(diǎn)(可望調(diào)整點(diǎn))接著向下檢查。已飽和。再檢查與相鄰接且未標(biāo)號(hào)的點(diǎn)調(diào)整量為給標(biāo)號(hào)為d)檢查與相鄰接且未標(biāo)號(hào)的點(diǎn),。而對(duì)來(lái)講是流入,現(xiàn)欲增加流出量,應(yīng)壓縮的流入量,只要的流入
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶(hù)所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶(hù)上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶(hù)上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶(hù)因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 遼寧省丹東市(2024年-2025年小學(xué)四年級(jí)語(yǔ)文)人教版小升初真題(上學(xué)期)試卷及答案
- 遼寧省撫順市(2024年-2025年小學(xué)四年級(jí)語(yǔ)文)統(tǒng)編版能力評(píng)測(cè)(上學(xué)期)試卷及答案
- 江西省撫州市(2024年-2025年小學(xué)四年級(jí)語(yǔ)文)人教版能力評(píng)測(cè)(下學(xué)期)試卷及答案
- 高一上學(xué)期數(shù)學(xué)《集合與函數(shù)概念》單元檢測(cè)卷(B)含答案解析
- 河北省唐山市(2024年-2025年小學(xué)四年級(jí)語(yǔ)文)人教版小升初模擬((上下)學(xué)期)試卷及答案
- 小學(xué)六年級(jí)英語(yǔ)課課練單選題100道及答案解析
- 貴陽(yáng)市公安局招聘警務(wù)輔助人員考試試卷及答案
- 2023年廣安市廣安區(qū)北辰街道辦事處招聘片區(qū)紀(jì)檢監(jiān)督員考試真題
- 中班語(yǔ)言課件教學(xué)課件
- 2024年透紅外線玻璃項(xiàng)目合作計(jì)劃書(shū)
- 工程項(xiàng)目場(chǎng)容場(chǎng)貌管理制度
- 圓的一般方程公開(kāi)課一等獎(jiǎng)市優(yōu)質(zhì)課賽課獲獎(jiǎng)?wù)n件
- 家長(zhǎng)會(huì)青春期教育
- 高中數(shù)學(xué)-高三專(zhuān)題復(fù)習(xí)裂項(xiàng)求和教學(xué)設(shè)計(jì)學(xué)情分析教材分析課后反思
- 2023年高考英語(yǔ)考前必練-非謂語(yǔ)動(dòng)詞(含近三年真題及解析)
- 【淺談中外民航服務(wù)差異6500字(論文)】
- 大學(xué)生創(chuàng)業(yè)英語(yǔ)知到章節(jié)答案智慧樹(shù)2023年廣西師范大學(xué)
- 微量注射泵及輸液泵操作試題附答案
- 腹膜透析相關(guān)性腹膜炎的護(hù)理查房
- 什么是社會(huì)建設(shè)
- 國(guó)際投資學(xué)教程(第四版)綦建紅答案
評(píng)論
0/150
提交評(píng)論