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

《第八章 圖與網(wǎng)絡(luò)分析》由會(huì)員分享，可在線(xiàn)閱讀，更多相關(guān)《第八章 圖與網(wǎng)絡(luò)分析（22頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、1AB例例1、哥尼斯堡七橋問(wèn)題、哥尼斯堡七橋問(wèn)題BCAD2l一、圖的概念：一、圖的概念：1 1、圖：、圖：點(diǎn)和線(xiàn)所組成的圖形，記為點(diǎn)和線(xiàn)所組成的圖形，記為G=(V,E)，其中，其中V是是點(diǎn)的集合，點(diǎn)的集合，E是邊的集合。是邊的集合。2、端點(diǎn)、關(guān)聯(lián)邊：、端點(diǎn)、關(guān)聯(lián)邊：聯(lián)結(jié)點(diǎn)聯(lián)結(jié)點(diǎn)vi,vj的邊記作的邊記作e=(vi,vj)，稱(chēng)，稱(chēng)vi,vj為為e的端點(diǎn)，也稱(chēng)的端點(diǎn)，也稱(chēng)e為為vi,vj的關(guān)聯(lián)邊。的關(guān)聯(lián)邊。、相鄰點(diǎn)、相鄰邊：、相鄰點(diǎn)、相鄰邊：具有同一條關(guān)聯(lián)邊的點(diǎn)為相鄰點(diǎn)，具有公共端點(diǎn)的邊為具有同一條關(guān)聯(lián)邊的點(diǎn)為相鄰點(diǎn)，具有公共端點(diǎn)的邊為相鄰邊。相鄰邊。4、環(huán)：、環(huán)：一條邊的兩個(gè)端點(diǎn)相同，則稱(chēng)該邊為

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

3、聯(lián)的邊為懸掛邊。v4v3v1v2e1e2e3e4e5e64定理：定理： 圖G=(V,E)中，所有點(diǎn)的次數(shù)之和等于邊數(shù)的兩倍。中，所有點(diǎn)的次數(shù)之和等于邊數(shù)的兩倍。二、連通圖二、連通圖1、鏈、圈：、鏈、圈：在無(wú)向圖在無(wú)向圖G=(V,E)，稱(chēng)一個(gè)點(diǎn)和邊交替的序列，稱(chēng)一個(gè)點(diǎn)和邊交替的序列vi1,ei1,vi2,ei2,vit-1,vit為連接為連接vi1和和vit的一條鏈。的一條鏈。簡(jiǎn)記為簡(jiǎn)記為vi1,vi2,vit。其中。其中eik=(vik,vik+1),k=1,2,t-1。點(diǎn)邊序列中沒(méi)有重復(fù)的點(diǎn)稱(chēng)為點(diǎn)邊序列中沒(méi)有重復(fù)的點(diǎn)稱(chēng)為初級(jí)鏈。初級(jí)鏈。若鏈?zhǔn)孜矁啥它c(diǎn)重合，則稱(chēng)為若鏈?zhǔn)孜矁啥它c(diǎn)重合，則稱(chēng)為圈。

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

5、m仰泳仰泳50m蛙泳蛙泳100m蝶泳蝶泳100m自由泳自由泳200m自由泳自由泳甲甲乙乙丙丙丁丁戊戊7三、子圖：三、子圖：的子圖。的子圖。是是則稱(chēng)則稱(chēng)，），如果），如果（）（設(shè)有兩個(gè)圖設(shè)有兩個(gè)圖212121222111GGEEVVE,VG,E,VG的真子圖。的真子圖。是是，則稱(chēng)，則稱(chēng)，如果如果212121GGEEVV。的生成子圖（部分圖）的生成子圖（部分圖）是是，則稱(chēng)，則稱(chēng)，如果如果212121GGEEVVv3e1v1v2e2e3e4e6v2e3e4v3v3v1v2e2e3e48四、有向圖：四、有向圖：1、弧、有向圖：、弧、有向圖：帶有方向的邊稱(chēng)為弧，記作帶有方向的邊稱(chēng)為弧，記作a= (vi,

6、vj)。由一些由一些點(diǎn)點(diǎn)和和弧弧組成的集合稱(chēng)為有向圖，記作組成的集合稱(chēng)為有向圖，記作D=(V,A) 。A表示表示G中弧的集合。中弧的集合。、路：、路：在有向圖在有向圖D=(V,A)中，稱(chēng)鏈中，稱(chēng)鏈vi1,vi2,vit為一條從為一條從vi1到到vit的路。若的路。若vi1=vit，則稱(chēng)之為回路。，則稱(chēng)之為回路。S1=v6,v5,v1,v5,v4,v3 S2=v1, v5,v1v6v5v4v3v2v1e1e5e4e3e2e6e7e8e9e1096.2 6.2 樹(shù)與最小樹(shù)與最小生成生成樹(shù)樹(shù)l一、樹(shù)的概念：一、樹(shù)的概念：l樹(shù)：無(wú)圈的連通圖。樹(shù)：無(wú)圈的連通圖。l二、樹(shù)的性質(zhì)：二、樹(shù)的性質(zhì)：l（1）樹(shù)枝

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

