圖論第三章的補(bǔ)充內(nèi)容ppt課件

1、 圖與網(wǎng)絡(luò)分析圖與網(wǎng)絡(luò)分析1. 圖的基本概念圖的基本概念2. 樹(shù)樹(shù) 2.1 樹(shù)與支撐樹(shù)樹(shù)與支撐樹(shù) 2.2 最小支撐樹(shù)問(wèn)題最小支撐樹(shù)問(wèn)題3. 最短路問(wèn)題最短路問(wèn)題4. 最大流問(wèn)題最大流問(wèn)題 第三章第三章 運(yùn)輸與配送管理運(yùn)輸與配送管理 補(bǔ)充內(nèi)容補(bǔ)充內(nèi)容1. 圖的基本概念圖的基本概念 圖圖: 由點(diǎn)和點(diǎn)與點(diǎn)由點(diǎn)和點(diǎn)與點(diǎn)之間的連線(xiàn)組成。若之間的連線(xiàn)組成。若點(diǎn)與點(diǎn)之間的連線(xiàn)沒(méi)點(diǎn)與點(diǎn)之間的連線(xiàn)沒(méi)有方向，稱(chēng)為邊，由有方向，稱(chēng)為邊，由此構(gòu)成的圖為無(wú)向圖。此構(gòu)成的圖為無(wú)向圖。 G=（V，E）端點(diǎn)端點(diǎn) 相鄰相鄰 關(guān)聯(lián)邊關(guān)聯(lián)邊 環(huán)環(huán) 多重邊多重邊 簡(jiǎn)單圖簡(jiǎn)單圖 多重圖多重圖次：一個(gè)點(diǎn)關(guān)聯(lián)的邊數(shù)稱(chēng)為該點(diǎn)的次。次：一個(gè)點(diǎn)

2、關(guān)聯(lián)的邊數(shù)稱(chēng)為該點(diǎn)的次。 鏈：是一個(gè)點(diǎn)、邊交錯(cuò)序列鏈：是一個(gè)點(diǎn)、邊交錯(cuò)序列, 如（如（ v1,e2,v2,e3,v4). 中間中間點(diǎn)點(diǎn)圈：鏈中，若起始點(diǎn)和終了點(diǎn)是同一個(gè)點(diǎn)，則稱(chēng)為圈。圈：鏈中，若起始點(diǎn)和終了點(diǎn)是同一個(gè)點(diǎn)，則稱(chēng)為圈。例如例如(v1,e2,v2, e3,v4,e4,v3,e1,v1)。度度 奇點(diǎn)奇點(diǎn) 偶點(diǎn)偶點(diǎn) 孤立點(diǎn)孤立點(diǎn)例例v1v2v3v4v5v6e2e4e5e6e7e8e1e3e9e10連通圖連通圖 不連通圖不連通圖 連通分圖連通分圖 支撐子圖支撐子圖 若點(diǎn)與點(diǎn)之間的連若點(diǎn)與點(diǎn)之間的連線(xiàn)有方向，稱(chēng)為弧，線(xiàn)有方向，稱(chēng)為弧，由此構(gòu)成的圖為有向由此構(gòu)成的圖為有向圖。圖。 D=（V，A

3、）基礎(chǔ)圖基礎(chǔ)圖 始點(diǎn)始點(diǎn) 終點(diǎn)終點(diǎn) 路路 回路回路v1v2v3v4v5v6e2e4e5e6e7e8e1e3v7v8e9e10v1v2v3v4v5v6e2e4e5e6e7e8e1e3例例例例樹(shù)：一個(gè)無(wú)圈的連通圖稱(chēng)為樹(shù)。樹(shù)圖樹(shù)：一個(gè)無(wú)圈的連通圖稱(chēng)為樹(shù)。樹(shù)圖G=（V,E的點(diǎn)數(shù)記為的點(diǎn)數(shù)記為p，邊數(shù)記為，邊數(shù)記為q，則，則q=p-1。例如例如 支撐樹(shù)：圖支撐樹(shù)：圖T=（V，E）是圖）是圖G=（V，E的支撐子圖，若圖的支撐子圖，若圖T是一個(gè)樹(shù)，則稱(chēng)是一個(gè)樹(shù)，則稱(chēng)T是是G的一的一個(gè)支撐樹(shù)。個(gè)支撐樹(shù)。2 . 樹(shù)樹(shù)2.1 樹(shù)與支撐樹(shù)樹(shù)與支撐樹(shù)例例 圖圖G有支撐樹(shù)，有支撐樹(shù)，當(dāng)且僅當(dāng)圖當(dāng)且僅當(dāng)圖G是連通是連通的

