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

1、第八章 圖與網(wǎng)絡(luò)分析1引例哥尼斯堡七橋問(wèn)題ABCDBDAC2環(huán)球旅行問(wèn)題：3環(huán)球旅行問(wèn)題的解4第1節(jié) 圖與網(wǎng)絡(luò)的基本知識(shí)圖可以用來(lái)做什么：管理當(dāng)中，事物及事物間的聯(lián)系可以用圖來(lái)描述五只球隊(duì)的比賽情況甲乙丙丁戊甲乙丙丁戊ABCD工作分配問(wèn)題圖已經(jīng)應(yīng)用于物質(zhì)結(jié)構(gòu)、交通、信息傳遞等的描述5圖與網(wǎng)絡(luò)的基本概念（1）圖：這里討論的圖由點(diǎn)以及點(diǎn)與點(diǎn)間的連線構(gòu)成，與平面幾何的圖不同，這里只關(guān)心圖中有多少個(gè)點(diǎn)，點(diǎn)與點(diǎn)間有無(wú)連線，至于點(diǎn)與點(diǎn)間的連線是直線還是曲線，點(diǎn)的相對(duì)位置，則是無(wú)關(guān)緊要的。6圖與網(wǎng)絡(luò)的基本概念（2）定義1 一個(gè)圖是由點(diǎn)集V=vi和V中的元素的無(wú)序?qū)Φ囊粋€(gè)集合E=ek所構(gòu)成的二元組，記為G=(

2、V, E)，V中的元素vi叫做頂點(diǎn)，E中的元素ek叫做邊v2v1v5v3v4e2e1e3e4e5e6V=v1,v2,v3,v4,v5E=e1,e2,e3,e4,e5,e6e1=(v1,v1), e2=(v1,v2)例7圖與網(wǎng)絡(luò)的基本概念（3）相鄰：圖中的兩點(diǎn)間存在連線（邊），則稱這兩點(diǎn)相鄰，并稱它們是這條邊的端點(diǎn)；若兩條邊有公共的端點(diǎn)，則稱這兩條邊相鄰，并稱它們是其公共端點(diǎn)的關(guān)聯(lián)邊。v2v1v5v3v4e2e1e3e4e5e6相鄰相鄰邊數(shù)：m(G)=|E|頂點(diǎn)數(shù)：n(G)=|V|8圖與網(wǎng)絡(luò)的基本概念（4）無(wú)向邊與無(wú)向圖：若圖中任一條邊的端點(diǎn)無(wú)序，即(vi, vj)與(vj, vi)是同一條邊，

3、則稱它為無(wú)向邊，此時(shí)圖稱為無(wú)向圖。有向圖：若圖中邊(vi, vj)的端點(diǎn)是有序的，則稱它是有向邊（或?。?，vi與vj分別稱為這條有向邊的始點(diǎn)和終點(diǎn)，相應(yīng)的圖稱為有向圖。9圖與網(wǎng)絡(luò)的基本概念（5）v2v1v5v3v4e2e1e3e4e5e6環(huán)(自回路)多重邊定義2 不含環(huán)和多重邊的圖稱為簡(jiǎn)單圖。含多重邊的圖稱為多重圖。簡(jiǎn)單圖10圖與網(wǎng)絡(luò)的基本概念（6）定義3 每一對(duì)頂點(diǎn)間都有邊相連的無(wú)向簡(jiǎn)單圖稱為無(wú)向完全圖；有向完全圖是指每一對(duì)頂點(diǎn)間有且僅有一條有向邊的簡(jiǎn)單圖。完全圖頂點(diǎn)數(shù)n與邊數(shù)m間成立如下關(guān)系:m=n(n-1)/211圖與網(wǎng)絡(luò)的基本概念（7）定義4 圖G=(V, E)的點(diǎn)集V可以分為兩個(gè)非空

4、子集X，Y，即X Y =V，X Y=，使得E中的每條邊的兩個(gè)端點(diǎn)中必有一個(gè)屬于X，另一個(gè)屬于Y，則稱G為二部圖（偶圖），有時(shí)記為G=(X, Y, E)二部圖非二部圖12圖與網(wǎng)絡(luò)的基本概念（8）定義5 以v為端點(diǎn)的邊數(shù)，叫做點(diǎn)v的次(degree)，記作deg(v), 或簡(jiǎn)記為d(v)。v2v1v5v3v4e2e1e3e4e5e6d(v1)=4d(v2)=3懸掛點(diǎn)孤立點(diǎn)懸掛邊偶點(diǎn)奇點(diǎn)13圖中頂點(diǎn)次的性質(zhì)定理1 任何圖中頂點(diǎn)次數(shù)的總和等于邊數(shù)的2倍。定理2 任何圖中次為奇數(shù)的頂點(diǎn)必有偶數(shù)個(gè)。定義6 在有向圖中，以頂點(diǎn)v為始點(diǎn)的邊數(shù)稱為頂點(diǎn)v的出次，記為d+(v)；以v為終點(diǎn)的邊數(shù)稱為v的入次，記為

