運(yùn)籌學(xué)_圖與網(wǎng)絡(luò)分析.ppt

1、第 八 章圖 與 網(wǎng) 絡(luò) 分 析,圖的基本概念 最小樹(shù)問(wèn)題 中國(guó)郵路問(wèn)題 網(wǎng)絡(luò)最短路問(wèn)題 網(wǎng)絡(luò)最大流問(wèn)題,幾個(gè)圖論問(wèn)題,哥尼斯堡七空橋 中國(guó)郵路問(wèn)題 球隊(duì)間比賽問(wèn)題,哥尼斯堡七空橋,哥尼斯堡七座橋問(wèn)題是200年前數(shù)學(xué)家歐拉所研究的問(wèn)題之一。 哥尼斯堡現(xiàn)名加里寧格勒，城中有小島，周?chē)衅咦鶚蚣芰⒃诓懈駹柡由稀?歐拉想：在城中散步時(shí)，能否每座橋只走一次，走遍所有的七座橋。,一筆畫(huà)問(wèn)題,圖1,中國(guó)郵路問(wèn)題 我國(guó)數(shù)學(xué)家管梅谷教授1962年首次提出，并給出了它的解法(奇偶點(diǎn)圖上作業(yè)法)。 郵遞員在送報(bào)刊信件時(shí)，從郵局出發(fā)，一般地每次都要走遍所負(fù)責(zé)的全部街道，任務(wù)完成后返回郵局。那么郵遞員應(yīng)該選擇哪一條

2、路線才能以盡可能少的路程走完所有的街道呢？,有A、B、C、D、E五支球隊(duì)，他們之間的比賽情況可以用圖表示出來(lái)。已知A隊(duì)和其他各隊(duì)都比賽過(guò)一次，B隊(duì)和A、C隊(duì)比賽過(guò)，D隊(duì)和E、C隊(duì)比賽過(guò)，E隊(duì)和A、D隊(duì)比賽過(guò)。,圖2,圖3,如果在比賽中： A勝E， B勝C， A勝D， C勝A， E勝D， A勝B，,注：本章所研究的圖與平面幾何中的圖不 同，這里我們只關(guān)心圖有幾個(gè)點(diǎn)，點(diǎn)與點(diǎn) 之間有無(wú)連線，兩條線有無(wú)公共頂點(diǎn)，點(diǎn) 與線是否有關(guān)聯(lián)，至于連線的方式是直線 還是曲線，點(diǎn)與點(diǎn)的相對(duì)位置如何都是無(wú) 關(guān)緊要的。,圖4,圖的基本概念,若點(diǎn)與點(diǎn)之間的連線沒(méi)有方向，稱為邊，由此構(gòu)成的圖為無(wú)向圖。記為: G=（V，E）

3、其中V是G的點(diǎn)的集合，E為G的邊的集合，連接Vi，Vj的邊記為Vi，Vj或Vj，Vi,v1,v2,v3,v4,v5,v6,e2,e4,e5,e6,e7,e8,e1,e3,e9,e10,圖是由點(diǎn)和點(diǎn)與點(diǎn)之間的連線組成。,若點(diǎn)與點(diǎn)之間的連線有方向，稱為弧，由此構(gòu)成的圖為有向圖。記為: D=（V，A），其中V是G的點(diǎn)的集合，A為G的弧的集合，一條方向?yàn)閺腣i指向Vj的弧記為(Vi，Vj),v1,v3,v4,v5,v6,e2,e4,e5,e6,e7,e8,e1,e3,v2,相鄰點(diǎn)：兩點(diǎn)之間的邊屬于E 相鄰邊：如果兩條邊有一個(gè)公共端點(diǎn) 環(huán)：邊的兩個(gè)端點(diǎn)相同 多重邊(平行邊)：兩個(gè)點(diǎn)之間有多于一條邊(弧)

4、 多重圖: 無(wú)環(huán)但允許有多重邊的圖 簡(jiǎn)單圖：無(wú)環(huán)且無(wú)多重邊的圖 注:在有向圖中，如果兩點(diǎn)之間有不同方向的兩條弧，不是多重邊,端點(diǎn)的次d(v)：點(diǎn) v 作為端點(diǎn)的邊的個(gè)數(shù)； 奇點(diǎn)：d(v)=奇數(shù)； 偶點(diǎn)：d(v)=偶數(shù)； 懸掛點(diǎn)：d(v)=1；懸掛邊：與懸掛點(diǎn)連接的邊， 孤立點(diǎn)：d(v)=0；空?qǐng)D：E = ，無(wú)邊圖。,在有向圖中，以Vi為始點(diǎn)的邊數(shù)稱為Vi的出次，以Vi為終點(diǎn)的邊數(shù)稱為Vi的入次，入次和出次的和稱為該點(diǎn)的次。 有向圖中所有頂點(diǎn)的入次之和等于所有頂點(diǎn)的的出次之和。,圖的連通性： 鏈：由兩兩相鄰的點(diǎn)及其相關(guān)聯(lián)的邊構(gòu)成的點(diǎn)邊序列。如： v0 , e1 , v1 , e2 , v2 ,

