第八章 圖與網(wǎng)絡分析

1、1ab例例1、哥尼斯堡七橋問題、哥尼斯堡七橋問題bcad2l一、圖的概念：一、圖的概念：1 1、圖：、圖：點和線所組成的圖形，記為點和線所組成的圖形，記為g=(v,e)，其中，其中v是是點的集合，點的集合，e是邊的集合。是邊的集合。2、端點、關聯(lián)邊：、端點、關聯(lián)邊：聯(lián)結點聯(lián)結點vi,vj的邊記作的邊記作e=(vi,vj)，稱，稱vi,vj為為e的端點，也稱的端點，也稱e為為vi,vj的關聯(lián)邊。的關聯(lián)邊。、相鄰點、相鄰邊：、相鄰點、相鄰邊：具有同一條關聯(lián)邊的點為相鄰點，具有公共端點的邊為具有同一條關聯(lián)邊的點為相鄰點，具有公共端點的邊為相鄰邊。相鄰邊。4、環(huán)：、環(huán)：一條邊的兩個端點相同，則稱該邊為

2、環(huán)（自回路）。一條邊的兩個端點相同，則稱該邊為環(huán)（自回路）。6.1 6.1 圖與網(wǎng)絡的基本概念圖與網(wǎng)絡的基本概念35、多重邊：、多重邊：若兩端之間有多于一條邊相關聯(lián)，稱這些邊為多重邊。若兩端之間有多于一條邊相關聯(lián)，稱這些邊為多重邊。 6、簡單圖與多重圖：、簡單圖與多重圖：不含環(huán)和多重邊的圖稱為簡單圖，無環(huán)但不含環(huán)和多重邊的圖稱為簡單圖，無環(huán)但含有多重邊的圖稱為多重圖。含有多重邊的圖稱為多重圖。7、次：、次：點點v的關聯(lián)邊個數(shù)稱為點的關聯(lián)邊個數(shù)稱為點v的次，記作的次，記作d(v)。8、懸掛點、懸掛邊：、懸掛點、懸掛邊：稱次為稱次為1的點為懸掛點，懸掛點所關聯(lián)的邊為懸掛邊。的點為懸掛點，懸掛點所關

3、聯(lián)的邊為懸掛邊。v4v3v1v2e1e2e3e4e5e64定理：定理： 圖g=(v,e)中，所有點的次數(shù)之和等于邊數(shù)的兩倍。中，所有點的次數(shù)之和等于邊數(shù)的兩倍。二、連通圖二、連通圖1、鏈、圈：、鏈、圈：在無向圖在無向圖g=(v,e)，稱一個點和邊交替的序列，稱一個點和邊交替的序列vi1,ei1,vi2,ei2,vit-1,vit為連接為連接vi1和和vit的一條鏈。的一條鏈。簡記為簡記為vi1,vi2,vit。其中。其中eik=(vik,vik+1),k=1,2,t-1。點邊序列中沒有重復的點稱為點邊序列中沒有重復的點稱為初級鏈。初級鏈。若鏈首尾兩端點重合，則稱為若鏈首尾兩端點重合，則稱為圈。

4、圈。v6v5v4v3v2v1e1e5e4e3e2e6e7e8e9e10s1=v6,v5,v1,v5,v4,v3s2=v6,v5,v1,v4,v352、連通圖：、連通圖：如果圖中任意兩點間至少有一條鏈相連，則如果圖中任意兩點間至少有一條鏈相連，則稱此圖為連通圖。稱此圖為連通圖。任何一個連通圖都可以分為若干個連通子圖，每個連通子任何一個連通圖都可以分為若干個連通子圖，每個連通子圖稱為由原圖的分圖。圖稱為由原圖的分圖。6例例2、有有5名運動員參加游泳比賽，問如何安排比賽，才能名運動員參加游泳比賽，問如何安排比賽，才能 使每位運動員都不連續(xù)地參加比賽？使每位運動員都不連續(xù)地參加比賽？ 運動員運動員50

5、m仰泳仰泳50m蛙泳蛙泳100m蝶泳蝶泳100m自由泳自由泳200m自由泳自由泳甲甲乙乙丙丙丁丁戊戊7三、子圖：三、子圖：的子圖。的子圖。是是則稱則稱，），如果），如果（）（設有兩個圖設有兩個圖212121222111ggeevve,vg,e,vg的真子圖。的真子圖。是是，則稱，則稱，如果如果212121ggeevv。的生成子圖（部分圖）的生成子圖（部分圖）是是，則稱，則稱，如果如果212121ggeevvv3e1v1v2e2e3e4e6v2e3e4v3v3v1v2e2e3e48四、有向圖：四、有向圖：1、弧、有向圖：、弧、有向圖：帶有方向的邊稱為弧，記作帶有方向的邊稱為弧，記作a= (vi,

6、vj)。由一些由一些點點和和弧弧組成的集合稱為有向圖，記作組成的集合稱為有向圖，記作d=(v,a) 。a表示表示g中弧的集合。中弧的集合。、路：、路：在有向圖在有向圖d=(v,a)中，稱鏈中，稱鏈vi1,vi2,vit為一條從為一條從vi1到到vit的路。若的路。若vi1=vit，則稱之為回路。，則稱之為回路。s1=v6,v5,v1,v5,v4,v3 s2=v1, v5,v1v6v5v4v3v2v1e1e5e4e3e2e6e7e8e9e1096.2 6.2 樹與最小樹與最小生成生成樹樹l一、樹的概念：一、樹的概念：l樹：無圈的連通圖。樹：無圈的連通圖。l二、樹的性質：二、樹的性質：l（1）樹枝

