《離散數(shù)學(xué)課件》1-2圖的基本概念摘要

1、1/81離散數(shù)學(xué)集 合 論數(shù)理邏輯圖論代數(shù)2/81一個(gè)人要把他帶的一條狗，一只羊和一袋菜用一條小船擺渡到河的對(duì)岸。每次擺渡這個(gè)人只能將狗、羊和菜之一帶過(guò)去。但是，不能把狗和羊，也不能把羊和菜單獨(dú)的留在河的同一岸。V=被允許出現(xiàn)的局面E=頂點(diǎn)之間的關(guān)系|一次擺渡能夠從一局面變?yōu)榱硪痪置?/819.1 圖的根本概念(一) 有向圖(二) 無(wú)向圖(三) 圖的同構(gòu)(四) 完全圖(五) 握手定理頂點(diǎn)集、邊集多重邊、自環(huán)、孤立點(diǎn)簡(jiǎn)單圖/多重圖圖的同構(gòu)映射子圖、生成子圖、補(bǔ)圖 有向完全圖頂點(diǎn)的度數(shù)入度、出度有向圖 G=(V,E)定義1 設(shè)V是一個(gè)非空有限集合， E是V上的二元關(guān)系。 那么稱(chēng)有序二元組G=(V,

2、E)是一個(gè)有向圖， 并稱(chēng)V 為頂點(diǎn)集， E為邊集。 其中，邊集E為有序二元組所構(gòu)成的集合。 5/81例 設(shè)V=2，3，4，5，6 ，E=(x, y)|x整除y, 即 E= (2,2), (2,4), (2,6), (3,3), (3,6), (4,4), (5,5), (6,6) 畫(huà)出有向圖G=(V,E)246356/81有向圖G=(V,E): 邊、孤立點(diǎn)、自環(huán)假設(shè)(a,b) E，稱(chēng)(a,b)為圖G中一條邊。設(shè)(a,b) E，稱(chēng)邊(a,b)關(guān)聯(lián)于頂點(diǎn)a和b，頂點(diǎn)a稱(chēng)為該邊的始點(diǎn)，頂點(diǎn)b稱(chēng)為該邊的終點(diǎn)，并稱(chēng)a和b相鄰。假設(shè)一個(gè)頂點(diǎn)沒(méi)有任何邊關(guān)聯(lián)于它，稱(chēng)該頂點(diǎn)為孤立點(diǎn)。假設(shè)一條邊的始點(diǎn)和終點(diǎn)是同一

3、頂點(diǎn)，稱(chēng)該邊為自環(huán)。246357/81多重集 約定一個(gè)多重集是一些對(duì)象的總體，但這些對(duì)象不必不同。如: a, a, a, b, b, c a, a, a a, b, c 一個(gè)元素的重?cái)?shù)是它在該多重集里出現(xiàn)的次數(shù)集合僅是多重集中重?cái)?shù)僅為0和1的特殊情況8/81無(wú)向圖G=(V,E)定義2 設(shè)V是一個(gè)非空有限集合， E是一個(gè)多重集合， E的元素是僅含V中兩個(gè)元素的多重子集。 那么稱(chēng)二元組G=(V,E)是一個(gè)無(wú)向圖，例1(p136) 圖G=(V,E)， V=v1, v2, v3, v4, v5， E= v1,v2,v2,v3, v3,v3,v3,v4, v2,v4,v4,v5, v2,v5,v2,v5