4、。求連通圖的支的。求連通圖的支撐樹(shù)的方法有撐樹(shù)的方法有“破破圈法和圈法和“避圈避圈法法”。v1v2v3v5e2e3e5e1e6e7e8破圈法破圈法v1v2e1v3e2e4e4v4v4v5e6避圈法避圈法v2e2e3e5e4v4v1v3v5e1e6e7e82 樹(shù)樹(shù)2.2 最小支撐樹(shù)問(wèn)題最小支撐樹(shù)問(wèn)題 給圖給圖G中的每一條邊中的每一條邊vi，vj一個(gè)相應(yīng)的一個(gè)相應(yīng)的數(shù)數(shù)ij，則稱(chēng)，則稱(chēng)G為賦權(quán)圖。在賦權(quán)圖為賦權(quán)圖。在賦權(quán)圖G的所有的所有支撐樹(shù)中，必有某個(gè)支撐樹(shù)，其所有邊的和支撐樹(shù)中，必有某個(gè)支撐樹(shù)，其所有邊的和為最小，稱(chēng)為最小樹(shù)。求賦權(quán)圖為最小，稱(chēng)為最小樹(shù)。求賦權(quán)圖G的最小支的最小支撐樹(shù)的方法也有

5、兩種撐樹(shù)的方法也有兩種,“破圈發(fā)和破圈發(fā)和“避圈避圈法法”。655172344v1v2v3v4v5v6 破圈法：任選一破圈法：任選一個(gè)圈，從圈中去掉權(quán)個(gè)圈，從圈中去掉權(quán)最大的一條邊。在余最大的一條邊。在余下的圖中重復(fù)這個(gè)步下的圖中重復(fù)這個(gè)步驟，直到得到一不含驟，直到得到一不含圈的圖為止。圈的圖為止。v3v21v42v53v641v2v3v4v5v6 避圈法：開(kāi)始選一條權(quán)最小的邊，避圈法：開(kāi)始選一條權(quán)最小的邊，以后每一步中，總從未被選取的邊中選以后每一步中，總從未被選取的邊中選一條權(quán)盡可能小，且與已選邊不構(gòu)成圈一條權(quán)盡可能小，且與已選邊不構(gòu)成圈的邊。的邊。3. 最短路問(wèn)

6、題最短路問(wèn)題 對(duì)于有向圖對(duì)于有向圖D D(V,A)(V,A)，給其每一個(gè)弧，給其每一個(gè)弧(vi,vj)(vi,vj)一一 個(gè)相應(yīng)的權(quán)值個(gè)相應(yīng)的權(quán)值wijwij，D D就成為賦權(quán)有向圖。給定賦權(quán)就成為賦權(quán)有向圖。給定賦權(quán)有向圖有向圖D D中的兩個(gè)頂點(diǎn)中的兩個(gè)頂點(diǎn)vsvs和和vtvt，設(shè)，設(shè)P P是由是由vsvs到到vtvt的一的一條路，把條路，把P P中所有弧的權(quán)之和稱(chēng)為路中所有弧的權(quán)之和稱(chēng)為路P P的權(quán)，記為的權(quán)，記為w(P)w(P)。如果路。如果路P P* *的權(quán)的權(quán)w(Pw(P* *) )是由是由vsvs到到vtvt的所有路的權(quán)的所有路的權(quán)中的最小者，則稱(chēng)中的最小者，則稱(chēng)P P* *是從是

7、從vsvs到到vtvt的最短路。最短路的最短路。最短路P P* *的權(quán)的權(quán)w(Pw(P* *) )稱(chēng)為從稱(chēng)為從vsvs到到vtvt的距離，記為的距離，記為d(vs,vt)d(vs,vt)。v1v2v3v4v5v6v7v8v9612231106410243263V 1V 2V 3V 4V 5V 6V 7V 8V 9-,0(v1,) (v1,) (v1,)(v1,1)v1,1(v1,6)(v1,6)(v1,3)(v1,) (v1,)(v4,11)(v1,) (v1,) (v1,)(v1,3)v1,3(v1,)(v1,)(v1,) (v1,)(v3,5)v3,5(v4,11)(v4,11)(v1,)