7、數(shù)等于頂點數(shù)減）樹枝數(shù)等于頂點數(shù)減1；l（2）樹的任意兩個頂點之間有且僅有一條初級鏈。）樹的任意兩個頂點之間有且僅有一條初級鏈。l（3）去掉樹的任一樹枝，便得到一個非連通圖；）去掉樹的任一樹枝，便得到一個非連通圖；l（4）在樹中任意兩個頂點間添上一條邊，恰好得到一）在樹中任意兩個頂點間添上一條邊，恰好得到一 l 個初級圈。個初級圈。l（5）在所有連通的生成子圖中，生成樹的邊數(shù)最少。）在所有連通的生成子圖中，生成樹的邊數(shù)最少。10l三、根樹（有向樹）：三、根樹（有向樹）：ld=(v,a)中，中，v到到d的任一頂點都有路，則的任一頂點都有路，則v稱為稱為d的根，的根，d稱為以稱為以v為根的根樹或有

8、向樹。為根的根樹或有向樹。l四、圖的生成樹：四、圖的生成樹：的生成樹。的生成樹。為為）是樹，則稱）是樹，則稱（）的生成子圖，如果）的生成子圖，如果（）是圖）是圖（設圖設圖gte,vte,vge,vtv6v5v4v3v2v1v6v5v4v3v2v111定理定理2： 圖g有生成樹的充要條件是圖有生成樹的充要條件是圖g是連通圖。是連通圖。尋找生成樹的方法：尋找生成樹的方法：、破圈法：、破圈法：在連通圖中任取一個圈，去掉圈上的任意一條在連通圖中任取一個圈，去掉圈上的任意一條 邊，對余下的圖重復這個步驟，直至無圈為止。邊，對余下的圖重復這個步驟，直至無圈為止。、避圈法：、避圈法：每次增加一條邊，且與已有

9、邊不構成圈，直至恰每次增加一條邊，且與已有邊不構成圈，直至恰 有有p-1條邊為止。條邊為止。v6v5v4v3v2v112例、例、下圖是某建筑物的平面圖，要求在其內(nèi)部從每一房下圖是某建筑物的平面圖，要求在其內(nèi)部從每一房間都能走到別的所有的房間，問至少要在墻上開多少門？間都能走到別的所有的房間，問至少要在墻上開多少門？ 試給出一個開門的方案。試給出一個開門的方案。 一一二二三三四四五五六六七七八八九九一一二二三三四四五五六六七七八八九九一一二二三三四四五五六六七七八八九九136.3 6.3 最小樹問題最小樹問題一、賦權圖：一、賦權圖：與點或邊有關的某些與點或邊有關的某些數(shù)量指標數(shù)量指標，通常稱之為

10、，通常稱之為“權權”。定義：定義：圖圖g中中,如果每條邊如果每條邊(弧弧) (vi,vj)都被賦予一個權數(shù)都被賦予一個權數(shù)wij, 則稱則稱g為賦權圖為賦權圖. 權可以表示為：權可以表示為：距離、費用、通過能力（數(shù)量）等。距離、費用、通過能力（數(shù)量）等。與無向圖和有向圖相對應，賦權圖可分為無向賦權圖和與無向圖和有向圖相對應，賦權圖可分為無向賦權圖和有向賦權圖，分別記為有向賦權圖，分別記為g=(v,e,w)和和d=(v,a,w)。14二、最小生成樹（最小樹）：二、最小生成樹（最小樹）：定義：定義：在給定連通賦權圖在給定連通賦權圖g=(v,e,w)中，求中，求g的生成樹的生成樹t=(v,e )，使

11、，使e 各邊權各邊權wij( 0)的總和最小的問題稱為最小樹的總和最小的問題稱為最小樹問題。其數(shù)學模型為：問題。其數(shù)學模型為：其中其中t*稱為最小樹。稱為最小樹。 許多網(wǎng)絡問題都可歸結為最小樹問題，如設計長度最許多網(wǎng)絡問題都可歸結為最小樹問題，如設計長度最小的公路網(wǎng)把若干城市聯(lián)通；設計用料最省的電話線網(wǎng)把小的公路網(wǎng)把若干城市聯(lián)通；設計用料最省的電話線網(wǎng)把有關單位聯(lián)系起來。有關單位聯(lián)系起來。15求最小樹的方法：求最小樹的方法：、破圈法、破圈法(管梅谷算法管梅谷算法) ：（）先從圖（）先從圖g任取一個圈，并從圈中去掉一條權最大的邊。任取一個圈，并從圈中去掉一條權最大的邊。若在同一圈中有幾條都是權最