4、 9/81無(wú)向圖G=(V,E) : 邊、自環(huán)、孤立點(diǎn)v,u E, 稱(chēng)v,u是G中一條邊。稱(chēng)V為頂點(diǎn)集， 稱(chēng)E為邊集。設(shè)e=v,u 是G中的一條邊， v和u稱(chēng)為邊e 的二個(gè)端點(diǎn)，稱(chēng)邊 e關(guān)聯(lián) v和u，也稱(chēng)v 鄰接到u，或 u鄰接于v。假設(shè)u=v，稱(chēng)v,u 為G中的自環(huán)。對(duì)于任意的u V ，假設(shè)不存在任何邊關(guān)聯(lián)u，說(shuō)頂點(diǎn)u是孤立點(diǎn)。邊和點(diǎn)：關(guān)聯(lián)點(diǎn)和點(diǎn)：相鄰邊和邊：相鄰10/81多重圖、簡(jiǎn)單圖一個(gè)圖，有向圖或無(wú)向圖，其邊集假設(shè)是多重集，稱(chēng)這樣的圖為多重圖，也簡(jiǎn)稱(chēng)圖。假設(shè)一個(gè)圖，也就是多重圖，其重?cái)?shù)大于1的邊稱(chēng)為多重邊，又稱(chēng)有這樣邊的圖為有多重邊的圖。稱(chēng)一個(gè)沒(méi)有多重邊，沒(méi)有自環(huán)，也沒(méi)有孤立點(diǎn)的圖為簡(jiǎn)單

5、圖。假設(shè)不聲明是簡(jiǎn)單圖，就泛指圖或多重圖。11/81圖的畫(huà)法不同、實(shí)質(zhì)相同12/81圖的畫(huà)法不同、實(shí)質(zhì)相同13/81圖的同構(gòu) G1G2定義3 設(shè)G1=(V1,E1)和G2=(V2,E2)是兩個(gè)圖， 假設(shè)存在函數(shù)f:V1V2，f是雙射， 且假設(shè)定義函數(shù)g:E1E2， 對(duì)于任意的v1,v1 E1， g(v1,v1)=f(v1),f(v1)， g也是一個(gè)雙射。 那么稱(chēng)圖G1和圖G2是同構(gòu)的兩個(gè)圖，記為 G1G2， 并稱(chēng)f為圖的同構(gòu)映射，。14/81完全圖 Kn一個(gè)簡(jiǎn)單圖，假設(shè)每一對(duì)不同的頂點(diǎn)之間都有一條邊相連，這樣的圖稱(chēng)為完全圖。一個(gè)有n(N)個(gè)頂點(diǎn)的完全圖在同構(gòu)的意義下是唯一的，記為Kn。15/8

6、1子圖、真子圖、生成子圖定義4 設(shè)G=(V,E), H=(V,E)是兩個(gè)圖。 假設(shè)V V且E E，那么說(shuō) H是G的子圖。 假設(shè)V V或E E，那么說(shuō) H是G的真子圖。 假設(shè)H是G的子圖且V=V，說(shuō)H是G的生成子圖。K4的真子圖K4的生成子圖例:K416/81例 K4的所有的生成子圖有多少？ 64個(gè)！17/81例 K4所有互不同構(gòu)的生成子圖有多少？11個(gè)！18/81補(bǔ)圖設(shè)G=(V,E)是一個(gè)圖，它沒(méi)有自環(huán)和多重邊。令 =(V,E)，其中 E= u,v uv，u,vV，u,v E稱(chēng) 為 G的補(bǔ)圖。GG例 下面兩圖互為補(bǔ)圖：19/81自互補(bǔ)圖一個(gè)無(wú)向簡(jiǎn)單圖如果同構(gòu)于它的補(bǔ)圖，那么稱(chēng)這個(gè)圖為自互補(bǔ)圖。

