《圖與網(wǎng)絡(luò)分析》PPT課件.ppt
《《圖與網(wǎng)絡(luò)分析》PPT課件.ppt》由會(huì)員分享,可在線閱讀,更多相關(guān)《《圖與網(wǎng)絡(luò)分析》PPT課件.ppt(45頁(yè)珍藏版)》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
第6章圖與網(wǎng)絡(luò)分析,圖的基本概念與模型樹(shù)圖和圖的最小部分樹(shù)最短路問(wèn)題網(wǎng)絡(luò)的最大流最小費(fèi)用流,,1.圖的基本概念與模型,運(yùn)籌學(xué)中研究的圖用來(lái)表明一些研究對(duì)象和這些對(duì)象之間的相互關(guān)系。用點(diǎn)表示研究對(duì)象,用邊表示這些對(duì)象之間的聯(lián)系,則圖G可以定義為點(diǎn)和邊的集合,記作G={V,E}如果給圖中的點(diǎn)和邊賦以具體的含義和權(quán)數(shù),如距離、費(fèi)用等,稱為網(wǎng)絡(luò)圖。,,端點(diǎn)、關(guān)聯(lián)邊、相鄰環(huán)、多重邊、簡(jiǎn)單圖次、奇點(diǎn)、偶點(diǎn)、孤立點(diǎn)鏈、圈、路、回路、連通圖完全圖、偶圖子圖、部分圖,【例】有甲、乙、丙、丁、戊、己六名運(yùn)動(dòng)員報(bào)名參加A、B、C、D、E、F六個(gè)項(xiàng)目的比賽。如下表所示,打√的是各運(yùn)動(dòng)員報(bào)名參加的比賽項(xiàng)目。問(wèn)六個(gè)項(xiàng)目的比賽順序應(yīng)如何安排,做到每名運(yùn)動(dòng)員都不連續(xù)地參加兩項(xiàng)比賽。,A,C,B,E,D,F,2.樹(shù)圖和圖的最小部分樹(shù),,樹(shù)圖是無(wú)圈的連通圖。性質(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.樹(shù)圖和圖的最小部分樹(shù),,圖的最小部分樹(shù)如果G1是G2的部分樹(shù),又是樹(shù)圖,則稱G1是G2的部分樹(shù)(或支撐樹(shù))。樹(shù)圖的各條邊稱為樹(shù)枝,一般圖含有多個(gè)部分樹(shù),其中樹(shù)枝總長(zhǎng)最小的部分樹(shù),稱為該圖的最小部分樹(shù)。定理1:圖中任一個(gè)點(diǎn)i,若j是與i相鄰點(diǎn)中距離最近的,則邊[i,j]一定必含在該圖的最小部分樹(shù)內(nèi)。推論:把圖的所有點(diǎn)分為V和V′兩個(gè)集合,則兩集合之間連線的最短邊一定包含在最小部分樹(shù)內(nèi)。,D,E,避圈法,【例】如下圖所示,S、A、B、C、D、E、T代表村鎮(zhèn),它們間連線表明村鎮(zhèn)間現(xiàn)有道路交通情況,連線旁數(shù)字代表道路的長(zhǎng)度?,F(xiàn)要求沿圖中道路架設(shè)電線,使上述村鎮(zhèn)全部同上電,應(yīng)如何架設(shè)使總的路線長(zhǎng)度為最短。,B,S,A,C,T,2,5,4,1,7,5,2,1,3,5,7,4,D,E,破圈法,【例】如下圖所示,S、A、B、C、D、E、T代表村鎮(zhèn),它們間連線表明村鎮(zhèn)間現(xiàn)有道路交通情況,連線旁數(shù)字代表道路的長(zhǎng)度?,F(xiàn)要求沿圖中道路架設(shè)電線,使上述村鎮(zhèn)全部同上電,應(yīng)如何架設(shè)使總的路線長(zhǎng)度為最短。,B,S,A,C,T,2,5,4,1,7,5,2,1,3,5,7,4,3.最短路問(wèn)題,,最短路問(wèn)題一般來(lái)說(shuō)就是從給定的網(wǎng)絡(luò)圖中找出任意兩點(diǎn)之間距離最短的一條路。這里的距離只是權(quán)數(shù)的代稱,在實(shí)際的網(wǎng)絡(luò)圖中,權(quán)數(shù)可以是時(shí)間、費(fèi)用等。,求解最短路問(wèn)題有兩種算法:求從某一點(diǎn)至其它各點(diǎn)之間最短距離的狄克斯屈拉(Dijkstra)算法;求網(wǎng)絡(luò)圖上任意兩點(diǎn)之間最短距離的矩陣算法;,狄克斯屈拉算法,,5,7,2,2,1,2,6,6,4,3,7,0,L11=0L1p=min{L11+d12,L11+d13}=min{0+5,0+2}=2=L13L1p=min{L11+d12,L13+d34,L13+d36}=min{0+5,2+7,2+4}=5=L12L1p=min{L12+d25,L12+d24,L13+d34,L13+d36}==min{5+7,5+2,2+7,2+4}=6=L16,2,5,6,狄克斯屈拉算法,,5,7,2,2,1,2,6,6,4,3,7,0,L1p=min{L12+d25,L12+d24,L13+d34,L16+d64,L16+d65,L16+d67}=min{5+7,5+2,2+7,6+2,6+1,6+6}=7=L14=L15L1p=min{L15+d57,L16+d67}=min{7+3,6+6}=10=L17,2,5,6,7,7,10,【練習(xí)】,4,6,5,7,1,5,5,2,4,1,6,8,0,4,5,5,9,10,16,矩陣算法,構(gòu)造一個(gè)新矩陣D(1),該矩陣給出了網(wǎng)絡(luò)中任意兩點(diǎn)之間直接到達(dá)和包括一個(gè)中間點(diǎn)時(shí)的最短距離。矩陣D(1)中每個(gè)元素的計(jì)算方式為:,一般有矩陣D(k)給出了網(wǎng)絡(luò)中任意兩點(diǎn)之間直接到達(dá),經(jīng)過(guò)一個(gè)、兩個(gè)、…、到(2k-1)個(gè)中間點(diǎn)時(shí)比較得到的最短距離。矩陣D(k)中每個(gè)元素的計(jì)算方式為:,【例】某人購(gòu)買一臺(tái)摩托車,準(zhǔn)備在今后4年內(nèi)使用。他可在第一年初購(gòu)買一臺(tái)新車,連續(xù)使用4年,也可于任何一年末換一臺(tái)新車。已知各年初的新車購(gòu)置價(jià)如下表1。不同役齡車的年使用維護(hù)費(fèi)及年末處理價(jià)如下表2。要求確定該人使用摩托車的最優(yōu)更新策略,使4年內(nèi)用于購(gòu)買、更新及使用維護(hù)的總費(fèi)用為最省。單位:萬(wàn)元。,,,,,,,,,,,0.8,0.9,1.1,1.4,1.7,1.8,2,2.8,2.9,4.2,0,0.8,1.7,2.6,3.7,一個(gè)郵遞員從郵局出發(fā),走遍他負(fù)責(zé)投遞的每一條街道,然后再返回郵局,問(wèn)應(yīng)選擇什么樣的路線,使走的路程為最短。因?yàn)檫@個(gè)問(wèn)題由中國(guó)數(shù)學(xué)工作者提出,故稱為中國(guó)郵路問(wèn)題。歐拉回路的定義是:連通圖G中,若存在一條回路,經(jīng)過(guò)每邊一次且僅一次,稱這條回路為歐拉回路。稱具有歐拉回路的圖為歐拉圖。,【例】設(shè)某郵遞員負(fù)責(zé)投遞的街道如圖所示,要求找出該郵遞員的最短投遞路線。,4,4,5,7,5,4,1,2,4,5,4,2,1,4,4,2,2,連通圖G是歐拉圖的充分必要條件是圖中的點(diǎn)全為偶點(diǎn)。(1)每條邊上最多重復(fù)一次;(2)在圖G的每個(gè)回路上,有重復(fù)邊的長(zhǎng)度不超過(guò)回路總長(zhǎng)的一半。,4,4,5,7,5,4,1,2,4,5,4,2,1,4,4,2,2,,,,,,4.網(wǎng)絡(luò)最大流,,網(wǎng)絡(luò)最大流的有關(guān)概念有向圖與容量網(wǎng)絡(luò)有向圖上的連線是有規(guī)定指向的,稱作??;所謂容量網(wǎng)絡(luò)是指對(duì)網(wǎng)絡(luò)上的每條弧都給出一個(gè)最大的通過(guò)能力,稱為該弧的容量,記為c(vi,vj)或簡(jiǎn)寫cij;在容量網(wǎng)絡(luò)中通常規(guī)定一個(gè)發(fā)點(diǎn)(記為s)和一個(gè)收點(diǎn)(記為t),網(wǎng)絡(luò)中既非發(fā)點(diǎn)又非收點(diǎn)的其它點(diǎn)稱為中間點(diǎn);網(wǎng)絡(luò)最大流是指網(wǎng)絡(luò)中從發(fā)點(diǎn)到收點(diǎn)之間允許通過(guò)的最大流量。,4.網(wǎng)絡(luò)最大流,,流與可行流所謂流是指加在網(wǎng)絡(luò)各條弧上的一組負(fù)載量,記作f(vi,vj)或簡(jiǎn)寫為fij;若網(wǎng)絡(luò)上所有的fij=0,這個(gè)流稱為零流;在容量網(wǎng)絡(luò)上滿足以下條件的一組流稱為可行流:容量限制條件,對(duì)所有弧有中間點(diǎn)平衡條件,4.網(wǎng)絡(luò)最大流,,割和流量割是指將容量網(wǎng)絡(luò)中的發(fā)點(diǎn)和收點(diǎn)分割開(kāi),并使s→t的流中斷的一組弧的集合。割的容量是組成它的集合中的各弧的容量之和。,,,,,,,,,,,,,,,,,,,9(4),9(9),8(8),7(5),5(4),2(0),6(1),5(5),10(8),,,,,,,,,,4.網(wǎng)絡(luò)最大流,,最大流最小割定理如果在網(wǎng)絡(luò)的發(fā)點(diǎn)和收點(diǎn)之間能找到一條鏈,在這條鏈上所有指向?yàn)閟→t的?。ǚQ為前向弧,記作+),存在f0,這樣的鏈稱為增廣鏈。,,,,,,4.網(wǎng)絡(luò)最大流,,最大流最小割定理當(dāng)增廣鏈存在時(shí),找出再令定理:在網(wǎng)絡(luò)中s→t的最大流量等于它的最小割集的容量。,,4.網(wǎng)絡(luò)最大流,,Ford-Fulkerson標(biāo)號(hào)算法首先給發(fā)點(diǎn)s標(biāo)號(hào)。括弧中的第一個(gè)數(shù)字是使這個(gè)點(diǎn)得到標(biāo)號(hào)的前一個(gè)點(diǎn)的代號(hào);括弧中的第二個(gè)數(shù)字表示從上一個(gè)標(biāo)號(hào)到這個(gè)標(biāo)號(hào)點(diǎn)的流量的最大允許調(diào)整值。列出與已標(biāo)號(hào)點(diǎn)相鄰的所有未標(biāo)號(hào)點(diǎn):考慮從已標(biāo)號(hào)點(diǎn)i出發(fā)的?。╥,j):,j點(diǎn)不標(biāo)號(hào),j點(diǎn)標(biāo)號(hào),,,列出與已標(biāo)號(hào)點(diǎn)相鄰的所有未標(biāo)號(hào)點(diǎn):考慮所有指向已標(biāo)號(hào)點(diǎn)i的?。╤,i):如果某未標(biāo)號(hào)點(diǎn)k有兩個(gè)以上相鄰的標(biāo)號(hào)點(diǎn),為減少迭代次數(shù),可按I、II中所述規(guī)則分別計(jì)算出的值,并取其中最大的一個(gè)標(biāo)記。重復(fù)第2步,可能出現(xiàn)兩種結(jié)局:標(biāo)號(hào)過(guò)程中斷,t得不到標(biāo)號(hào),說(shuō)明網(wǎng)絡(luò)中不存在增廣鏈,給定的流量即為最大流。記已標(biāo)號(hào)點(diǎn)的集合為V,未標(biāo)號(hào)點(diǎn)集合為V′,(V,V′)為網(wǎng)絡(luò)的最小割;t點(diǎn)得到標(biāo)號(hào),反向追蹤找出增廣鏈;,h點(diǎn)不標(biāo)號(hào),h點(diǎn)標(biāo)號(hào),,修改流量,設(shè)圖中原有可行流為f,按一下方式獲得新的可行流f′:抹掉圖中所有標(biāo)號(hào),重復(fù)第1到第4步,直至圖中找不到任何增廣鏈,即出現(xiàn)第3步的結(jié)局I為止,這時(shí)網(wǎng)絡(luò)圖中的流量即為最大流。,,,,,,,,,,,,,,,,,,,,9(4),9(9),8(8),7(5),5(4),2(0),6(1),5(5),10(8),,,,,,,,,,,,,,,,,,,,,,,,9(4),9(9),8(8),7(5),5(4),2(0),6(1),5(5),10(8),7(6),5(3),9(5),6(0),10(9),,最小割最大流:14,,,,,,,,,,,,,,,,,,,,,,,,,5(5),6(4),3(3),5(4),2(0),3(3),3(2),4(4),2(2),2(0),8(6),6(6),,,,,,,,,,,,,,,,,,,,,,,,,5(5),6(5),3(3),5(5),2(0),3(2),3(3),4(4),2(1),2(0),8(7),6(6),,,,,,,,最小割最大流:13,【例】某河流中有4個(gè)島嶼,從兩岸至各島嶼及各島嶼之間的橋梁編號(hào)如圖所示,在一次敵對(duì)的軍事行動(dòng)中,問(wèn)至少應(yīng)炸斷哪幾座橋梁,才能完全切斷兩岸的交通聯(lián)系?,,A,B,C,D,E,F,,,,,,,2(1),2,1(1),2(1),1,1,1,1(1),3(1),,A,B,C,D,E,F,,,,,,,2(1),2,1(1),2(1),1,1,1,1(1),3(1),,A,B,C,D,E,F,,,,,,,2(2),2,1(1),2(2),1,1,1(1),1(1),3(2),,最小割:{(D,F),(D,E),(A,E)},5.最小費(fèi)用流,,最小費(fèi)用流問(wèn)題對(duì)于容量網(wǎng)絡(luò),除考慮各條弧上的流量、容量外,還需考慮弧上通過(guò)單位流量時(shí)的費(fèi)用(bij),保證最終給出的流量或最大流也是費(fèi)用最少的。關(guān)鍵點(diǎn):確定“最小費(fèi)用增廣鏈”。,【例】各弧旁數(shù)字為(cij,bij),試求圖中從s→t的最小費(fèi)用最大流。,從原容量網(wǎng)絡(luò)的零流f0開(kāi)始;對(duì)原容量網(wǎng)絡(luò)的可行流fk構(gòu)造加權(quán)網(wǎng)絡(luò)W(fk):對(duì)0- 1.請(qǐng)仔細(xì)閱讀文檔,確保文檔完整性,對(duì)于不預(yù)覽、不比對(duì)內(nèi)容而直接下載帶來(lái)的問(wèn)題本站不予受理。
- 2.下載的文檔,不會(huì)出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入(下載+內(nèi)容+預(yù)覽)歸上傳者、原創(chuàng)作者;如果您是本文檔原作者,請(qǐng)點(diǎn)此認(rèn)領(lǐng)!既往收益都?xì)w您。
下載文檔到電腦,查找使用更方便
9.9 積分
下載 |
- 配套講稿:
如PPT文件的首頁(yè)顯示word圖標(biāo),表示該P(yáng)PT已包含配套word講稿。雙擊word圖標(biāo)可打開(kāi)word文檔。
- 特殊限制:
部分文檔作品中含有的國(guó)旗、國(guó)徽等圖片,僅作為作品整體效果示例展示,禁止商用。設(shè)計(jì)者僅對(duì)作品中獨(dú)創(chuàng)性部分享有著作權(quán)。
- 關(guān) 鍵 詞:
- 圖與網(wǎng)絡(luò)分析 網(wǎng)絡(luò)分析 PPT 課件
鏈接地址:http://m.italysoccerbets.com/p-12945823.html