5、e3 , v3 , , vn-1 , en , vn v0 , vn分別為鏈的起點(diǎn)和終點(diǎn) 簡(jiǎn)單鏈：鏈中所含的邊均不相同。 初等鏈：鏈中所含的點(diǎn)均不相同，也稱通路。 圈：起點(diǎn)和終點(diǎn)相同的鏈。,e8,是一條鏈，且是開(kāi)鏈，也是簡(jiǎn)單鏈，但不是初等鏈，因?yàn)関1出現(xiàn)兩次。,是一個(gè)圈。,v3,e1,e2,e3,通路：由兩兩相鄰的點(diǎn)及其相關(guān)聯(lián)的弧構(gòu)成的點(diǎn)弧交錯(cuò)序列；如： v0 , e1 , v1 , e2 , v2 , e3 , v3 , , vn-1 , en , vn v0 , vn分別為鏈的起點(diǎn)和終點(diǎn) 回路：通路的起點(diǎn)和終點(diǎn)相同 連通圖：圖中任意兩點(diǎn)之間均至少有一條鏈相連，否則稱作不連通圖。 任何一個(gè)不

6、連通的圖都可以分為若干個(gè)連同子圖，每一個(gè)都稱為原圖的一個(gè)分圖,例如圖中，v1和v6之間沒(méi)有通路，因此它不是連通圖， 而如果去掉v6，則構(gòu)成一個(gè)連通圖。,連通是一個(gè)很重要的概念，如果一個(gè)問(wèn)題所對(duì)應(yīng)的圖是一個(gè)不連通圖，則該問(wèn)題一定可以分解成互不相關(guān)的子問(wèn)題來(lái)加以研究，即可以把不連通圖分解成連通的子圖來(lái)研究。,子圖 設(shè) G1 = V1 , E1 , G2 = V2 , E2 子圖定義：如果 V2 V1 , E2 E1 稱 G2 是 G1 的子圖； 真子圖：如果 V2 V1 , E2 E1 稱 G2 是 G1 的真子圖； 部分圖：如果 V2 = V1 , E2 E1 稱 G2 是 G1 的部分圖；,部

7、分圖,子圖,必須指出，并不是從圖G1中任選一些頂點(diǎn)和邊在一起就組成G1的子圖G1，而只有在G1中的一條邊以及連接該邊的兩個(gè)端點(diǎn)均選入G2時(shí)，G2才是G1的子圖。,真子圖,v1,部分圖,若T是圖G(V，E)的部分圖，且T是樹(shù)，則稱T為G的部分樹(shù)。 若T是圖G的部分樹(shù)，則從G中去掉T中所有的邊，所得到的子圖稱為G中的T的余樹(shù)，也稱為G的一個(gè)余樹(shù)。 余樹(shù)不一定是樹(shù)！,一個(gè)沒(méi)有圈的圖稱為一個(gè)無(wú)圈圖或稱為林。 一個(gè)連通的無(wú)圈圖則稱為樹(shù)，一個(gè)林的每個(gè)連通子圖都是一個(gè)樹(shù)。,樹(shù)與部分樹(shù),網(wǎng)絡(luò) 點(diǎn)和邊帶有某種數(shù)量指標(biāo)的圖稱為網(wǎng)絡(luò)，或稱為賦權(quán)圖。,最小樹(shù)問(wèn)題：選取網(wǎng)絡(luò)中的部分圖，使得網(wǎng)絡(luò)連通，且使總權(quán)數(shù)最小。 在