8、向樹(shù)。為根的根樹(shù)或有向樹(shù)。l四、圖的生成樹(shù)：四、圖的生成樹(shù)：的生成樹(shù)。的生成樹(shù)。為為）是樹(shù)，則稱(chēng)）是樹(shù)，則稱(chēng)（）的生成子圖，如果）的生成子圖，如果（）是圖）是圖（設(shè)圖設(shè)圖GTE,VTE,VGE,VTv6v5v4v3v2v1v6v5v4v3v2v111定理定理2： 圖G有生成樹(shù)的充要條件是圖有生成樹(shù)的充要條件是圖G是連通圖。是連通圖。尋找生成樹(shù)的方法：尋找生成樹(shù)的方法：、破圈法：、破圈法：在連通圖中任取一個(gè)圈，去掉圈上的任意一條在連通圖中任取一個(gè)圈，去掉圈上的任意一條 邊，對(duì)余下的圖重復(fù)這個(gè)步驟，直至無(wú)圈為止。邊，對(duì)余下的圖重復(fù)這個(gè)步驟，直至無(wú)圈為止。、避圈法：、避圈法：每次增加一條邊，且與已有

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

10、，通常稱(chēng)之為“權(quán)權(quán)”。定義：定義：圖圖G中中,如果每條邊如果每條邊(弧弧) (vi,vj)都被賦予一個(gè)權(quán)數(shù)都被賦予一個(gè)權(quán)數(shù)wij, 則稱(chēng)則稱(chēng)G為賦權(quán)圖為賦權(quán)圖. 權(quán)可以表示為：權(quán)可以表示為：距離、費(fèi)用、通過(guò)能力（數(shù)量）等。距離、費(fèi)用、通過(guò)能力（數(shù)量）等。與無(wú)向圖和有向圖相對(duì)應(yīng)，賦權(quán)圖可分為無(wú)向賦權(quán)圖和與無(wú)向圖和有向圖相對(duì)應(yīng)，賦權(quán)圖可分為無(wú)向賦權(quán)圖和有向賦權(quán)圖，分別記為有向賦權(quán)圖，分別記為G=(V,E,W)和和D=(V,A,W)。14二、最小生成樹(shù)（最小樹(shù)）：二、最小生成樹(shù)（最小樹(shù)）：定義：定義：在給定連通賦權(quán)圖在給定連通賦權(quán)圖G=(V,E,W)中，求中，求G的生成樹(shù)的生成樹(shù)T=(V,E )，使

11、，使E 各邊權(quán)各邊權(quán)Wij( 0)的總和最小的問(wèn)題稱(chēng)為最小樹(shù)的總和最小的問(wèn)題稱(chēng)為最小樹(shù)問(wèn)題。其數(shù)學(xué)模型為：?jiǎn)栴}。其數(shù)學(xué)模型為：其中其中T*稱(chēng)為最小樹(shù)。稱(chēng)為最小樹(shù)。 許多網(wǎng)絡(luò)問(wèn)題都可歸結(jié)為最小樹(shù)問(wèn)題，如設(shè)計(jì)長(zhǎng)度最許多網(wǎng)絡(luò)問(wèn)題都可歸結(jié)為最小樹(shù)問(wèn)題，如設(shè)計(jì)長(zhǎng)度最小的公路網(wǎng)把若干城市聯(lián)通；設(shè)計(jì)用料最省的電話(huà)線(xiàn)網(wǎng)把小的公路網(wǎng)把若干城市聯(lián)通；設(shè)計(jì)用料最省的電話(huà)線(xiàn)網(wǎng)把有關(guān)單位聯(lián)系起來(lái)。有關(guān)單位聯(lián)系起來(lái)。15求最小樹(shù)的方法：求最小樹(shù)的方法：、破圈法、破圈法(管梅谷算法管梅谷算法) ：（）先從圖（）先從圖G任取一個(gè)圈，并從圈中去掉一條權(quán)最大的邊。任取一個(gè)圈，并從圈中去掉一條權(quán)最大的邊。若在同一圈中有幾條都是權(quán)最

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

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