8、 (v1,)(v2,6)v2,6 (v1,)(v5,9)v5,9(v5,10)(v5,12) (v1,)(v5,10)v5,10(v5,12) (v1,) (v1,)(v5,12)v5,12(v1,) (v1,) v1,對(duì)無(wú)向圖，與此方法類(lèi)似。對(duì)無(wú)向圖，與此方法類(lèi)似。 在所有弧的權(quán)都非負(fù)在所有弧的權(quán)都非負(fù)的情況下，目前公認(rèn)最的情況下，目前公認(rèn)最好的求最短路的方法是好的求最短路的方法是Dijkstra標(biāo)號(hào)法。用實(shí)標(biāo)號(hào)法。用實(shí)例介紹如下：例介紹如下：例例 求上圖中求上圖中v1到到v8的最短路。的最短路。v1v2v3v4v5v6v7v8v9612231106410243263 最短路問(wèn)題是網(wǎng)絡(luò)理論中

9、應(yīng)用最廣泛的問(wèn)題之一。許多優(yōu)化問(wèn)題可以使用這個(gè)模型，如設(shè)備更新，管線(xiàn)鋪設(shè)，線(xiàn)路安排，廠(chǎng)區(qū)布局等。 最短路問(wèn)題的一般提法如下：設(shè)G(V，E)為連通圖，圖中各邊(Vi,Vj)有權(quán)l(xiāng)ijlij= ,表示Vi,Vj間無(wú)邊）， Vs,Vt為圖中任意兩點(diǎn)，求一條道路，使它是從Vs到Vt 的所有路中總權(quán)最小的路。即： L ()=min 有些最短路問(wèn)題也可以是求網(wǎng)絡(luò)中某指定點(diǎn)到其余所有結(jié)點(diǎn)的最短路，或求網(wǎng)絡(luò)中任意兩點(diǎn)間的最短路。v ,(vlj)iijDijkstra算法：算法思路：若序列算法思路：若序列Vs ,V1,V2,Vn-1,Vn是是Vs到到Vn的最短路，則序列的最短路，則序列Vs ,V1,V2,Vn-

10、1也是也是Vs到到Vn-1的最短路。的最短路。標(biāo)號(hào)法步驟：標(biāo)號(hào)法步驟： TTentative Label試探性標(biāo)號(hào)，試探性標(biāo)號(hào)，PPermanent Label ）永）永久性標(biāo)號(hào)，給久性標(biāo)號(hào)，給V i點(diǎn)一個(gè)點(diǎn)一個(gè)P標(biāo)號(hào)時(shí)，表示從標(biāo)號(hào)時(shí)，表示從Vs到到V i點(diǎn)的最短路權(quán)，點(diǎn)的最短路權(quán)， V i點(diǎn)的標(biāo)號(hào)點(diǎn)的標(biāo)號(hào)不再改變，給不再改變，給V i點(diǎn)一個(gè)點(diǎn)一個(gè)T標(biāo)號(hào)時(shí)，表示從標(biāo)號(hào)時(shí)，表示從Vs到到V i點(diǎn)的估計(jì)最短路權(quán)的上界，點(diǎn)的估計(jì)最短路權(quán)的上界，算法每一步都把某點(diǎn)的算法每一步都把某點(diǎn)的T標(biāo)號(hào)變?yōu)闃?biāo)號(hào)變?yōu)镻標(biāo)號(hào)，當(dāng)終點(diǎn)標(biāo)號(hào)，當(dāng)終點(diǎn) Vt得到得到P標(biāo)號(hào)時(shí)，全部計(jì)算標(biāo)號(hào)時(shí)，全部計(jì)算結(jié)束。結(jié)束。n個(gè)頂點(diǎn)得圖，

11、最多個(gè)頂點(diǎn)得圖，最多n-1步就可以算出從始點(diǎn)到終點(diǎn)得最短路。步就可以算出從始點(diǎn)到終點(diǎn)得最短路。Step 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)， TVi）+ Step 2: 若若Vi: (Vi, Vj)屬于屬于E，且，且Vj為為T(mén)標(biāo)號(hào)，對(duì)標(biāo)號(hào)，對(duì)Vj 的的T標(biāo)號(hào)更改：標(biāo)號(hào)更改： TVj）min TVj） ,P （Vi）+lijStep 3: 比較所有具有比較所有具有T標(biāo)號(hào)的點(diǎn)，把最小的改為標(biāo)號(hào)的點(diǎn)，把最小的改為P標(biāo)號(hào)，即：標(biāo)號(hào)，即： PVi）min TVi）, 當(dāng)有當(dāng)有2個(gè)以上最小者時(shí)，可同時(shí)改為個(gè)以上最小者時(shí)，可同時(shí)改為P標(biāo)號(hào)，若全部點(diǎn)均為標(biāo)

