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

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

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

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

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

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

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

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

8、連，則稱此圖為連通圖。任何一個不連通圖都可以分為若干個連通子圖，每一個稱為一個分圖。三、圖的矩陣表示圖的矩陣表示方法有權(quán)矩陣、鄰接矩陣、關(guān)聯(lián)矩陣、回路矩陣、割集矩陣等。定義11 網(wǎng)絡(luò)賦權(quán)圖G=（V，E），其中邊(vi,vj)有權(quán)wij,構(gòu)造矩陣A=(aij)nn,其中其它0),(Evvwajiijij則稱A為網(wǎng)絡(luò)G的權(quán)矩陣?yán)簩懗錾蠄D的權(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是歐拉圖，當(dāng)且僅當(dāng)G中無奇點(diǎn)。推論1 無向連通圖G為歐拉圖，當(dāng)且僅當(dāng)G的邊集可劃分為若干個初等回路。推論2 無向連通圖G有歐拉道路，當(dāng)且僅當(dāng)G中恰有兩個奇點(diǎn)。定理4 連通有向圖G是歐拉圖，當(dāng)且僅當(dāng)它每個頂點(diǎn)的出次等于入次。 （二中國郵路問題 一個郵遞員，負(fù)責(zé)某一地區(qū)的信件投遞。他每天要從郵局出發(fā)，走遍該地區(qū)所有街道再返回郵局，問應(yīng)如何安排送信的路線可以使所走的總路程最短？這個問題是我國管梅谷教授在196

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

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

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

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

14、程，直到所有的邊試驗(yàn)完畢。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，反復(fù)2再檢查剩余的弦，直到全部弦檢查完畢為止。例：用破圈法求上圖中的一棵最小生成樹。定理9 圖G的生成樹T為最小樹，當(dāng)且僅當(dāng)對任一e來說，e是T+e中與之對應(yīng)的圈e中的最大權(quán)邊。四、根樹及其應(yīng)用定義17 若一個有向圖在不考慮邊的方向時是一棵樹，則稱這個有向圖為有向樹。定義18 有向樹T，恰有一個結(jié)點(diǎn)入次為0，其余各點(diǎn)入次均為1，則稱T為根樹又稱外向樹）。根樹中入次為0的點(diǎn)稱為根。根樹中出次為0的點(diǎn)稱為葉，其他頂點(diǎn)稱為分枝點(diǎn)。由根到某一頂點(diǎn)vi的道路長度設(shè)每邊長度為1），稱為點(diǎn)vi的層次。定義 19 在根樹中，若每個頂點(diǎn)的出次小于或等于m，稱這棵樹為m叉樹。若每個頂點(diǎn)的出次恰好等于m或零，則稱這棵樹為完全m叉樹。當(dāng)m=2時，稱為二叉樹、完全二叉樹。在實(shí)際問題中常討論葉子上帶權(quán)的二叉樹。令有s個葉子的二叉樹T各葉子的權(quán)分別為pi，根到各葉子的距離(層次)為li(i1，s)，這樣二叉樹T的總權(quán)數(shù)siiilpTm1)(滿足總權(quán)最小的二叉樹稱為最優(yōu)二叉樹?；舴蚵?D A Huffman)