5、d-(v)。頂點(diǎn)v的出次與入次的和稱為點(diǎn)v的次。14圖與網(wǎng)絡(luò)的基本概念（9）定義7 圖G=(V, E), 若E是E的子集，若V是V的子集，且E中的邊僅與V中的頂點(diǎn)相關(guān)聯(lián)，則稱G = (V, E)為圖G的一個(gè)子圖，特別地，若V =V, 則稱G為G的一個(gè)生成子圖（支撐子圖）。子圖生成子圖15圖與網(wǎng)絡(luò)的基本概念（10）有時(shí)需要用圖來(lái)表示事物及事物之間的定量的聯(lián)系，這時(shí)圖中除了頂點(diǎn)與邊外，還有與點(diǎn)或邊有關(guān)的某些數(shù)量指標(biāo)，常稱它們?yōu)椤皺?quán)”，權(quán)在圖中可以表示距離、費(fèi)用、通過(guò)能力等。這種點(diǎn)或邊帶權(quán)的圖稱為網(wǎng)絡(luò)（或賦權(quán)圖）31311278534251616連通圖（1）定義8 無(wú)向圖中一個(gè)點(diǎn)、邊交錯(cuò)的序列，序列

6、中的第一個(gè)和最后一個(gè)元素都是點(diǎn)，若其中每條邊以序列中位于它之前和之后的點(diǎn)為端點(diǎn)，則稱這個(gè)點(diǎn)邊序列為圖中連接其第一個(gè)點(diǎn)與最后一個(gè)點(diǎn)的鏈。鏈中所含的邊數(shù)稱為鏈長(zhǎng)。鏈，但只是簡(jiǎn)單鏈而非初等鏈簡(jiǎn)單鏈：沒(méi)有重復(fù)邊；初等鏈：既無(wú)重復(fù)邊也無(wú)重復(fù)點(diǎn)。對(duì)有向圖可類似定義鏈，如果各邊的方向一致，則稱為道路。17連通圖（2）定義9 若在無(wú)向圖中，一條鏈的第一個(gè)點(diǎn)與最后一個(gè)點(diǎn)重合，則稱這條鏈為圈。只有重復(fù)點(diǎn)而無(wú)重復(fù)邊的圈為簡(jiǎn)單圈，既無(wú)重復(fù)點(diǎn)又無(wú)重復(fù)邊的圈為初等圈。初等圈非簡(jiǎn)單的圈18連通圖（3）有向圖無(wú)向圖路鏈回路圈路(邊的方向一致)不是路19連通圖（4）定義10 一個(gè)圖中任意兩點(diǎn)間至少有一條鏈相連，則稱此圖為連通圖

7、。任何一個(gè)不連通圖總可以分為若干個(gè)連通子圖，每一個(gè)稱為原圖的一個(gè)分圖（連通分支）。連通圖非連通圖20圖的矩陣表示鄰接矩陣對(duì)于圖G=(V, E), |V|=n, 構(gòu)造一個(gè)矩陣A=(aij)nn, 其中： v1v2v3v4v5v621圖的矩陣表示權(quán)矩陣對(duì)于網(wǎng)絡(luò)（賦權(quán)圖）G=(V, E), |V|=n, 其中邊(vi, vj)上有權(quán)wij，構(gòu)造一個(gè)矩陣A=(aij)nn, 其中： 342516v1v2v3v422歐拉回路（1）定義13 連通圖G中，若存在一條道路，經(jīng)過(guò)每邊一次且僅一次，則稱這條道路為歐拉道路。若存在一條回路經(jīng)過(guò)每邊一次也僅一次，則稱這條回路為歐拉回路。具有歐拉回路的圖稱為歐拉圖（E圖

8、）。定理3 無(wú)向連通圖G是歐拉圖，當(dāng)且僅當(dāng)G中無(wú)奇點(diǎn)23歐拉回路（2）推論1 無(wú)向連通圖G為歐拉圖，當(dāng)且僅當(dāng)G的邊集可以劃分為若干個(gè)初等回路。推論2 無(wú)向連通圖G中有歐拉道路，當(dāng)且僅當(dāng)G中恰好有兩個(gè)奇點(diǎn)。ABCD哥尼斯堡七橋問(wèn)題無(wú)解一筆畫(huà)問(wèn)題24歐拉回路（3）定理4 連通有向圖G是歐拉圖，當(dāng)且僅當(dāng)它的每個(gè)頂點(diǎn)的出次等于入次。連通有向圖G有歐拉道路，當(dāng)且僅當(dāng)這個(gè)圖中除了兩個(gè)頂點(diǎn)外，其余每個(gè)頂點(diǎn)的出次等于入次，且這兩個(gè)頂點(diǎn)中，一個(gè)頂點(diǎn)的入次比出次多1，另一個(gè)的入次比出次少1。v1v2v3v4v5v625樹(shù)樹(shù)的概念定義14 連通且不含圈的無(wú)向圖稱為樹(shù)。樹(shù)中次為1的點(diǎn)稱為樹(shù)葉，次大于1的點(diǎn)稱為分枝點(diǎn)。