12、號(hào)，若全部點(diǎn)均為P標(biāo)號(hào)則標(biāo)號(hào)則終止。否則用終止。否則用Vi代替代替Vi轉(zhuǎn)回轉(zhuǎn)回Step 2。v1v4v2v6v8v7v5v346594157445761.首先給V1以P標(biāo)號(hào)， P （V1）0給其余點(diǎn)T標(biāo)號(hào)， TVi）+ （i=2,3,8）2. 由于V1， V2 ）， （V2， V3 ）邊屬于E，且V2， V3為T(mén)標(biāo)號(hào)，所 以修正2個(gè)點(diǎn)標(biāo)號(hào)： TV2）min TV2） , PV1）+l12 min + , 0+4 = 4 TV3）min TV3） , P （V3）+l13 min + , 0+6 = 63. 比較所有T標(biāo)號(hào)， TV2最小，故令P （V2）44. V2 為剛得到P標(biāo)號(hào)的點(diǎn)，考察邊V

13、2， V4 ）， （V2， V5 ）的端點(diǎn)V4 ，V5： TV4）min TV4） , PV2）+l24 min + , 4+5 = 9 TV5）min TV5） , P （V2）+l25 min + , 4+4 = 85. 比較所有T標(biāo)號(hào)， TV3最小，故令P （V3）86. 考察點(diǎn)V3，有： TV4）min TV4） , PV3）+l34 min 9, 6+4 = 9 TV5）min TV5） , P （V3）+l35 min 8, 6+7 = 87. 比較所有T標(biāo)號(hào)， TV5最小，故令P （V5）88. 考察點(diǎn)V3： TV6）min TV6） , PV5）+l56 min + , 8+5

14、 = 13 TV7）min TV7） , P （V5）+l57 min + ,8+6 = 149. 比較所有T標(biāo)號(hào)， TV4最小，故令P （V4）910.考察點(diǎn)V4： TV6）min TV6） , PV4）+l46 min 13, 9+9 = 13 TV7）min TV7） , P （V4）+l47 min 14,9+7 = 1411.比較所有T標(biāo)號(hào)， TV6最小，故令P （V6）1312.考察點(diǎn)V6： TV7）min TV7） , PV6）+l67 min 14, 13+5 = 14 TV8）min TV8） , P （V6）+l68 min + ,13+4 = 1713.比較所有T標(biāo)號(hào)，

15、TV7最小，故令P （V7）1414.考察點(diǎn)V7： TV8）min TV8） , P （V7）+l78 min 17,14+1 = 1515.因?yàn)橹挥幸粋€(gè)T標(biāo)號(hào)TV8），令PV8）15，計(jì)算結(jié)束。 V1到V8的最短路為V1 V2 V5 V7 V8，路長(zhǎng)PV8）15，同時(shí)得到V1到其余各點(diǎn)的最短路Floyd-Warshall算法：求網(wǎng)絡(luò)中任意兩點(diǎn)間的最短路：令網(wǎng)絡(luò)的權(quán)距陣為D=（dijnn，lij為Vi到Vj的距離，其中： lij ，當(dāng)（ Vi ， Vj ）E , 其它算法步驟： step1：輸入D0）= D；step2 ：計(jì)算Dk）= （dij(k)）nn , (k=1,2,3,n); 其中：

16、 dij(k)=mindi(k-1), dik(k-1)+dkj(k-1) Step3： Dn）= （dij(n)）nn中 元素dij(n)就是Vi 到 Vj的最短路長(zhǎng)。 0 5 1 2 0 5 1 2 5 0 10 2 5 0 6 7 2 D= D(0)= 2 3 0 2 8 D(1)= 2 3 0 2 8 2 6 0 4 2 7 3 0 4 2 4 4 0 2 4 4 0 0 5 1 2 7 0 4 1 2 6 0 4 1 2 6 0 4 1 2 6 5 0 6 7 2 5 0 6 7 2 5 0 6 7 2 5 0 6 6 2 D(2)= 2 3 0 2 5 D(3)= 2 3 0 2

17、5 D(4)= 2 3 0 2 5 D(5)= 2 3 0 2 5 2 7 3 0 4 2 6 3 0 4 2 6 3 0 4 2 6 3 0 4 7 2 4 4 0 6 2 4 4 0 2 3 0 4 0 6 2 4 4 0dijv3v1v2v5v45242126284310v1v2v3v4v5v1 v2 v3 v4 v5v1v2v3v4v5v1 v2 v3 v4 v5d23(1)=min d23(0), d21(0)+ d130)= min10,5+1=6由于dij(1)=mindij(0), di1(0)+d1j(0) 表示從Vi到Vj或直接有邊或借V1為中間點(diǎn)時(shí)的最短路長(zhǎng)。紅字元素為更