12、大邊，則任選其中一邊去掉若在同一圈中有幾條都是權最大邊，則任選其中一邊去掉。（）在余下的子圈中，重復上述步驟，直至沒有圈止。（）在余下的子圈中，重復上述步驟，直至沒有圈止。、避圈法、避圈法(kruskal算法算法) ：開始選一條權最小的邊，以后每開始選一條權最小的邊，以后每步從未選的邊中選取一條權最小的邊，使它與已選邊不構成步從未選的邊中選取一條權最小的邊，使它與已選邊不構成圈，直至選夠圈，直至選夠q1條邊止。條邊止。v2v1v4v322344546v5v2v1v4v32234v516例、例、今要在七個城市之間修筑一個公路網(wǎng)，每個城市之今要在七個城市之間修筑一個公路網(wǎng)，每個城市之間的公路修筑費

13、用就是各條邊上的權，試求總修筑費用最間的公路修筑費用就是各條邊上的權，試求總修筑費用最小的公路網(wǎng)。小的公路網(wǎng)。v1v4v7v6v5v3v28567632445310v1v4v7v6v5v3v2324453176.6.4 4 最最短路短路問題問題 最短路問題是網(wǎng)絡理論中應用最廣泛的問題之一，許最短路問題是網(wǎng)絡理論中應用最廣泛的問題之一，許多優(yōu)化問題可以使用這個模型，如管道鋪設，設備更新，多優(yōu)化問題可以使用這個模型，如管道鋪設，設備更新，線路安排等。線路安排等。 給定給定d=(v,a,w)，其中，其中wij w，表示弧，表示弧(vi,vj)的權（可的權（可以是費用、時間、距離等）。設以是費用、時間

14、、距離等）。設vs和和vt是是d中任意兩頂點，中任意兩頂點，求一條路，使它是從求一條路，使它是從vs到到vt的所有路中總權最小的路。的所有路中總權最小的路。 其數(shù)學模型為：其數(shù)學模型為：ijwpwmin)(* (vi,vj)p 18求最短路的求最短路的狄克斯特狄克斯特dijkstradijkstra標號法標號法（w wijij 0 0）1、基于以下基于以下原理原理：若序列：若序列vs,vi1,vik,vt是從是從vs到到vt的最的最短路，則序列短路，則序列vs,vi1,vik必為從必為從vs到到vik的最短路。的最短路。 2、dijkstra標號法的基本思想是采用標號法的基本思想是采用兩種標號

15、兩種標號： t標號標號與與p標號標號，t標號為臨時性標號標號為臨時性標號(temporary label)，p標號為永久性標號標號為永久性標號(permanent label)。 從從vs開始，逐步向外探尋最短路。給開始，逐步向外探尋最短路。給vi點點p標號時，表標號時，表示從示從vs到到vi點的最短路權，點的最短路權，vi的標號不再改變。給的標號不再改變。給vi點點t標號標號時，表示從時，表示從vs到到vi點的最短路權上界的估計。凡沒有得到點的最短路權上界的估計。凡沒有得到p標號的點都有標號的點都有t標號。標號法每一步都是把某一標號。標號法每一步都是把某一t標號點改標號點改為為p標號，當終點

16、標號，當終點vt得到得到p標號時，計算全部結束。如果點標號時，計算全部結束。如果點vj不能由不能由t標號變?yōu)闃颂栕優(yōu)閜標號，則說明標號，則說明vs到到vj不存在路。不存在路。19 3、步驟：、步驟： (1)給給vs以以p標號，標號，p(vs)=0，其余各點給，其余各點給t標號，且標號，且 t(vi)=+ 。 (2)若若vi點為剛得到點為剛得到p標號的點，考慮標號的點，考慮t標號點標號點vj,(vi,vj) a。 對對vj的的t標號進行如下的更改：標號進行如下的更改：t(vj)=mint(vj),p(vi)+wij (3)比較所有具有比較所有具有t標號點，把最小者改為標號點，把最小者改為p標號，

17、即：標號，即： p(vjo)=mint(vj) vj為為t標號標號 若全部點均為若全部點均為p標號。則停止。否則以標號。則停止。否則以vjo代代vi，返回，返回(2)20v6v5v4v3v2v1v8v7356117423521695（1） p(v1)=0 , t(vi)=+ , i=2,3,4,5,6,7,8 t(v2)=min+ ,0+3=3， k(v2)=v1 t(v3)=min+ ,0+5=5， k(v3)=v1 t(v4)=min+ ,0+6=6， k(v4)=v1（2） p(v2)=3 t(v3)=min5,3+1=4， k(v3)=v2 t(v5)=min+ ,3+7=10， k(v5)=v2 t(v6)=min+ ,3+4=7， k(v4)=v221v6v5v4v3v2v1v8v7356117423521695（3） p(v3)=4 t(v4)=min6,4+1=5， k(v4)=v3 t(v6)=min7,4+2=6， k(v6)=v3（4） p(v4)=5 t(v6)=min6,5+3=6， k(v6)