第8章圖與網(wǎng)絡分析1ppt課件

1、第八章 圖與網(wǎng)絡分析第一節(jié) 圖與網(wǎng)絡的基本知識第二節(jié) 樹第三節(jié) 最短路問題第四節(jié) 最大流問題第五節(jié) 最小費用流問題（一哥尼斯堡七橋難題 1736年瑞士數(shù)學家歐拉E.Euler在求解七橋一筆畫難題時，就用了點線圖來分析論證：每個點均有奇數(shù)條邊時，一筆畫問題無解。（要求不重邊）CDAB(前蘇)哥尼斯堡城中的普雷格爾河ACBD（二）“環(huán)球旅行問題1857年，英國數(shù)學家哈密爾頓(Hamilton)發(fā)明了一種游戲，他用一個實心正12面體象征地球，正12面體的20個頂點分別表示世界上20座名城，要求游戲者從任一城市出發(fā)，尋找一條可經(jīng)由每個城市一次且僅一次再回到原出發(fā)點的路，這就是“環(huán)球旅行問題。（要求不重

2、點）（三）“中國郵路問題”一個郵遞員從郵局出發(fā)要走遍他所負責的每條街道去送信，問應如何選擇適當?shù)穆肪€可使所走的總路程最短。這個問題就與歐拉回路有密切的關系。第一節(jié) 圖與網(wǎng)絡的基本知識一、圖與網(wǎng)絡的基本概念（一圖及其分類5家企業(yè)業(yè)務往來關系甲乙戊丙丁由上面的例子可以看出，這里所研究的圖與平面幾何中的圖不同，這里只關心圖中有多少個點，點與點之間有無連線，至于連線的方式是直線還是曲線，點與點的相對位置如何，都是無關緊要的。工人與需要完成的工作電路網(wǎng)絡城市規(guī)劃交通運輸、信息傳遞、物資調(diào)配甲乙丙丁戊ABCD定義1 一個圖是由點集V=vi和V中元素的無序?qū)Φ囊粋€集合Eek所構(gòu)成的二元組，記為G(V,E)，

3、V中的元素vi叫做頂點，E中的元素ek叫做邊。 當V,E為有限集合時，G稱為有限圖，否則，稱為無限圖。 兩個點u,v屬于V，如果邊(u,v)屬于E，則稱u,v兩點相鄰。u,v稱為邊(u,v)的端點。12345e1e2e3e4e5e6 兩條邊ei,ej屬于E，如果它們有一個公共端點u，則稱ei,ej相鄰。邊ei,ej稱為點u的關聯(lián)邊。 用m(G)|E|表示圖G中的邊數(shù)，用n(G)|V|表示圖G的頂點個數(shù)。在不引起混淆情況下簡記為m,n。 對于任一條邊(vi,vj)屬于E，如果邊(vi,vj)端點無序，則它是無向邊，此時圖G稱為無向圖。如果邊(vi,vj)的端點有序，即它表示以vi為始點，vj為終

4、點的有向邊(或稱弧)，這時圖G稱為有向圖 一條邊的兩個端點如果相同稱此邊為環(huán)(自回路)。 兩個點之間多于一條邊的，稱為多重邊。定義2 不含環(huán)和多重邊的圖稱為簡單圖，含有多重邊的圖稱為多重圖。（a）（b）（c）（d）定義3 每一對頂點間都有邊相連的無向簡單圖稱為完全圖。有n個頂點的無向完全圖記作Kn。 有向完全圖則是指每一對頂點間有且僅有一條有向邊的簡單圖。定義4 圖G(V,E)的點集V可以分為兩個非空子集X,Y，即XUYV，XY，使得E中每條邊的兩個端點必有一個端點屬于X，另一個端點屬于Y則稱G為二部圖(偶圖、二分圖)，有時記作G(X,Y,E)。（二頂點的次度）定義5 以點v為端點的邊數(shù)叫做點