9、ABCDEFGHIJKLMN廠長(zhǎng)人事科財(cái)務(wù)科總工程師生產(chǎn)副廠長(zhǎng)新產(chǎn)品開(kāi)發(fā)科技術(shù)科生產(chǎn)科設(shè)備科供應(yīng)科動(dòng)力科經(jīng)營(yíng)副廠長(zhǎng)銷售科檢驗(yàn)科26樹(shù)樹(shù)的性質(zhì)定理6 T=(V, E), |V|=n, |E|=m, 則下列關(guān)于樹(shù)的說(shuō)法是等價(jià)的。（1）T是一個(gè)樹(shù)（即T是不含圈的連通圖）27樹(shù)樹(shù)的性質(zhì)（2）T無(wú)圈，且m=n-128樹(shù)樹(shù)的性質(zhì)（3）T連通，且m=n-129樹(shù)樹(shù)的性質(zhì)（4）T無(wú)圈，但每加一新邊就得到唯一的一個(gè)圈T是邊數(shù)最多的無(wú)圈圖30樹(shù)樹(shù)的性質(zhì)（5）T連通，但任舍去一邊就不連通T是邊數(shù)最少的連通圖31樹(shù)樹(shù)的性質(zhì)（6）T中任意兩點(diǎn)有唯一一條鏈相連32生成樹(shù)概念定義15 若圖G的生成子圖是一棵樹(shù)，則稱該樹(shù)為圖

10、G的生成樹(shù)（支撐樹(shù)），或簡(jiǎn)稱為圖G的樹(shù)。定理7 圖G有生成樹(shù)的充分必要條件是圖G是連通的33生成樹(shù)解法（1）避圈法這種方法是每步從連通圖中選出一條邊，使得它與已經(jīng)選出的邊不構(gòu)成圈，直到選夠n-1條邊為止。一個(gè)圖的生成樹(shù)不是唯一的。34避圈法的另一種表述先去掉圖G中所有邊，只留下點(diǎn)，每次任意放回一條邊，使之與已經(jīng)放回的邊不構(gòu)成圈，反復(fù)進(jìn)行，直到有（n-1）條邊為止。5個(gè)頂點(diǎn)，4條邊35生成樹(shù)解法（2）破圈法這種方法是每步從連通圖中選一個(gè)圈，并去掉該圈的一條邊，直到圖中不含圈為止。36另一種解法37最小生成樹(shù)概念定義16 連通圖G=(V, E), 每條邊上有非負(fù)權(quán)L(e)，一棵生成樹(shù)上各邊的權(quán)之和

11、，稱為這棵生成樹(shù)的權(quán)，具有最小權(quán)的生成樹(shù)，稱為最小生成樹(shù)（最小支撐樹(shù)），簡(jiǎn)稱最小樹(shù)。例如 如何用造價(jià)最省的電話線網(wǎng)將各有關(guān)單位連起來(lái)的問(wèn)題，就歸結(jié)為求最小生成樹(shù)的問(wèn)題。354367124非最小樹(shù)38最小生成樹(shù)解法1（Kruskal算法）避圈法：這種方法每步從圖中挑選一條邊，滿足：（1）它與已經(jīng)選出的邊不構(gòu)成圈；（2）它是滿足條件（1）的權(quán)最小的邊，直到選夠n-1條邊為止。141213144553245214121314455324529個(gè)頂點(diǎn)，8條邊39避圈法另一種表述先去掉圖G的所有邊，只留下頂點(diǎn)，每次放回一條權(quán)最小的邊，使之與已經(jīng)放回的邊不構(gòu)成圈，反復(fù)進(jìn)行，直到有（n-1）條邊為止。948