18、新的元素。dij(2)與dij(3)表示從Vi到Vj最多經(jīng)中間點(diǎn)V1，V2與V1，V2 ， V3的最短路長(zhǎng)因dij(5)表示從Vi到Vj最多經(jīng)中間點(diǎn)V1,V2V5的所有路中的最短路長(zhǎng)。故D(5就給出了2點(diǎn)間不論幾步到達(dá)的最短路長(zhǎng) 給一個(gè)有向圖D(V,A)，指定兩個(gè)點(diǎn)，一個(gè)點(diǎn)稱(chēng)為發(fā)點(diǎn)，記為vs，另一個(gè)點(diǎn)稱(chēng)為收點(diǎn)，記為vt，其余點(diǎn)稱(chēng)為中間點(diǎn)。4. 最大流問(wèn)題最大流問(wèn)題4.1基本概念和定理基本概念和定理3511 42352vsv2v1v3v4vt 對(duì)于D中的每一個(gè)弧(vi,vj)，相應(yīng)地給一個(gè)數(shù)cijcij0），稱(chēng)為弧(vi,vj)的容量。我們把這樣的D稱(chēng)為網(wǎng)絡(luò)或容量網(wǎng)絡(luò)），記為D(V,A,C)。

19、所謂網(wǎng)絡(luò)上的流，是指定義在弧集A上的函數(shù)ff(vi,vj)，并稱(chēng)f(vi,vj)為弧(vi,vj)上的流量，簡(jiǎn)記為fij?？尚辛鳌⒖尚辛鞯牧髁?、最大流。3,15,21,01,0 4,12,23,15,22,1vsv2v1v3v4vt 給定容量網(wǎng)絡(luò)D(V,A,C)，若點(diǎn)集V被剖分為兩個(gè)非空集合V1和V2，使 vsV1 ，vtV2，則把弧集(V1,V2)稱(chēng)為分離vs和vt的截集。 顯然，若把某一截集的弧從網(wǎng)絡(luò)中去掉，則從vs到vt便不存在路。所以，直觀上說(shuō)，截集是從vs到vt的必經(jīng)之路。3511 42352vsv2v1v3v4vt 截集的容量(簡(jiǎn)稱(chēng)截量) 最小截集 對(duì)于可行流ffij，我們把網(wǎng)絡(luò)中

20、使fijcij的弧稱(chēng)為飽和弧，使fij0的弧稱(chēng)為非零流弧。 設(shè)f是一個(gè)可行流，是從vs到vt的一條鏈，若滿(mǎn)足前向弧都是非飽和弧,后向弧都是都是非零流弧,則稱(chēng)是可行流f的一條增廣鏈。3,15,21,01,0 4,12,23,15,22,1vsv2v1v3v4vt 若是聯(lián)結(jié)發(fā)點(diǎn)vs和收點(diǎn)vt的一條鏈，我們規(guī)定鏈的方向是從vs到vt，則鏈上的弧被分成兩類(lèi)：前向弧、后向弧。 對(duì)最大流問(wèn)題有下列定理： 定理1 可行流f*fij*是最大流，當(dāng)且僅當(dāng)D中不存在關(guān)于f*的增廣鏈。 定理2最大流最小截定理任一網(wǎng)絡(luò)中，最大流的流量等于最小截集的截量。4. 最大流問(wèn)題最大流問(wèn)題4.2 求最大流的標(biāo)號(hào)法求最大流的標(biāo)號(hào)法 標(biāo)號(hào)法思想是：先找一個(gè)可行流。標(biāo)號(hào)法思想是：先找一個(gè)可行流。對(duì)于一個(gè)可行流，經(jīng)過(guò)標(biāo)號(hào)過(guò)程得到對(duì)于一個(gè)可行流，經(jīng)過(guò)標(biāo)號(hào)過(guò)程得到從發(fā)點(diǎn)從發(fā)點(diǎn)vsvs到收點(diǎn)到收點(diǎn)vtvt的增廣鏈；經(jīng)過(guò)調(diào)的增廣鏈；經(jīng)過(guò)調(diào)整過(guò)程沿增廣鏈增加可行流的流量，整過(guò)程沿增廣鏈增加可行流的流量，得新的可行流。重復(fù)這一過(guò)程，直到得新的可行流。重復(fù)這一過(guò)程，直到可行流無(wú)增廣鏈，得到最大流?？尚辛鳠o(wú)增廣鏈，得到最大流。 標(biāo)號(hào)過(guò)程: (1)給vs標(biāo)號(hào)