7、例 4個(gè)頂點(diǎn)的自互補(bǔ)圖：20/81例 試畫(huà)出五個(gè)頂點(diǎn)的自互補(bǔ)圖21/81頂點(diǎn)的度數(shù)設(shè)G=(V,E)是一個(gè)圖，對(duì)于每一個(gè)vV，稱(chēng)關(guān)聯(lián)頂點(diǎn)v的邊數(shù)為頂點(diǎn)v的度數(shù)，記為d(v)。23322/81定理1 (握手定理)設(shè)G=(V,E)是一個(gè)圖，對(duì)于每一個(gè)vV， d(v)為頂點(diǎn)v的度數(shù)。那么: d(v) = 2|E|vV23323/81推論 任何一個(gè)無(wú)向圖，度數(shù)為奇數(shù)的頂點(diǎn)有偶數(shù)個(gè)。證明：設(shè) G=(V,E)是一個(gè)無(wú)向圖。令 V1= vVd(v)是奇數(shù)， V2= vVd(v)是偶數(shù)， 顯然V1， V2 是V的一個(gè)劃分。 d(v)vV1 d(v)=vV d(v)vV2+ d(v)vV d(v)=vV1 d(v

8、)vV2容易說(shuō)明，等式右端是偶數(shù)，而等式左端是|V1|個(gè)奇數(shù)相加，故|V1|為偶數(shù)。24/81例2 有9個(gè)人在一起打乒乓球，已知他們每人至少和其中另外3個(gè)人各打過(guò)一場(chǎng)球，則一定有一個(gè)人不止和3個(gè)人打過(guò)球。用圖論語(yǔ)言解釋這件事。解：設(shè)v1，v2，v9代表這9個(gè)人，建立頂點(diǎn)集 V=v1，v2，v9， 對(duì)于其中的任意兩個(gè)人vi和 vjij，假設(shè)vi和vj打過(guò)一場(chǎng)球，那么 vi,vj E，得到邊集E，那么我們有了一個(gè)無(wú)向圖G=V，E。 假設(shè)每一個(gè)人僅和其余3個(gè)人各打過(guò)一場(chǎng)球，那么 d(vi)=3，而此時(shí)圖G的奇數(shù)度的頂點(diǎn)是9個(gè)，即是奇數(shù)個(gè)，與推論矛盾。矛盾說(shuō)明，至少有一個(gè)人vi，d(vi) 4。25/

9、81例 (3,3,2,3)與(5,2,3,1,4)能成為圖的度數(shù)序列嗎? 為什么?解: 不能，因?yàn)槎葦?shù)為奇數(shù)的頂點(diǎn)數(shù)目不是偶數(shù)。26/81例 已知圖G中有10條邊, 4個(gè)3度頂點(diǎn),其余頂點(diǎn)的度數(shù)均小于等于2, 問(wèn)G中至少有多少個(gè)頂點(diǎn)?為什么?解: 圖G中頂點(diǎn)度數(shù)之和為 210=20， 而已有4個(gè)頂點(diǎn)的度數(shù)之和為43=12，還剩下8度， 按題意，還需至少4個(gè)頂點(diǎn)， 所以圖G至少有8個(gè)頂點(diǎn)。27/81例3(p138) 兩無(wú)向圖是否同構(gòu)？ a b c d egf1 2 3 4 567答：圖a中兩個(gè)3度頂點(diǎn)之間沒(méi)有邊，而圖b中兩個(gè)3度頂點(diǎn)之間有邊，故不存在兩圖之間的同構(gòu)映射。ab28/81同構(gòu)圖的頂點(diǎn)

