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

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

2、E)是一個有向圖， 并稱V 為頂點集， 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) 畫出有向圖G=(V,E)246356/81有向圖G=(V,E): 邊、孤立點、自環(huán)假設(shè)(a,b) E，稱(a,b)為圖G中一條邊。設(shè)(a,b) E，稱邊(a,b)關(guān)聯(lián)于頂點a和b，頂點a稱為該邊的始點，頂點b稱為該邊的終點，并稱a和b相鄰。假設(shè)一個頂點沒有任何邊關(guān)聯(lián)于它，稱該頂點為孤立點。假設(shè)一條邊的始點和終點是同一

3、頂點，稱該邊為自環(huán)。246357/81多重集 約定一個多重集是一些對象的總體，但這些對象不必不同。如: a, a, a, b, b, c a, a, a a, b, c 一個元素的重數(shù)是它在該多重集里出現(xiàn)的次數(shù)集合僅是多重集中重數(shù)僅為0和1的特殊情況8/81無向圖G=(V,E)定義2 設(shè)V是一個非空有限集合， E是一個多重集合， E的元素是僅含V中兩個元素的多重子集。 那么稱二元組G=(V,E)是一個無向圖，例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無向圖G=(V,E) : 邊、自環(huán)、孤立點v,u E, 稱v,u是G中一條邊。稱V為頂點集， 稱E為邊集。設(shè)e=v,u 是G中的一條邊， v和u稱為邊e 的二個端點，稱邊 e關(guān)聯(lián) v和u，也稱v 鄰接到u，或 u鄰接于v。假設(shè)u=v，稱v,u 為G中的自環(huán)。對于任意的u V ，假設(shè)不存在任何邊關(guān)聯(lián)u，說頂點u是孤立點。邊和點：關(guān)聯(lián)點和點：相鄰邊和邊：相鄰10/81多重圖、簡單圖一個圖，有向圖或無向圖，其邊集假設(shè)是多重集，稱這樣的圖為多重圖，也簡稱圖。假設(shè)一個圖，也就是多重圖，其重數(shù)大于1的邊稱為多重邊，又稱有這樣邊的圖為有多重邊的圖。稱一個沒有多重邊，沒有自環(huán)，也沒有孤立點的圖為簡單

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

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

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

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

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

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

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

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

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

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

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

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

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

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

19、任意兩個頂點之間有邊直接相連，屬于同一個頂點子集Vi的任意兩個頂點借助頂點子集Vj的任意一個頂點連通。所以，根據(jù)連通的定義知：G的補圖一定連通 。圖的矩陣表示 關(guān)聯(lián)矩陣無向圖、有向圖鄰接矩陣無向圖、有向圖有向圖的可達矩陣 5556/81無向圖的關(guān)聯(lián)矩陣設(shè) G=(V,E)是一個無向圖，|V|=n，|E|=m，V=v1,v2, ,vn，E=e1,e2, ,em，那么有nm 階矩陣 ， M(G)=(mij)nm其中: 稱 M(G)=(mij)nm為圖G的關(guān)聯(lián)矩陣。mij=1 如頂點vi與邊ei關(guān)聯(lián)0 如頂點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)=特點：1、行和為度數(shù)2、列和為23、所有元素的和為總 度數(shù)4、平行邊列相同有向圖的關(guān)聯(lián)矩陣58定義 設(shè)無環(huán)有向圖D=, V=v1, v2, , vn, E=e1, e2, , em, 令 則稱(mij)nm為D的關(guān)聯(lián)矩陣，記為M(D).59例：寫出以下圖的關(guān)聯(lián)矩陣60有向圖的關(guān)聯(lián)矩陣性質(zhì) (4) 平行邊對應(yīng)的列相同61/81鄰接矩陣 (adjacency matrix) 設(shè) G=(V,E)是一個無向圖，|V|=n，

21、V=v1,v2, ,vn，那么有nn 階矩陣， A(G)=(aij)nn其中: 稱 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, 令 為頂點vi鄰接到頂點vj邊的條數(shù)，稱( )mn為D的鄰接矩陣, 記作A(D), 簡記為A. 有向圖的鄰接矩陣補 64例 鄰接矩陣性質(zhì)65/81定理2設(shè)圖

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

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

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

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

26、(t1)最小性矛盾。設(shè)t2P，且t2是從v0到t1的其長度小于LT(t1)的通路中遇到的第一個P中的點。于是有一條從v0到t2僅經(jīng)過T中的點的通路，其長度小于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)過T中的點從v0到x的最短通路的長。那么有 LT(x)=minLT(x), LT(t1)+W(t1,x)這里，假設(shè)圖中t1,x E, 取W(t1,x)=。v0t1xt

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

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