14、、距離等）。設(shè)vs和和vt是是D中任意兩頂點(diǎn)，中任意兩頂點(diǎn)，求一條路，使它是從求一條路，使它是從vs到到vt的所有路中總權(quán)最小的路。的所有路中總權(quán)最小的路。 其數(shù)學(xué)模型為：其數(shù)學(xué)模型為：ijWPWmin)(* (vi,vj)P 18求最短路的求最短路的狄克斯特狄克斯特DijkstraDijkstra標(biāo)號(hào)法標(biāo)號(hào)法（W Wijij 0 0）1、基于以下基于以下原理原理：若序列：若序列vs,vi1,vik,vt是從是從vs到到vt的最的最短路，則序列短路，則序列vs,vi1,vik必為從必為從vs到到vik的最短路。的最短路。 2、Dijkstra標(biāo)號(hào)法的基本思想是采用標(biāo)號(hào)法的基本思想是采用兩種標(biāo)號(hào)

15、兩種標(biāo)號(hào)： T標(biāo)號(hào)標(biāo)號(hào)與與P標(biāo)號(hào)標(biāo)號(hào)，T標(biāo)號(hào)為臨時(shí)性標(biāo)號(hào)標(biāo)號(hào)為臨時(shí)性標(biāo)號(hào)(Temporary Label)，P標(biāo)號(hào)為永久性標(biāo)號(hào)標(biāo)號(hào)為永久性標(biāo)號(hào)(Permanent Label)。 從從vs開(kāi)始，逐步向外探尋最短路。給開(kāi)始，逐步向外探尋最短路。給vi點(diǎn)點(diǎn)P標(biāo)號(hào)時(shí)，表標(biāo)號(hào)時(shí)，表示從示從vs到到vi點(diǎn)的最短路權(quán)，點(diǎn)的最短路權(quán)，vi的標(biāo)號(hào)不再改變。給的標(biāo)號(hào)不再改變。給vi點(diǎn)點(diǎn)T標(biāo)號(hào)標(biāo)號(hào)時(shí)，表示從時(shí)，表示從vs到到vi點(diǎn)的最短路權(quán)上界的估計(jì)。凡沒(méi)有得到點(diǎn)的最短路權(quán)上界的估計(jì)。凡沒(méi)有得到P標(biāo)號(hào)的點(diǎn)都有標(biāo)號(hào)的點(diǎn)都有T標(biāo)號(hào)。標(biāo)號(hào)法每一步都是把某一標(biāo)號(hào)。標(biāo)號(hào)法每一步都是把某一T標(biāo)號(hào)點(diǎn)改標(biāo)號(hào)點(diǎn)改為為P標(biāo)號(hào)，當(dāng)終點(diǎn)

16、標(biāo)號(hào)，當(dāng)終點(diǎn)vt得到得到P標(biāo)號(hào)時(shí)，計(jì)算全部結(jié)束。如果點(diǎn)標(biāo)號(hào)時(shí)，計(jì)算全部結(jié)束。如果點(diǎn)vj不能由不能由T標(biāo)號(hào)變?yōu)闃?biāo)號(hào)變?yōu)镻標(biāo)號(hào)，則說(shuō)明標(biāo)號(hào)，則說(shuō)明vs到到vj不存在路。不存在路。19 3、步驟：、步驟： (1)給給vs以以P標(biāo)號(hào)，標(biāo)號(hào)，P(vs)=0，其余各點(diǎn)給，其余各點(diǎn)給T標(biāo)號(hào)，且標(biāo)號(hào)，且 T(vi)=+ 。 (2)若若vi點(diǎn)為剛得到點(diǎn)為剛得到P標(biāo)號(hào)的點(diǎn)，考慮標(biāo)號(hào)的點(diǎn)，考慮T標(biāo)號(hào)點(diǎn)標(biāo)號(hào)點(diǎn)vj,(vi,vj) A。 對(duì)對(duì)vj的的T標(biāo)號(hào)進(jìn)行如下的更改：標(biāo)號(hào)進(jìn)行如下的更改：T(vj)=minT(vj),P(vi)+wij (3)比較所有具有比較所有具有T標(biāo)號(hào)點(diǎn)，把最小者改為標(biāo)號(hào)點(diǎn)，把最小者改為P標(biāo)號(hào)，

17、即：標(biāo)號(hào)，即： P(vjo)=minT(vj) vj為為T(mén)標(biāo)號(hào)標(biāo)號(hào) 若全部點(diǎn)均為若全部點(diǎn)均為P標(biāo)號(hào)。則停止。否則以標(biāo)號(hào)。則停止。否則以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(

18、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)=v3 T(v7)=min+ ,5+5=10， k(v7)=v4（5） P(v6)=6 T(v5)=min10,6+2=8， k(v5)=v6 T(v7)=min10,6+1=7， k(v7)=v6 T(v8)=min+ ,6+9=15， k(v8)=v622v6v5v4v3v2v1v8v7356117423521695（6） P(v7)=7 T(v8)=min15,7+5=12， k(v8)=v7（7） P(v5)=8 T(v8)=min12,8+6=12， k(v8)=v7（8） P(v8)=12（9） 反向追蹤找最短路徑：反向追蹤找最短路徑：