8、實(shí)際應(yīng)用中，經(jīng)常碰到需要求一個(gè)賦權(quán)連通圖的最小樹(shù)的問(wèn)題。例如，用節(jié)點(diǎn)表示城市，用邊表示可以在兩個(gè)城市之間架設(shè)光纜，邊上的權(quán)表示光纜的長(zhǎng)度，試求應(yīng)如何架設(shè)光纜，才能使任意兩城市之間均由光纜相通，且使光纜的總長(zhǎng)度最短。 求最小樹(shù)的方法，依據(jù)的是樹(shù)的特點(diǎn)，即無(wú)圈和連通，加上最短的要求，方法主要有兩種：一種稱為破圈法，一種稱為取邊避圈法。,網(wǎng)絡(luò)最小樹(shù)問(wèn)題,取邊避圈法 方法步驟：依次在圖中取一個(gè)權(quán)值最小的邊，或者是相對(duì)最短的邊，并且在每次取邊時(shí)都不能與已取的邊構(gòu)成圈。 首先在圖中選最短的邊，并且將與之關(guān)聯(lián)的兩個(gè)點(diǎn)標(biāo)記， 然后每次都在標(biāo)記點(diǎn)和未標(biāo)記點(diǎn)間可能的邊中取一個(gè)最短的邊，并將新選的邊標(biāo)記， 重復(fù)上述

9、過(guò)程，直到所有的點(diǎn)均被標(biāo)記了。,1,4,3,2,1,6,7,2,2,5,3,破圈法,方法步驟： 在網(wǎng)絡(luò)圖中尋找一個(gè)圈，若已經(jīng)無(wú)圈則轉(zhuǎn)步驟3。 在圈中選取權(quán)數(shù)最大的邊，從網(wǎng)絡(luò)圖中截去該邊，對(duì)新的網(wǎng)絡(luò)，轉(zhuǎn)步驟1。 若q=p-1(邊數(shù)=定點(diǎn)數(shù)-1)，則已找到最小樹(shù)，否則網(wǎng)絡(luò)圖不連通，無(wú)最小樹(shù)。,課堂練習(xí)： P224 2.a）,問(wèn)題定義：在一個(gè)賦權(quán)圖上求一個(gè)圈，經(jīng)過(guò)圖中每一條邊至少一次，使圈中各邊權(quán)值的總和為最小。,中國(guó)郵路問(wèn)題,比如圈：v5，v2，v1，v3，v2，v4，v3，v5，v4，v6，v5,歐拉鏈與歐拉圈 經(jīng)過(guò)且僅經(jīng)過(guò)圖中每一條邊一次的鏈稱為歐拉鏈，經(jīng)過(guò)且僅經(jīng)過(guò)圖中每一條邊一次的圈稱為歐拉

10、圈,定理 連通多重圖中含有歐拉鏈的充分必要條件是圖中奇點(diǎn)的個(gè)數(shù)為0或2。且當(dāng)且僅當(dāng)沒(méi)有奇點(diǎn)時(shí)圖中含有歐拉圈，即沒(méi)有奇點(diǎn)的連通圖必含有歐拉圈。,E=v5，v2，v1，v3，v2，v4，v3，v5，v4，v6，v5,對(duì)于不含奇點(diǎn)的連通圖，中國(guó)郵路問(wèn)題就是要找圖中的歐拉圈。,v1,v2,v3,v4,v5,v6,含有奇點(diǎn)的連通圖中不含歐拉圈，此時(shí)，最優(yōu)的郵遞路線是什么呢？,求解中國(guó)郵路問(wèn)題的奇偶點(diǎn)圖上作業(yè)法,奇偶點(diǎn)表上作業(yè)法 (1)找出奇點(diǎn)(一定為偶數(shù)個(gè))，在每?jī)蓚€(gè)奇點(diǎn)之間找一條鏈，在這些鏈經(jīng)過(guò)的所有邊上增加一條邊，這樣所有的奇點(diǎn)變?yōu)榕键c(diǎn)，一定存在歐拉圈，但是不一定是路線最短的，所以需要檢驗(yàn)和調(diào)整。