10、度設(shè)G1=(V1,E1)和G2=(V2,E2)同構(gòu)，即存在同構(gòu)映射f:V1V2，那么對(duì)于任意的viV1，一定有 d(vi)=d(f(vi) 任意兩個(gè)同構(gòu)的無(wú)向圖，一定有一個(gè)同樣的頂點(diǎn)度序列。頂點(diǎn)度序列是一組按大小排列的正整數(shù)，每一個(gè)數(shù)對(duì)應(yīng)某一個(gè)頂點(diǎn)的度數(shù)。29/81例 考察兩個(gè)不同構(gòu)的簡(jiǎn)單無(wú)向圖。每一個(gè)圖都僅有6個(gè)頂點(diǎn)，且每個(gè)頂點(diǎn)都均是3度，并指出這兩個(gè)圖為什么不同構(gòu)。反證法： 假使兩圖同構(gòu)。 不妨假設(shè)紅點(diǎn)對(duì)應(yīng)紅點(diǎn),那么3個(gè)綠點(diǎn)對(duì)應(yīng)3個(gè)綠點(diǎn), 剩下的2個(gè)藍(lán)點(diǎn)對(duì)應(yīng)2個(gè)藍(lán)點(diǎn)，而在左圖中2個(gè)藍(lán)點(diǎn)間無(wú)邊，而在右圖中2個(gè)藍(lán)點(diǎn)間有邊。矛盾！30/81有向完全圖如果一個(gè)有向圖去掉邊的方向以后所得無(wú)向圖是完全

11、圖，那么稱(chēng)為有向完全圖。31/81出度、入度定義5 設(shè)G=(V,E)是一個(gè)有向圖， vV ， 稱(chēng)以v為始點(diǎn)的邊的條數(shù)為v的出度， 記為 d出(v)或d+(v)； 稱(chēng)以v為終點(diǎn)的邊的條數(shù)為v的入度，記為 d入(v)或d(v)。32/81定理2 d出(v) = d入(v)=|E|vVvV設(shè)G=(V,E)是一個(gè)有向圖，那么 33/81小結(jié) 圖的根本概念(一) 有向圖(二) 無(wú)向圖(三) 圖的同構(gòu)(四) 完全圖(五) 握手定理頂點(diǎn)集、邊集多重邊、自環(huán)、孤立點(diǎn)簡(jiǎn)單圖/多重圖圖的同構(gòu)映射子圖、生成子圖、補(bǔ)圖 有向完全圖頂點(diǎn)的度數(shù)入度、出度34/819.2 圖中的通路、圖的連通性和圖的矩陣表示 (一) 通路

12、(二) 簡(jiǎn)單通路、初等通路(三) 簡(jiǎn)單回路、初等回路(四) 連通圖(五) 單側(cè)連通、強(qiáng)連通(六) 關(guān)聯(lián)矩陣、鄰接矩陣、可達(dá)矩陣35/81通路: 頂點(diǎn)序列稱(chēng)頂點(diǎn)序列(vi1，vi2，vis)為圖G中的一條通路，假設(shè)vijV，1js，且(vij, vi(j+1) E，其中 1js-1。例 (v1, v2, v3)為通路 (v1,v3,v4,v6,v7)為通路36/81通路: 邊序列稱(chēng)邊序列 (ei1，ei2，eit) 為圖G中的一條通路，假設(shè)eijE，1jt，且適當(dāng)?shù)囊?guī)定邊eij(1jt)中的兩個(gè)端點(diǎn)，讓其中一個(gè)為起點(diǎn)，一個(gè)為終點(diǎn)，可以使eij的終點(diǎn)與ei(j+1)的起點(diǎn)是同一頂點(diǎn)，其中1jt-1

13、。例 (e2, e3)為通路 (e1,e5,e8,e12)為通路37/81通路的長(zhǎng)度、頂點(diǎn)間的距離稱(chēng)一條通路經(jīng)過(guò)的邊的多少為這條通路的長(zhǎng)度。稱(chēng)兩個(gè)頂點(diǎn)間的最短通路的長(zhǎng)度為該兩個(gè)頂點(diǎn)間的距離。例 (v1,v2,v3)為通路，長(zhǎng)度為2。 (v1,v3,v4,v6,v7)為通路, 長(zhǎng)度為4。38/81簡(jiǎn)單通路、初等通路稱(chēng)一條通路為簡(jiǎn)單通路, 如果它的每一條邊都不重復(fù)出現(xiàn)。稱(chēng)一條通路為初等通路, 如果它的每一個(gè)頂點(diǎn)都不重復(fù)出現(xiàn).例 (v1,v2,v5,v6,v4,v6,v8,v7)為簡(jiǎn)單通路,但非初等通路.39/81回路、簡(jiǎn)單回路、初等回路圈設(shè)(vi1，vi2，vis)是圖G=(V,E)中的一條通路，