5、v的次。記作deg(v)，簡記為d(v).次為1的點稱為懸掛點。連結(jié)懸掛點的邊稱為懸掛邊。次為零的點稱為孤立點。次為奇數(shù)的點稱為奇點。次為偶數(shù)的點稱為偶點。123456（a）1234（b）123（c）4定理1 任何圖中，頂點次數(shù)的總和等于邊數(shù)的2倍。證明：由于每條邊必與兩個頂點關聯(lián)，在計算點的次時，每條邊均被計算了兩次，所頂點次數(shù)的總和等于邊數(shù)的2倍。定理2 任何圖中，次為奇數(shù)的頂點必為偶數(shù)個。證明：設V1和V2分別為圖G中奇點與偶點的集合(V1V2=V)。由定理1知：mvdvdVvVv2)()(21偶數(shù)偶數(shù)偶數(shù) 定義6 有向圖中，以vi為始點的邊數(shù)稱為點vi的出次，用d+(vi)表示，以vi

6、為終點的邊數(shù)稱為點vi的入次，用d-(vi)表示。vi點的出次與入次之和就是該點的次。容易證明有向圖中，所有頂點的入次之和等于所有頂點的出次之和。（三子圖 定義7 圖G(V,E)，若E是E的子集，V是V的子集，且E中的邊僅與V中的頂點相關聯(lián)，則稱G(V,E)是G的一個子圖。特別地，若VV,則G稱為G的生成子圖(支撐子圖)。（四網(wǎng)絡 在實際問題中，往往只用圖來描述所研究對象之間的關系還是不夠的，與圖聯(lián)系在一起的，通常還有與點或邊有關的某些數(shù)量指標，我們常稱之為“權(quán)”，權(quán)可以代表如距離、費用、通過能力(容量)等等。這種點或邊帶有某種數(shù)量指標的圖你為網(wǎng)絡(賦權(quán)間)。二、連通圖定義8 無向圖G=(V,

7、E),若圖G中某些點與邊的交替序列可以排成的形式,且 ,則稱這個點邊序列連接 與 的一條鏈,鏈長為k。),.,(11102kkkiiiiiiivevevev),.,1)(,(1ktvvetttiii0ivkivp點邊列中沒有重復的點和重復的邊者為初等鏈。p定義9 無向圖G中,連結(jié) 與 的一條鏈,當與 是同一個點時,稱此鏈為圈。圈中既無重復點也無重復邊者為初等圈。p（1對于有向圖可以類似于無向圖定義鏈和圈、初等鏈，此時不考慮邊的方向。而當鏈(圈)上的邊方向相同時,稱為道路(回路)。p（2對于無向圖來說，道路與鏈、回路與圈意義相同。0ivkivkiv0iv定義10 一個圖中任意兩點間至少有一條鏈相

8、連，則稱此圖為連通圖。任何一個不連通圖都可以分為若干個連通子圖，每一個稱為一個分圖。三、圖的矩陣表示圖的矩陣表示方法有權(quán)矩陣、鄰接矩陣、關聯(lián)矩陣、回路矩陣、割集矩陣等。定義11 網(wǎng)絡賦權(quán)圖G=（V，E），其中邊(vi,vj)有權(quán)wij,構(gòu)造矩陣A=(aij)nn,其中其它0),(Evvwajiijij則稱A為網(wǎng)絡G的權(quán)矩陣例：寫出上圖的權(quán)矩陣。定義12 對于圖G=（V，E），|V|=n，構(gòu)造一個矩陣A =(aij)nn ，其中：其它0),(1Evvajiij則稱A為圖G的鄰接矩陣v1v2v3v4v5742943856例：鄰接矩陣表示上圖。v5v1v2v3v4四、歐拉回路與中國郵路問題 （一歐拉

9、回路與道路 定義13 連通圖G中，若存在一條道路，經(jīng)過每邊一次且僅一次，則稱這條路為歐拉道路。若存在一條回路，經(jīng)過每邊一次且僅一次則稱這條回路為歐拉回路。歐拉圖含有歐拉回路。定理3 無向連通圖G是歐拉圖，當且僅當G中無奇點。推論1 無向連通圖G為歐拉圖，當且僅當G的邊集可劃分為若干個初等回路。推論2 無向連通圖G有歐拉道路，當且僅當G中恰有兩個奇點。定理4 連通有向圖G是歐拉圖，當且僅當它每個頂點的出次等于入次。 （二中國郵路問題 一個郵遞員，負責某一地區(qū)的信件投遞。他每天要從郵局出發(fā)，走遍該地區(qū)所有街道再返回郵局，問應如何安排送信的路線可以使所走的總路程最短？這個問題是我國管梅谷教授在196

10、2年首先提出的。因此國際上通稱為中國郵路問題。用圖論的語言描述：給定一個連通圖G，每邊有非負權(quán)l(xiāng)(e)，要求一條回路過每邊至少一次，且滿足總權(quán)最小。第二節(jié) 樹一、樹的概念和性質(zhì) （一幾個樹的例子（1乒乓球單打比賽抽簽后，可用圖來表示。ABCDEFGIJKLMNH運動員（2某企業(yè)的組織結(jié)構(gòu)。廠長人事科財務科總工程師新產(chǎn)品開發(fā)科技術科生產(chǎn)副廠長生產(chǎn)科設備科供應科動力科銷售科檢驗科經(jīng)營副廠長（二定義14：連通且不含圈的圖稱為樹。樹中次為1的點稱為樹葉，次大于1的點稱為分枝點。 （三樹的性質(zhì)定理6 圖T=（V，E），|V|=n，|E|=m，則下列關于樹的說法是等價的。（1T是一個樹。（2T無圈，且m=

11、n-1。（3T連通，且m=n-1。（4T無圈，但每加一新邊即得惟一一個圈。（5T連通，但任舍去一個邊就不連通。（6T中任意兩點，有惟一鏈相連。樹的性質(zhì)任何樹必有樹葉(即次數(shù)為1的節(jié)點)。樹中任意兩點之間有且僅有一條鏈連接相通。任意去掉一條樹枝，該樹就被分割成兩互不連通的子圖。樹的任意兩個頂點間添加一條邊稱為連枝），就構(gòu)成一個回路。僅用一條連枝構(gòu)成的回路稱為單連枝回路，也稱為基本回路 一連通圖可能具有很多樹，這些樹都是原連通圖的部分圖，即包括了原連通圖的所有頂點。連枝的集合是原連通圖相應的余樹，或稱補樹。余樹可能是樹，也可能不是樹，甚至是非連通圖。二、圖的生成樹 定義15 若圖G的生成子圖是一棵

12、樹，則稱該樹為G的生成樹(支撐樹)。或簡稱為圖G的樹。圖G中屬于生成樹的邊稱為樹枝，不在生成樹中的邊際為弦。e1e2e3e4e5e6e7e8e9（a）e1e2e3e7e8e9（b）定理7 圖G(V，E)有生成樹的充分必要條件為G是連通圖。尋找生成樹的方法（1深探法步驟如下用標號法）在點集V中任取點v。給v以標號0。若某u點已得標號i，檢查一端點為u的各邊，另一端點是否均已標號。 若有(u，w)邊之w未標號，則結(jié)w以標號i十1，記下邊(u，w)。今w代u，反復 。 若這樣的邊的另一端點均已有標號，就退到標號為i-1的r點，以r代u，反復。直到全部點得到標號為止。例：試用深探法求下圖中的一棵生成樹

13、012345678910111213（2廣探法 步驟如下： 在點集V中任取一點v，給v以標號0。 令所有標號為i的點集為Vi，檢測查Vi，VVi中的邊端點是否均已標號。對所有未標號之點均標以i+1，記下這些邊。對標號i+1的點重復步驟，直到全部點得到標號為止。例：用廣探法求上圖中的一棵生成樹。三、最小生成樹問題 定義16 連通圖G(V，E)、每條邊上有非負權(quán)L(e)。一棵生成樹所有樹枝上權(quán)的總和，稱為這個生成樹的權(quán)。具有最小權(quán)的生成樹稱為最小生成樹(最小支撐樹)簡稱最小樹。算法1 (Kruskal算法)（1將所有的邊按從小到大的順序排列（2將每條邊加入到生成子圖中，如構(gòu)成圈則舍去。（3反復2過

14、程，直到所有的邊試驗完畢。v1v2v3v4v5v6v7871452635432將邊按權(quán)從小到大排序( v2,v3),( v4,v5),(v6,v7),(v4,v6),(v5,v7),(v2,v5),(v5,v6),(v2,v4),(v3,v6),(v3,v4),(v1,v3),(v1,v2)將邊加入到新圖中,如不構(gòu)成回路則保留;否則,去掉.例：求下圖的一棵最小支撐樹( v2,v3),( v4,v5),(v6,v7),(v4,v6),(v5,v7),(v2,v5),(v5,v6),(v2,v4),(v3,v6),(v3,v4),(v1,v3),(v1,v2)v1v2v3v4v5v6v787145

15、6543223其權(quán)為：19定理8 用Kruskal算法得到的子圖T*(e1,e2,en-1)是一棵最小樹。算法2破圈法）（1從圖G中任選一棵樹T1。（2加上一條弦e1，T1+e1中立即生成一個圈。去掉此圈中最大權(quán)邊，得到新樹T2。以T2代T1，反復2再檢查剩余的弦，直到全部弦檢查完畢為止。例：用破圈法求上圖中的一棵最小生成樹。定理9 圖G的生成樹T為最小樹，當且僅當對任一e來說，e是T+e中與之對應的圈e中的最大權(quán)邊。四、根樹及其應用定義17 若一個有向圖在不考慮邊的方向時是一棵樹，則稱這個有向圖為有向樹。定義18 有向樹T，恰有一個結(jié)點入次為0，其余各點入次均為1，則稱T為根樹又稱外向樹）。根樹中入次為0的點稱為根。根樹中出次為0的點稱為葉，其他頂點稱為分枝點。由根到某一頂點vi的道路長度設每邊長度為1），稱為點vi的層次。定義 19 在根樹中，若每個頂點的出次小于或等于m，稱這棵樹為m叉樹。若每個頂點的出次恰好等于m或零，則稱這棵樹為完全m叉樹。當m=2時，稱為二叉樹、完全二叉樹。在實際問題中常討論葉子上帶權(quán)的二叉樹。令有s個葉子的二叉樹T各葉子的權(quán)分別為pi，根到各葉子的距離(層次)為li(i1，s)，這樣二叉樹T的總權(quán)數(shù)siiilpTm1)(滿足總權(quán)最小的二叉樹稱為最優(yōu)二叉樹。霍夫曼(D A Huffman)