11、(2)檢驗(yàn)增加的邊的權(quán)值是否是最小的。 定理3 假設(shè)M是使得圖G中不含奇點(diǎn)的所有增加邊，則M是權(quán)值總和為最小的增加邊的充分必要條件是： 1)圖G中每條邊上最多增加一條邊； 2)在圖G的每個(gè)圈上，增加的邊的總權(quán)值不超過(guò)該圈總權(quán)值的一半。 如果上述兩個(gè)條件都滿足則已經(jīng)找到權(quán)值最小的歐拉圈 否則轉(zhuǎn)入3) 3)調(diào)整增加邊。如果1)不滿足，則從該條邊的增加邊中去掉偶數(shù)條； 如果2)不滿足，則將這個(gè)圈上的增加邊去掉，將該圈的其余邊上添加增 加邊，轉(zhuǎn)入(2),v1，v6，v5，v4，v6，v2，v6，v3，v4，v3，v2，v1,不滿足定理3條件,網(wǎng)絡(luò) 對(duì)有向圖D=(V,A)，如果對(duì)于有向圖D中的每一條弧(

12、vi,vj) A，都有一個(gè)數(shù)w(vi,vj) 與它對(duì)應(yīng)，此時(shí)稱D為一個(gè)網(wǎng)絡(luò)，或稱賦權(quán)有向圖。 有向網(wǎng)絡(luò)：網(wǎng)絡(luò)中每個(gè)邊都是有向邊； 無(wú)向網(wǎng)絡(luò)：網(wǎng)絡(luò)中每個(gè)邊都是無(wú)向邊； 混合網(wǎng)絡(luò)：網(wǎng)絡(luò)中既有有向邊，又有無(wú)向邊； 網(wǎng)絡(luò)最短路線問(wèn)題：尋找網(wǎng)絡(luò)中從起點(diǎn) v1 到終點(diǎn) vn 的最短路線。,網(wǎng) 絡(luò) 最 短 路 問(wèn) 題,一般的最短路問(wèn)題描述： 給定一個(gè)賦權(quán)有向圖D=(V,A)，對(duì)每一個(gè)弧a=(vi,vj)，相應(yīng)地有權(quán)w(a)=wij，又給定D中的任何兩個(gè)頂點(diǎn)vs和vt ，設(shè)P是從vs到vt的路，定義路P的權(quán)是P中所有弧之和，記為w(P)，最短路問(wèn)題就是要在所有從vs到vt的路中，求一條權(quán)最小的路，即一條從vs

13、到vt的路P0使得：,路P0的權(quán)稱為從vs到vt的距離，記為d(vs,vt)。,有向圖權(quán)值非負(fù)- Dijkstra算法,Dijkstra算法的基本步驟(權(quán)值非負(fù)) 1.給頂點(diǎn)v1標(biāo)號(hào)(0)，v1稱為已標(biāo)號(hào)點(diǎn)，記標(biāo)號(hào)點(diǎn)集為V1=v1 2.在未標(biāo)號(hào)點(diǎn)集V2中找出與標(biāo)號(hào)點(diǎn)集V1中的頂點(diǎn)vi有弧相連(并且以vi為起點(diǎn))的點(diǎn)vj， 3.在第2步選出的點(diǎn)中，選出滿足下面條件的點(diǎn)vk，并給vk標(biāo)號(hào)(l,L1k)，其中l(wèi)為第一標(biāo)號(hào)， L1k為第二標(biāo)號(hào),為從v1到vk的最短路的長(zhǎng)度，l表示在從v1到vk的最短路上，與vk相鄰的點(diǎn)是vl,4. 若最后一個(gè)頂點(diǎn)vn未標(biāo)號(hào)，則轉(zhuǎn)回第2步；若vn已標(biāo)號(hào)，則從vn開(kāi)始，按

14、照第一個(gè)標(biāo)號(hào)逆向追蹤，直到v1，就得到從v1到vn的最短路，vn的第二個(gè)標(biāo)號(hào)表示最短路的長(zhǎng)度。,求從v1到v8的最短路,(0),(1,1),(1,3),(3,5),(2,6),(5,10),(5,9),(5,12),注：在給頂點(diǎn)編號(hào)時(shí)，如果在多個(gè)為標(biāo)號(hào)點(diǎn)均取得最小值Llk則對(duì)這多個(gè)點(diǎn)同時(shí)標(biāo)號(hào)，這些點(diǎn)的第二個(gè)標(biāo)號(hào)相同，但是第一個(gè)標(biāo)號(hào)不一定相同。,課堂練習(xí)： P225 6. a) 和 b),有向圖某些權(quán)值為負(fù) 1. 先對(duì)圖中各個(gè)點(diǎn)按照Dijkstra算法標(biāo)號(hào)，稱之為第一次標(biāo)號(hào)，令m=1，轉(zhuǎn)入第二步； 2. 對(duì)圖中除了v1以外的所有點(diǎn)進(jìn)行m+1次標(biāo)號(hào)，記L1k(m+1)為對(duì)頂點(diǎn)vk的第m+1次標(biāo)號(hào)的

15、第二個(gè)標(biāo)號(hào)值，計(jì)算公式如下：,3.如果對(duì)所有的點(diǎn)L1k(m)= L1k(m+1)都成立則逆向追蹤，找出最短路，算法終止；若存在L1k(m) L1k(m+1), 則令m=m+1，返回第2步,求從v1到v4的最短路,(0),(1,2),(1,3),(2,1),(0),(3,1),(1,3),(2,0),課堂練習(xí): P225 7,無(wú)向圖,將算法稍作修改：在未標(biāo)號(hào)點(diǎn)集中 找出與標(biāo)號(hào)點(diǎn)vi有邊相連的點(diǎn)vj,網(wǎng)絡(luò)最大流問(wèn)題,下圖表示從產(chǎn)地v1到銷(xiāo)地v6的交通網(wǎng)，弧旁邊的數(shù)字表示這條運(yùn)輸線的最大通過(guò)能力，產(chǎn)品經(jīng)過(guò)這個(gè)交通網(wǎng)從v1運(yùn)到v6，要求制定一個(gè)運(yùn)輸方案使得從v1運(yùn)到v6的產(chǎn)品數(shù)量最多。,基本概念,網(wǎng)絡(luò)