14、假設(shè)vi1=vis，那么這條通路為G中的一條回路。假設(shè)一個(gè)回路中邊不重復(fù)出現(xiàn)，那么稱(chēng)之為簡(jiǎn)單回路。假設(shè)一個(gè)回路中頂點(diǎn)不重復(fù)出現(xiàn)，那么稱(chēng)之為初等回路，又稱(chēng)之為圈。40/81例 回路、簡(jiǎn)單回路、初等回路圈 (v2,v4,v5,v6,v4,v3,v2)為一個(gè)簡(jiǎn)單回路，但不是圈41/81定理1G=(V,E)是一個(gè)無(wú)向圖。v1，v2V，假設(shè)G中存在一條v1 到v2的通路，那么一定存在一條從v1到v2的初等通路。42/81定理1的證明設(shè) S=nNG中存在一條長(zhǎng)為n的從v1 到v2的通路 由題知S，又SN，由自然數(shù)集的非空子集有最小數(shù)，可設(shè)mS，對(duì)于任意nS，有 m n。設(shè)(v1=vi0，vi1，vi(m-

15、1)，v2=vim)是G中一條從v1到v2長(zhǎng)度為m的通路，那么這條通路即是初等通路。否那么，假設(shè)它不是初等通路，一定存在兩個(gè)相同的頂點(diǎn)vij和vik(0jkm)，使得vij=vik。于是 (vi0，vij ，vi(k+1)， ，vim)也是 中一條從v1到v2的通路，且長(zhǎng)度為m-k+j (m)，這與m最小矛盾。43/81推論G=(V,E)是一個(gè)無(wú)向圖， |V|=n。如果G中存在一條從v1到v2的通路，那么一定存在一條從v1到v2的長(zhǎng)度小于等于n-1的通路。恰有 n個(gè)頂點(diǎn)的圖G 中的初等通路最長(zhǎng)為n-1。44/81連通圖定義 G=(V,E)是一個(gè)無(wú)向圖，假設(shè)G中任意兩個(gè)不同的頂點(diǎn)之間在G中都有通

16、路存在， 那么稱(chēng)G是一個(gè)連通圖，否那么稱(chēng)G為不連通圖。45/81有向連通圖定義 稱(chēng)一個(gè)有向圖是連通的，如果去掉邊的方向后所得無(wú)向圖是連通的。46/81單側(cè)連通一個(gè)有向圖任意二點(diǎn)之間都有單向通路，那么稱(chēng)為單側(cè)連通圖。例連通、非單側(cè)連通單側(cè)連通47/81強(qiáng)連通如果一個(gè)有向圖任意二點(diǎn)之間都有雙向的通路，那么稱(chēng)為強(qiáng)連通圖。例單側(cè)連通非強(qiáng)連通強(qiáng)連通連通性判別定理(強(qiáng)連通判別法) D強(qiáng)連通當(dāng)且僅當(dāng)D中存在經(jīng)過(guò)每個(gè)頂點(diǎn)至少一次的回路定理(單向連通判別法) D單向連通當(dāng)且僅當(dāng)D中存在經(jīng)過(guò)每個(gè)頂點(diǎn)至少一次的通路 48(1)(2)(3)例 下圖(1)強(qiáng)連通, (2)單連通, (3) 弱連通49/81連通分支設(shè)G為

17、一個(gè)無(wú)向圖,R是G中頂點(diǎn)之間的連通關(guān)系,按著R可將V(G)劃分成k(k1)個(gè)等價(jià)類(lèi),記成V1,V2,Vk,稱(chēng)由它們導(dǎo)出的子圖GV1,GV2,GVk 為G的連通分支。其個(gè)數(shù)記作p(G)=k.50/81例 連通分支連通分支數(shù)為1 連通分支數(shù)為451點(diǎn)割集 記 Gv: 從G中刪除v及關(guān)聯(lián)的邊 GV: 從G中刪除V中所有的頂點(diǎn)及關(guān)聯(lián)的邊 Ge : 從G中刪除e GE: 從G中刪除E中所有邊定義 設(shè)無(wú)向圖G=, VV, 假設(shè)p(GV)p(G)且VV, p(GV)=p(G), 那么稱(chēng)V為G的點(diǎn)割集. 假設(shè)v為點(diǎn)割集, 那么稱(chēng)v為割點(diǎn).52點(diǎn)割集(續(xù))例 v1,v4, v6是點(diǎn)割集, v6是割點(diǎn). v2,v