12、2333791423316個(gè)頂點(diǎn)，5條邊40最小生成樹(shù)解法（2）破圈法：這種方法每步從圖中任選一個(gè)圈，然后去掉該圈中權(quán)最大的邊，直到圖中沒(méi)有圈為止。14121314455324529個(gè)頂點(diǎn)，8條邊41破圈法舉例948233379194823337916個(gè)頂點(diǎn)，5條邊42破圈法舉例v4v2v3v16215846最小生成樹(shù)的權(quán)= 9/v4v2v3v1621546v4v2v3v162154/v4v2v3v16214/v4v2v3v162143最短路問(wèn)題最短路問(wèn)題是網(wǎng)絡(luò)理論中應(yīng)用最廣泛的問(wèn)題之一，許多優(yōu)化問(wèn)題，如設(shè)備更新、管道鋪設(shè)、線路安排等都可以化為最短路問(wèn)題求解。最短路問(wèn)題的提法：設(shè)G=(V, E

13、)為連通圖，圖中的各邊(vi, vj)有非負(fù)權(quán)l(xiāng)ij (lij=表示vi, vj間無(wú)邊), vs, vt是圖中任意兩點(diǎn)，求一條道路，使它是從vs到vt的所有道路中總權(quán)最小的道路。44Dijkstra算法原理：若(vs, v1, , vn-1, vn)是vs到vn的最短路，則(vs, v1, , vn-1)是vs到vn-1的最短路。思路：采用標(biāo)號(hào)法。使用兩種標(biāo)號(hào)，T標(biāo)號(hào)和P標(biāo)號(hào)，一個(gè)點(diǎn)的P標(biāo)號(hào)是永久性標(biāo)號(hào)，表示起點(diǎn)到該點(diǎn)最短路的權(quán)，它一旦給出就不再改變；而點(diǎn)的T標(biāo)號(hào)是臨時(shí)性的標(biāo)號(hào)，表示對(duì)起點(diǎn)到該點(diǎn)最短路的權(quán)的估計(jì)值，當(dāng)?shù)玫礁_的估計(jì)值時(shí)要修改原來(lái)的T標(biāo)號(hào)，此外算法的每一步要把某一個(gè)點(diǎn)的T標(biāo)號(hào)改

14、成P標(biāo)號(hào)，當(dāng)?shù)玫浇K點(diǎn)vt的P標(biāo)號(hào)時(shí)算法結(jié)束。45Dijkstra算法步驟第一步：給vs點(diǎn)P標(biāo)號(hào)P(vs )=0, 其余點(diǎn)T標(biāo)號(hào)T(vi)=+ 第二步：若vi為剛獲得P標(biāo)號(hào)的點(diǎn)，則修改以vi為起點(diǎn)的各邊終點(diǎn)的T標(biāo)號(hào)為下兩個(gè)數(shù)中的較小者：一個(gè)是vi的P標(biāo)號(hào)與該邊權(quán)之和，另一個(gè)是該終點(diǎn)原來(lái)的T標(biāo)號(hào)。第三步：取所有具有T標(biāo)號(hào)的點(diǎn)中T標(biāo)號(hào)值最小的點(diǎn)，將其T標(biāo)號(hào)改為P標(biāo)號(hào)。若本次得到P標(biāo)號(hào)的點(diǎn)為終點(diǎn)，算法終止，否則返回上一步。46例（p251）465447796554104654477965541046給起點(diǎn)P標(biāo)號(hào)0，其余點(diǎn)T標(biāo)號(hào)（在下面的求解過(guò)程中，粉色的數(shù)字為P標(biāo)號(hào)）修改以剛獲得P標(biāo)號(hào)的點(diǎn)為起點(diǎn)的邊的

15、終點(diǎn)的T標(biāo)號(hào)；然后將最小的T標(biāo)號(hào)改成P標(biāo)號(hào)4746544779655410496846544779655410496848465447796554104968131446544779655410496813141749465447796554104968131415465447796554104968131415最短路線見(jiàn)圖50v1v2v3v4v6v5v7v838422433123340T(v2)=min(,0+4)=4, T(v3)=min(,0+8)=8黃色數(shù)字表示P標(biāo)號(hào)最短路問(wèn)題舉例51v1v2v3v4v6v5v7v83842243312334048比較所有的T標(biāo)號(hào)，4最小。所以P（v2

16、）=44從v2出發(fā)，到v4,v5。T(v4)=min(,4+3)=7, T(v5)=min(,4+4)=87852v1v2v3v4v6v5v7v83842243312334048比較所有的T標(biāo)號(hào)，7最小。所以P（v4）=74從v4出發(fā)，到v6。T(v6)=min(,7+3)=107871053v1v2v3v4v6v5v7v83842243312334048比較所有的T標(biāo)號(hào)，8最小。所以P(v3)=P(v5)=84從v3出發(fā)，到v7, T(v7)=min(,8+3)=11從v5出發(fā)，到v8, T(v8)=min(,8+4)=127871088111254v1v2v3v4v6v5v7v83842243312334048比較所有的T標(biāo)號(hào)，10最小。所以P(v6)=104從v6出發(fā)，到v7, T(v7)=min(11,10+3)=11比較所有的T標(biāo)號(hào)，11最小。所以