16、與流 對(duì)有向圖D=(V,A)，如果其中指定某一點(diǎn)vs為發(fā)點(diǎn)，另一點(diǎn)vt為收點(diǎn)，其他點(diǎn)則稱為中間點(diǎn)。若對(duì)于有向圖D中的每一條弧(vi,vj) A，都有一個(gè)數(shù)c(vi,vj) 0與它對(duì)應(yīng)，稱c為弧的容量，記為D=(V,A ,C) 定義在弧集合A上的一個(gè)函數(shù)f=f(vi,vj)稱為網(wǎng)絡(luò)D上的流，并稱f(vi,vj)為弧(vi,vj)上的流量，簡(jiǎn)記為fij,可行流： 滿足下述條件的流稱為可行流： (1)容量限制：對(duì)于每一個(gè)弧(vi,vj) A， 0fij cij (2)平衡條件： 對(duì)于中間點(diǎn)：流出量等于流入量，即對(duì)于每個(gè)i(is,t)有,對(duì)于發(fā)點(diǎn)：,對(duì)于收點(diǎn)：,稱v(f)為可行流的流量，發(fā)點(diǎn)的凈輸出量

17、等于收點(diǎn)的凈輸入量。,最大流問(wèn)題就是要找出一個(gè)可行流使得v(f)達(dá)到最大,飽和弧和非飽和弧 網(wǎng)絡(luò)D=(V,A ,C)，f=f(vi,vj)是D的可行流，則如果某一條弧(vi,vj) A滿足 (1) fij = cij ，則稱(vi,vj)為飽和??； (2) fij 0 ， 則稱(vi,vj)為非零流??； 前向弧和后向弧 網(wǎng)絡(luò)D中與給定的鏈 方向一致的弧 稱為前向弧，記作 ； 與給定的鏈方向相反的弧稱為后向弧，記作 ；,增廣鏈(可擴(kuò)充鏈),4,0,0,2,1,大家想想：增廣鏈的意義在哪里？,根據(jù)定理，對(duì)于給定的可行流f，要判斷它是不是最大流只需要判斷D中有沒(méi)有關(guān)于f的增廣鏈。 如果有，則需要對(duì)f

18、進(jìn)行改進(jìn)；如果沒(méi)有增廣鏈，則已經(jīng)得到最大流。,定理：可行流f*是最大流，當(dāng)且僅當(dāng)不存在關(guān)于f*的增廣鏈,尋找最大流的標(biāo)號(hào)法,網(wǎng)絡(luò)D中的點(diǎn)分為兩類(lèi)，一類(lèi)是標(biāo)號(hào)點(diǎn)(屬于V1* )，一類(lèi)是非標(biāo)號(hào)點(diǎn)(不屬于V1* ) ； 標(biāo)號(hào)點(diǎn)有兩類(lèi)一類(lèi)是已檢查的，一類(lèi)是未檢查的。每個(gè)標(biāo)號(hào)點(diǎn)有兩個(gè)標(biāo)號(hào)：第一個(gè)標(biāo)號(hào)表示這個(gè)點(diǎn)的標(biāo)號(hào)是從哪一點(diǎn)得到的，以便進(jìn)一步找出增廣鏈，第二個(gè)標(biāo)號(hào)是用來(lái)表示方向,2.標(biāo)號(hào)過(guò)程,從vi出發(fā)的弧,進(jìn)入vi的弧,1.確定初始可行流,根據(jù)圖中弧的容量限制，確定一個(gè)初始的可行流，可以取零流。,vi變?yōu)闃?biāo)號(hào)且已檢查的點(diǎn)，在vi旁加上*以示區(qū)別,3.調(diào)整過(guò)程,前向弧,后向弧,用標(biāo)號(hào)法求如下圖所示的網(wǎng)絡(luò)最大流 圖中已經(jīng)給出初始流。,(8,5),vs,v2,v1,v4,v3,vt,(2,2),(6,5),(10,4),(7,2),(9,5),(6,0),(3,2),(5,2),(5,3),(8，5),vs,v2,v1,v4,v3,vt,(2,2),(6,5),(1