18、5是點(diǎn)割集嗎？ 53邊割集定義 設(shè)無(wú)向圖G=, EE, 假設(shè)p(GE)p(G)且EE, p(GE)=p(G), 那么稱(chēng)E為G的邊割集. 假設(shè)e為邊割集, 那么稱(chēng)e為割邊或橋.圖中，e1,e2，e1,e3,e5,e6，e8等是邊割集，e8是橋，e7,e9,e5,e6是邊割集嗎？54/81例 G=(V,E)是一個(gè)簡(jiǎn)單圖，試證明若G不連通，則 G的補(bǔ)圖 G 一定連通。證明：因?yàn)镚不連通，那么G可以分為假設(shè)干連通子圖： V1，E1，- ，Vn，En 根據(jù)補(bǔ)圖構(gòu)造過(guò)程知，在G的補(bǔ)圖中， V1中每個(gè)頂點(diǎn)與其它頂點(diǎn)集V2，- ，Vn中頂點(diǎn)有邊相連。 這樣， 在G的補(bǔ)圖中，有分別屬于兩個(gè)頂點(diǎn)子集Vi與Vj中的

19、任意兩個(gè)頂點(diǎn)之間有邊直接相連，屬于同一個(gè)頂點(diǎn)子集Vi的任意兩個(gè)頂點(diǎn)借助頂點(diǎn)子集Vj的任意一個(gè)頂點(diǎn)連通。所以，根據(jù)連通的定義知：G的補(bǔ)圖一定連通 。圖的矩陣表示 關(guān)聯(lián)矩陣無(wú)向圖、有向圖鄰接矩陣無(wú)向圖、有向圖有向圖的可達(dá)矩陣 5556/81無(wú)向圖的關(guān)聯(lián)矩陣設(shè) G=(V,E)是一個(gè)無(wú)向圖，|V|=n，|E|=m，V=v1,v2, ,vn，E=e1,e2, ,em，那么有nm 階矩陣 ， M(G)=(mij)nm其中: 稱(chēng) M(G)=(mij)nm為圖G的關(guān)聯(lián)矩陣。mij=1 如頂點(diǎn)vi與邊ei關(guān)聯(lián)0 如頂點(diǎn)vi與邊ei關(guān)聯(lián)57/81例 e1 e2 e3 e4 e5 e6 e7 e8 v1 1 1 1

20、 0 1 0 0 0 v2 1 0 0 1 0 0 0 0 v3 0 0 1 1 0 0 1 1v4 0 0 0 0 1 1 0 1v5 0 1 0 0 0 1 1 0 M(G)=特點(diǎn)：1、行和為度數(shù)2、列和為23、所有元素的和為總 度數(shù)4、平行邊列相同有向圖的關(guān)聯(lián)矩陣58定義 設(shè)無(wú)環(huán)有向圖D=, V=v1, v2, , vn, E=e1, e2, , em, 令 則稱(chēng)(mij)nm為D的關(guān)聯(lián)矩陣，記為M(D).59例：寫(xiě)出以下圖的關(guān)聯(lián)矩陣60有向圖的關(guān)聯(lián)矩陣性質(zhì) (4) 平行邊對(duì)應(yīng)的列相同61/81鄰接矩陣 (adjacency matrix) 設(shè) G=(V,E)是一個(gè)無(wú)向圖，|V|=n，

