第6章圖與網(wǎng)絡(luò)分析.ppt

1、第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)

2、目。問(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)

3、。 推論：把圖的所有點(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)度。現(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)度。現(xiàn)要求沿圖中道路架設(shè)電線，使上述村鎮(zhèn)全部同上電，應(yīng)如何架設(shè)使總的路線長(zhǎng)度為最短。,B,S,

4、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=0 L1p=minL11+d12, L11+d13=min0+5, 0+2=2=L13 L1p=minL11+d12, L13+d34, L13+d36=min0+

5、5, 2+7, 2+4=5=L12 L1p=minL12+d25, L12+d24, L13+d34, L13+d36= =min5+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=minL12+d25, L12+d24, L13+d34, L16+d64, L16+d65, L16+d67=min5+7, 5+2, 2+7, 6+2, 6+1, 6+6=7=L14=L15 L1p=minL15+d57, L16+d67=min7+3, 6+6=10 =L17,2,5,6,7,7,10,【練習(xí)】,4,6,5,7,

6、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)用

7、于購(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是歐

8、拉圖的充分必要條件是圖中的點(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ò)最大流,流與可行

9、流 所謂流是指加在網(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)，并使st的流中斷的一組弧的集合。 割的容量是組成它的集合中的各弧的容量之和。,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，這樣的鏈稱

10、為增廣鏈。,4. 網(wǎng)絡(luò)最大流,最大流最小割定理 當(dāng)增廣鏈存在時(shí)，找出 再令 定理：在網(wǎng)絡(luò)中st的最大流量等于它的最小割集的容量。,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ì)算出 的值，

11、并取其中最大的一個(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)

12、,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),

13、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)，試求圖中從st的最小費(fèi)用最大流。,從原容量網(wǎng)絡(luò)的零流f0開(kāi)始； 對(duì)原容量網(wǎng)絡(luò)的可行流fk構(gòu)造加權(quán)網(wǎng)絡(luò)W(fk): 對(duì)0fijcij的弧(i, j)，在加權(quán)網(wǎng)絡(luò)的i點(diǎn)和j點(diǎn)之間分別繪制弧(i, j)和(j, i)，其權(quán)數(shù)分別為bij和-bij； 對(duì)fij=cij的弧，在加權(quán)網(wǎng)絡(luò)的i點(diǎn)和j點(diǎn)之間繪制弧(j, i)，其權(quán)數(shù)為-bij； 對(duì)fij=0的弧，在加權(quán)網(wǎng)絡(luò)的i點(diǎn)和j點(diǎn)之間繪制弧(i, j)，其權(quán)數(shù)為bij。 確定最小