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

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

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

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

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

6、連通的圖都可以分為若干個連同子圖，每一個都稱為原圖的一個分圖,例如圖中，v1和v6之間沒有通路，因此它不是連通圖， 而如果去掉v6，則構(gòu)成一個連通圖。,連通是一個很重要的概念，如果一個問題所對應(yīng)的圖是一個不連通圖，則該問題一定可以分解成互不相關(guān)的子問題來加以研究，即可以把不連通圖分解成連通的子圖來研究。,子圖 設(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中任選一些頂點和邊在一起就組成G1的子圖G1，而只有在G1中的一條邊以及連接該邊的兩個端點均選入G2時，G2才是G1的子圖。,真子圖,v1,部分圖,若T是圖G(V，E)的部分圖，且T是樹，則稱T為G的部分樹。 若T是圖G的部分樹，則從G中去掉T中所有的邊，所得到的子圖稱為G中的T的余樹，也稱為G的一個余樹。 余樹不一定是樹！,一個沒有圈的圖稱為一個無圈圖或稱為林。 一個連通的無圈圖則稱為樹，一個林的每個連通子圖都是一個樹。,樹與部分樹,網(wǎng)絡(luò) 點和邊帶有某種數(shù)量指標的圖稱為網(wǎng)絡(luò)，或稱為賦權(quán)圖。,最小樹問題：選取網(wǎng)絡(luò)中的部分圖，使得網(wǎng)絡(luò)連通，且使總權(quán)數(shù)最小。 在

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

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

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

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

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

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

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

15、第二個標號值，計算公式如下：,3.如果對所有的點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),課堂練習: P225 7,無向圖,將算法稍作修改：在未標號點集中 找出與標號點vi有邊相連的點vj,網(wǎng)絡(luò)最大流問題,下圖表示從產(chǎn)地v1到銷地v6的交通網(wǎng)，弧旁邊的數(shù)字表示這條運輸線的最大通過能力，產(chǎn)品經(jīng)過這個交通網(wǎng)從v1運到v6，要求制定一個運輸方案使得從v1運到v6的產(chǎn)品數(shù)量最多。,基本概念,網(wǎng)絡(luò)

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

17、等于收點的凈輸入量。,最大流問題就是要找出一個可行流使得v(f)達到最大,飽和弧和非飽和弧 網(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中與給定的鏈 方向一致的弧 稱為前向弧，記作 ； 與給定的鏈方向相反的弧稱為后向弧，記作 ；,增廣鏈(可擴充鏈),4,0,0,2,1,大家想想：增廣鏈的意義在哪里？,根據(jù)定理，對于給定的可行流f，要判斷它是不是最大流只需要判斷D中有沒有關(guān)于f的增廣鏈。 如果有，則需要對f

18、進行改進；如果沒有增廣鏈，則已經(jīng)得到最大流。,定理：可行流f*是最大流，當且僅當不存在關(guān)于f*的增廣鏈,尋找最大流的標號法,網(wǎng)絡(luò)D中的點分為兩類，一類是標號點(屬于V1* )，一類是非標號點(不屬于V1* ) ； 標號點有兩類一類是已檢查的，一類是未檢查的。每個標號點有兩個標號：第一個標號表示這個點的標號是從哪一點得到的，以便進一步找出增廣鏈，第二個標號是用來表示方向,2.標號過程,從vi出發(fā)的弧,進入vi的弧,1.確定初始可行流,根據(jù)圖中弧的容量限制，確定一個初始的可行流，可以取零流。,vi變?yōu)闃颂柷乙褭z查的點，在vi旁加上*以示區(qū)別,3.調(dià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