21、V=v1,v2, ,vn，那么有nn 階矩陣， A(G)=(aij)nn其中: 稱(chēng) A(G)=(aij)nn為圖G的鄰接矩陣。aij=1 vi,vj E0 vi,vj E62/81例 鄰接矩陣 v1 v2 v3 v4 v5v1 0 1 1 1 1v2 1 0 1 0 1v3 1 1 0 1 1v4 1 0 1 0 1v5 1 0 1 1 0 A(G)=63定義 設(shè)有向圖D=, V=v1, v2, , vn, E=e1, e2, , em, 令 為頂點(diǎn)vi鄰接到頂點(diǎn)vj邊的條數(shù)，稱(chēng)( )mn為D的鄰接矩陣, 記作A(D), 簡(jiǎn)記為A. 有向圖的鄰接矩陣補(bǔ) 64例 鄰接矩陣性質(zhì)65/81定理2設(shè)圖

22、G=(V,E) ，其中V=v1,v2, ,vn。A是 G的鄰接矩陣。對(duì)于任意的自然數(shù)k，設(shè)矩陣Ak的第i行第j列的元素為aij(k)，即 Ak=(aij(k)nn那么aij(k) 給出了所有的從vi到vj的長(zhǎng)度為k的通路的條數(shù)。假設(shè) aij(k)=0，說(shuō)明沒(méi)有vi到vj的長(zhǎng)度為k的通路。66/81例 有向圖D如下圖, 求A, A2, A3, A4, 并答復(fù)諸問(wèn)題：D中長(zhǎng)度為1, 2, 3, 4的通路各有多少條？ 其中回路分別為多少條？(2) D中長(zhǎng)度小于或等于4的通路為多少條？ 其中有多少條回路？ 長(zhǎng)度 通路 回路 67合計(jì) 50 818 1211 3314 1417 368/81有向圖的可達(dá)

23、矩陣定義 設(shè)D=為有向圖, V=v1, v2, , vn, 令 稱(chēng)(pij)nn為D的可達(dá)矩陣, 記作P(D), 簡(jiǎn)記為P. 性質(zhì): P(D)主對(duì)角線(xiàn)上的元素全為1. D強(qiáng)連通當(dāng)且僅當(dāng)P(D)的元素全為1.69例 右圖所示的有向圖D的可達(dá)矩陣為70/819.3 帶權(quán)圖與帶權(quán)圖中的最短通路(一) 帶權(quán)圖(二) 最短通路問(wèn)題(三) 狄克斯瑞(Dijkstra)算法71/81例假設(shè)有分布在不同建筑物中的5臺(tái)計(jì)算機(jī)C1, C2, C3, C4, C5。計(jì)算機(jī)連接的可能方案以及每種連接方式的本錢(qián)單位：元如右圖所示。C1 100 C2C3C4C5120370200本錢(qián)最低的安裝方案C1 100 C2900

24、C3C4C512040020045037072/81帶權(quán)圖一個(gè)帶權(quán)圖規(guī)定為 一個(gè)有序三元組(V，E，f )，或 一個(gè)有序三元組(V，E，g)，或 一個(gè)有序四元組(V，E，f，g)，其中，V是頂點(diǎn)集，E是邊集， f是定義在V上的函數(shù)，g是定義在E上的函數(shù)，f和g我們可以稱(chēng)為權(quán)函數(shù)。對(duì)于每一個(gè)頂點(diǎn)或邊x，f(x)和g(x)可以是一個(gè)數(shù)字、符號(hào)或是某種量。73/81帶權(quán)圖中的最短通路設(shè)G=(V,E,W)是一個(gè)帶權(quán)圖，其W是邊集E 到R+=xRx0 的一個(gè)函數(shù)。通常稱(chēng) W(e)為邊e的長(zhǎng)度，圖G中一個(gè)通路的長(zhǎng)度定義為通路中所經(jīng)過(guò)的邊的長(zhǎng)度之和。設(shè) v0,zV， 要求從 v0到z的最短通路的長(zhǎng)。74/8

25、1Dijkstra算法的根本思想先把V分成兩個(gè)子集，一個(gè)設(shè)為T(mén), T=vVv0到v的最短通路的長(zhǎng)已經(jīng)求出，另一個(gè)是P=VT。顯然T，因?yàn)橹辽賤0T。要不斷地?cái)U(kuò)大T，直到zT。T PVTv0z75/81定理對(duì)于任意的xP，設(shè)LT(x)表示從v0僅經(jīng)過(guò)T中的頂點(diǎn)到x的最短通路的長(zhǎng)。假設(shè)不存在這樣的通路，置LT(x)=。稱(chēng)LT(x)為 x關(guān)于T的指標(biāo)。令 LT(t1)=minLT(x) xP那么 LT(t1)是從v0到t1的最短通路的長(zhǎng)。T PVTv0t1注：LT(x)即為教材上的l(t)x76/81定理的證明假設(shè)存在從v0到t1的通路其長(zhǎng)小于LT(t1)，這條路一定包含了P中的頂點(diǎn)否那么， 與LT

26、(t1)最小性矛盾。設(shè)t2P，且t2是從v0到t1的其長(zhǎng)度小于LT(t1)的通路中遇到的第一個(gè)P中的點(diǎn)。于是有一條從v0到t2僅經(jīng)過(guò)T中的點(diǎn)的通路，其長(zhǎng)度小于LT(t1)，而由LT(t2)的定義知，LT(t2)LT(t1), 這與假設(shè)LT(t1)=minLT(x)xP矛盾。T PVTv0t1t277/81命題設(shè)T和P，已找出t1, 使 LT(t1)=min LT(x) xP。令 T=T t1 P=P t1，并設(shè) LT(x)表示僅經(jīng)過(guò)T中的點(diǎn)從v0到x的最短通路的長(zhǎng)。那么有 LT(x)=minLT(x), LT(t1)+W(t1,x)這里，假設(shè)圖中t1,x E, 取W(t1,x)=。v0t1xt

27、v0t1xv0t1x79/81命題的證明從v0到x且不含P中頂點(diǎn)的任何一條最短通路，只有兩種可能的情況：一條既不包含P中的頂點(diǎn)也不包含t1的通路. 此時(shí)，最短通路長(zhǎng)仍然為 LT(x)v0t1x80/81命題的證明(2) 一條由v0到t1不包含P中的其它頂點(diǎn)，然后由t1經(jīng)過(guò)t1,x到x的通路。 此時(shí)，最短通路長(zhǎng)為 LT(t1) +W(t1,x) .v0t1x81/81命題證明的說(shuō)明：還有一種？實(shí)際上，從v0到t1再到 t的這條通路一定不短于從v0到t的最短通路，而由作法可知從v0 到t的最短路經(jīng)過(guò)的點(diǎn)全在T中，所以即使有可能產(chǎn)生一條最短路，我們也可以用一條從 v0到t的僅經(jīng)過(guò)T中點(diǎn)的最短通路取代

28、，也就是說(shuō)這種情況可以歸化為第一種情況考慮。從 v0到t1，再到 T中某一頂點(diǎn)t，由t到x中間不經(jīng)P中點(diǎn)。v0t1xt82/81Dijkstra算法設(shè)起點(diǎn)是v0，終點(diǎn)是z。具體程序如下：開(kāi)始，設(shè) T=v0，P=VT，對(duì)P中的每一個(gè)頂點(diǎn)x,令 LT(x)=W(v0,x)。設(shè)t1是P中關(guān)于T有最小指標(biāo)的頂點(diǎn), 即 LT(t1)=minLT(x) xP。假設(shè)t1=z，那么終止。 否那么，設(shè) T=T t1，P=P t1。 對(duì)于P中的每一個(gè)頂點(diǎn) ，計(jì)算它關(guān)于T的指標(biāo)： LT(x)=minLT(x), LT(t1)+W(t1,x)。 把T代為T(mén),把P代為P,把LT(x)代為L(zhǎng)T(x)， 重復(fù)步驟(2)。83/81例