離散數(shù)學(xué)圖概念7路與回路

1、精選ppt1Discrete Mathematics精選ppt2第七章第七章 圖論圖論n圖論是近年來發(fā)展迅速而又應(yīng)用廣泛的一圖論是近年來發(fā)展迅速而又應(yīng)用廣泛的一門學(xué)科。本章主要講授圖論的基本概念和門學(xué)科。本章主要講授圖論的基本概念和定理。定理。n圖論：數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、編譯原理、圖論：數(shù)據(jù)結(jié)構(gòu)、操作系統(tǒng)、編譯原理、計算機網(wǎng)絡(luò)原理的基礎(chǔ)計算機網(wǎng)絡(luò)原理的基礎(chǔ)n要求：熟練掌握圖的基本概念和定理并能要求：熟練掌握圖的基本概念和定理并能夠進行簡單應(yīng)用。夠進行簡單應(yīng)用。精選ppt37-1 圖的基本概念圖的基本概念本節(jié)要熟悉下列概念（本節(jié)要熟悉下列概念（26個）：個）：圖、圖、 無向邊、無向邊、 有向邊、

2、有向邊、 起始結(jié)點、起始結(jié)點、 終止結(jié)點、終止結(jié)點、無向圖、無向圖、有向圖、有向圖、 混合圖、混合圖、鄰接點、鄰接點、 鄰接邊、鄰接邊、孤立結(jié)點、孤立結(jié)點、零圖、零圖、平凡圖、平凡圖、結(jié)點的度數(shù)、結(jié)點的度數(shù)、圖的最大度、最小度、圖的最大度、最小度、結(jié)點的入度、結(jié)點的入度、 結(jié)點的出度、結(jié)點的出度、平行邊、平行邊、簡單圖、簡單圖、 完全圖、完全圖、補圖、補圖、 子圖、子圖、生成子圖、生成子圖、 子圖的相對于圖的補圖、子圖的相對于圖的補圖、圖的同構(gòu)圖的同構(gòu)多重圖、多重圖、精選ppt4n圖的定義圖的定義n點的度數(shù)點的度數(shù)n特殊的圖特殊的圖n圖同構(gòu)圖同構(gòu)7-1 圖的基本概念圖的基本概念精選ppt5一、

3、圖的定義一、圖的定義 定義定義7-1.1 圖圖（graph）G由一個三元組由一個三元組表示，其中：表示，其中： 非空集合非空集合V(G)=v1,v,v2 2,v,vr r 稱為圖稱為圖G的的結(jié)點集結(jié)點集，其成員其成員vi(i=1,2,r)稱為稱為結(jié)點結(jié)點或或頂點頂點（nodes or vertices）；）； 集合集合 E(G)=e1,e2,es 稱為圖稱為圖G的的邊集邊集，其成員，其成員ej(j=1,2,s)稱為稱為邊邊(edges)。 函數(shù)函數(shù) G ：E(G)(V(G),V(G) ，稱為邊與頂點的稱為邊與頂點的關(guān)聯(lián)映射關(guān)聯(lián)映射（associatve mapping） 精選ppt6例例1：G

4、=其中其中V(G)=a，b，c，d，E(G)=e1，e2，e3，e4，e5，e6， G(e1)=(a，b)， G(e2)=(a，c)， G(e3)=(b，d)， G(e4)=(b，c)， G(e5)=(d，c)， G(e6)=(a，d)abcde1e2e3e4e5e6 若把圖中的邊若把圖中的邊ej看作總是和兩個結(jié)點關(guān)聯(lián)，那么一個圖亦簡記看作總是和兩個結(jié)點關(guān)聯(lián)，那么一個圖亦簡記為為G= ，其中非空集合，其中非空集合V稱為圖稱為圖G的的結(jié)點集結(jié)點集，集合，集合 E稱為圖稱為圖G的的邊集邊集。 若邊若邊ej與結(jié)點無序偶與結(jié)點無序偶(vj,vk)關(guān)聯(lián)，那么稱該邊為無向邊。關(guān)聯(lián)，那么稱該邊為無向邊。 若

5、邊若邊ej與結(jié)點序偶與結(jié)點序偶關(guān)聯(lián)，那么稱該邊為有向邊。關(guān)聯(lián)，那么稱該邊為有向邊。起始結(jié)點起始結(jié)點終止結(jié)點終止結(jié)點精選ppt7例例2：G=其中其中V(G)=a，b，c，d，E(G)=e1，e2，e3，e4，e5，e6， G(e1)=(a，b)， G(e2)=(a，c)， G(e3)=(b，d)， G(e4)=(b，c)， G(e5)=(d，c)， G(e6)=(a，d)一個圖與結(jié)點、連接結(jié)點的邊、邊與結(jié)點的關(guān)聯(lián)有關(guān)。精選ppt82、有向邊、有向邊&無向邊無向邊n無向邊：如果無向邊：如果E中邊中邊ei對應(yīng)對應(yīng)V中的結(jié)點對是無中的結(jié)點對是無序的序的(u，v)稱稱ei是無向邊，記是無向邊，記

6、ei=(u，v)，稱，稱u，v是是ei的兩個端點。的兩個端點。n有向邊：如果有向邊：如果ei與結(jié)點有序?qū)εc結(jié)點有序?qū)ο鄬?yīng)，相對應(yīng)，稱稱ei是有向邊，記是有向邊，記ei=，稱，稱u為為ei的始點，的始點，v為為ei的終點。的終點。精選ppt93、圖的分類：、圖的分類：無向圖：每條邊均為無向邊的圖稱為無向圖。無向圖：每條邊均為無向邊的圖稱為無向圖。有向圖：每條邊均為有向邊的圖稱為有向圖。有向圖：每條邊均為有向邊的圖稱為有向圖?；旌蠄D：有些邊是無向邊，有些邊是有向邊的圖稱混合圖：有些邊是無向邊，有些邊是有向邊的圖稱為混合圖。為混合圖。V1v1v4v5v1v2v3v4V2V3V4(a)無向圖無向圖(

7、b)有向圖有向圖( c ) 混合圖混合圖(孤立點孤立點)v2v3環(huán)環(huán)精選ppt101、G1=是無向圖，其中V1=V1，V2，V3，V4，V5，V6，E1=e1，e2，e3，e4，e5，e6，e1=(V1，V3)，e2=(V1，V4)，e2=(V2，V4)，e3=(V3，V4)，e4=(V3，V6)，e5=(V4，V5)，e6=(V5，V6)3、G3=是混合圖，V3=V1，V2，V3，V4，E3=，(V1，V3)，(V4，V2)2、G2=是有向圖，其中V2=V1，V2，V3，V4，E=，練習(xí)：畫出下面的圖。練習(xí)：畫出下面的圖。精選ppt114、點和邊的關(guān)聯(lián)：如、點和邊的關(guān)聯(lián)：如ei=(u，v)或

8、或ei=稱稱u，v與與ei關(guān)聯(lián)。關(guān)聯(lián)。5、點與點的相鄰：關(guān)聯(lián)于同一條邊的結(jié)點稱為鄰接、點與點的相鄰：關(guān)聯(lián)于同一條邊的結(jié)點稱為鄰接點。點。6、邊與邊的鄰接：關(guān)聯(lián)于同一結(jié)點的邊稱為鄰接、邊與邊的鄰接：關(guān)聯(lián)于同一結(jié)點的邊稱為鄰接邊。邊。7、孤立結(jié)點：不與任何結(jié)點相鄰接的結(jié)點稱為孤、孤立結(jié)點：不與任何結(jié)點相鄰接的結(jié)點稱為孤立結(jié)點。立結(jié)點。8、零圖：僅有孤立結(jié)點的圖。、零圖：僅有孤立結(jié)點的圖。9、平凡圖：僅有一個孤立結(jié)點的圖。、平凡圖：僅有一個孤立結(jié)點的圖。精選ppt1210、自回路、自回路(環(huán)環(huán))：關(guān)聯(lián)于同一結(jié)點的邊稱為自回路，：關(guān)聯(lián)于同一結(jié)點的邊稱為自回路，或稱為環(huán)?；蚍Q為環(huán)。11、平行邊：在有向圖

9、中，始點和終點均相同的邊、平行邊：在有向圖中，始點和終點均相同的邊稱為平行邊，無向圖中若兩點間有多條邊，稱這些稱為平行邊，無向圖中若兩點間有多條邊，稱這些邊為平行邊，兩點間平行邊的條數(shù)稱為邊的重數(shù)。邊為平行邊，兩點間平行邊的條數(shù)稱為邊的重數(shù)。精選ppt13n圖的定義圖的定義n點的度數(shù)點的度數(shù)n特殊的圖特殊的圖n圖同構(gòu)圖同構(gòu)7-1 圖的基本概念圖的基本概念精選ppt14二、點的度數(shù)二、點的度數(shù)1、點的度數(shù)的定義、點的度數(shù)的定義定義定義7-1.2：在圖：在圖G=，v V，與結(jié)點，與結(jié)點v關(guān)聯(lián)的邊數(shù)稱為關(guān)聯(lián)的邊數(shù)稱為該點的度數(shù)，記為該點的度數(shù)，記為deg(v)。孤立結(jié)點的度數(shù)為孤立結(jié)點的度數(shù)為0。2

10、、出度與入度、出度與入度定義定義7-1.3：在：在有向圖有向圖中，中，v V，n以以v為始點的邊數(shù)稱為該結(jié)點的出度，記作為始點的邊數(shù)稱為該結(jié)點的出度，記作deg+(v);n以以v為終點的邊數(shù)稱為該結(jié)點的入度，記作為終點的邊數(shù)稱為該結(jié)點的入度，記作deg-(v)。顯然有顯然有deg(v)=deg+(v)+deg-(v)精選ppt15如：如：G1是無向圖，是無向圖，deg(v1)=3，deg(v2)=1G2是有向圖，是有向圖，deg+(v1)=3，deg-(v1)=2，deg(v1)=5，v1v2G1v1v3v4v2G2精選ppt163、最大度和最小度：、最大度和最小度：圖圖G最大度記為最大度記為

11、 (G)=maxdeg(v)|v V(G)，最小度數(shù)記為最小度數(shù)記為 (G)=mindeg(v)|v V(G)。4、定理、定理7-1.1：每個圖中，結(jié)點度數(shù)總和等于邊數(shù)的兩倍。：每個圖中，結(jié)點度數(shù)總和等于邊數(shù)的兩倍。即即 deg(v)=2|E| v V 該定理又稱該定理又稱握手定理握手定理證明證明 因為每條邊必關(guān)聯(lián)兩個結(jié)點，而一條邊給予關(guān)聯(lián)因為每條邊必關(guān)聯(lián)兩個結(jié)點，而一條邊給予關(guān)聯(lián)的每個結(jié)點的度數(shù)為的每個結(jié)點的度數(shù)為1。因此在。因此在每個圖中，結(jié)點度數(shù)總每個圖中，結(jié)點度數(shù)總和等于邊數(shù)的兩倍。和等于邊數(shù)的兩倍。精選ppt17 5、定理、定理7-1.2圖中圖中, 度數(shù)為奇數(shù)的結(jié)點必度數(shù)為奇數(shù)的結(jié)點

12、必定是偶數(shù)個。定是偶數(shù)個。 證明：設(shè)證明：設(shè)G G中奇數(shù)度結(jié)點集合為中奇數(shù)度結(jié)點集合為V V1 1, ,偶數(shù)度結(jié)點集合偶數(shù)度結(jié)點集合為為V V2 2，則有：則有： deg(v)+ deg(v) = deg(v) =2|E| v V1 v V2 v V由于由于 deg(v)是是偶數(shù)之和必為偶數(shù)，而偶數(shù)之和必為偶數(shù)，而2|E|是偶數(shù)，是偶數(shù)， v V2故得故得 deg(v)是偶數(shù)，而各個是偶數(shù)，而各個deg(vi) (vi V1 )是是奇數(shù)，奇數(shù)， v V1這就要求偶數(shù)個這就要求偶數(shù)個deg(vi)求和，即求和，即|V V1 1|是偶數(shù)。是偶數(shù)。 精選ppt186、定理、定理7-1.3：在任何有向

13、圖中，所有結(jié)點的入度：在任何有向圖中，所有結(jié)點的入度之和等于所有結(jié)點的出度之和之和等于所有結(jié)點的出度之和， 且均等于邊數(shù)且均等于邊數(shù)。證明證明 因為每一條有向邊必對應(yīng)一個入度和一個因為每一條有向邊必對應(yīng)一個入度和一個出度，若一個結(jié)點具有一個入度或出度，則必關(guān)出度，若一個結(jié)點具有一個入度或出度，則必關(guān)聯(lián)一條有向邊，所以聯(lián)一條有向邊，所以有向圖中，各結(jié)點入度之和有向圖中，各結(jié)點入度之和等于邊數(shù)，各結(jié)點出度之和也等于邊數(shù)等于邊數(shù)，各結(jié)點出度之和也等于邊數(shù) 。因此，。因此，在任何有向圖中，所有結(jié)點的入度之和等于所有在任何有向圖中，所有結(jié)點的入度之和等于所有結(jié)點的出度之和。結(jié)點的出度之和。精選ppt19

14、n圖的定義圖的定義n點的度數(shù)點的度數(shù)n特殊的圖特殊的圖n圖同構(gòu)圖同構(gòu)7-1 圖的基本概念圖的基本概念精選ppt20三、特殊的圖三、特殊的圖1、多重圖、多重圖定義定義7-1.4：含有平行邊的圖稱為多重圖。：含有平行邊的圖稱為多重圖。2、簡單圖：不含平行邊和環(huán)的圖稱為簡單圖。、簡單圖：不含平行邊和環(huán)的圖稱為簡單圖。3、完全圖、完全圖定義定義7-1.5：簡單圖：簡單圖G=中，若每一對結(jié)點中，若每一對結(jié)點間均有邊相連，則稱該圖為完全圖。間均有邊相連，則稱該圖為完全圖。有有n個結(jié)點的無向完全圖記為個結(jié)點的無向完全圖記為Kn。無向完全圖：每一條邊都是無向邊無向完全圖：每一條邊都是無向邊 不含有平行邊和環(huán)不

15、含有平行邊和環(huán) 每一對結(jié)點間都有邊相連每一對結(jié)點間都有邊相連精選ppt21如果在如果在Kn中，對每一條邊任意確定一個方向，則稱該中，對每一條邊任意確定一個方向，則稱該圖為圖為n個結(jié)點的有向完全圖。個結(jié)點的有向完全圖。顯然它的邊數(shù)為顯然它的邊數(shù)為n(n-1)/2。 定理定理7-1.4圖中圖中, n個結(jié)點的無向完全圖個結(jié)點的無向完全圖Kn的邊數(shù)為的邊數(shù)為n(n-1)/2。 證明：證明： n個結(jié)點中任取兩個結(jié)點的組合數(shù)為個結(jié)點中任取兩個結(jié)點的組合數(shù)為 Cn2 = = n(n-1)/2故的邊數(shù)為故的邊數(shù)為 |E| = n(n-1)/2 精選ppt225、相對于完全圖的補圖、相對于完全圖的補圖定義定義7

16、-1.6：給定一個簡單圖：給定一個簡單圖G，由，由G中所有結(jié)點和所有能使中所有結(jié)點和所有能使G成為完全圖的添加邊組成的圖，稱為成為完全圖的添加邊組成的圖，稱為G的相對于完全圖的的相對于完全圖的補圖，或簡稱為補圖，或簡稱為G的補圖，記為的補圖，記為 G。即。即G=， G=，其中，其中E2=(u，v)u，v V，(u，v) E1。v5v1v2v3v4v5v1v2v3v4v5v1v2v3v4(a)完全圖完全圖K5(b)圖圖G(c)圖圖G的補圖的補圖G精選ppt236、子圖、子圖定義定義7-1.7：設(shè)圖：設(shè)圖G=，如果有圖，如果有圖G=，且，且E E，V V，則稱，則稱G為為G的子圖。的子圖。 當當V

17、=V時，則稱時，則稱G為為G的生成子圖。的生成子圖。例如，下圖，例如，下圖， 圖圖(b)的的G和圖和圖(c)的的G 都是圖都是圖(a)的的K5的子圖。的子圖。v5v1v2v3v4v5v1v2v3v4v5v1v2v3v4(a)完全圖完全圖K5(b)圖圖G(c)圖圖G的補圖的補圖G精選ppt247、相對于圖相對于圖G的補圖的補圖定義定義7-1.8：設(shè)設(shè)G=是是G=的子圖，若的子圖，若給定另一給定另一個圖個圖G”=使得使得E”=E-E，且，且V”中僅包含中僅包含E”的邊所關(guān)聯(lián)的邊所關(guān)聯(lián)的結(jié)點，則稱的結(jié)點，則稱G”是子圖是子圖G相對于圖相對于圖G的補圖。的補圖。例如，上圖例如，上圖(b)的的G是圖是圖

18、(c)的的G 相對于圖相對于圖(a)的的K5的補圖。的補圖。v5v1v2v3v4v5v1v2v3v4v5v1v2v3v4(a)完全圖完全圖K5(b)圖圖G(c)圖圖G的補圖的補圖G精選ppt25n圖的定義圖的定義n點的度數(shù)點的度數(shù)n特殊的圖特殊的圖n圖同構(gòu)圖同構(gòu)7-1 圖的基本概念圖的基本概念精選ppt26四、同構(gòu)四、同構(gòu)定義定義7-1.9：設(shè)圖：設(shè)圖G=及圖及圖G=，如果存在一一對應(yīng)的映射如果存在一一對應(yīng)的映射g：VV且且e=(vi，vj)(或或)是是G的一條邊，當且僅當?shù)囊粭l邊，當且僅當e=(g(vi)，g(vj)(或或)是是G的一條邊，的一條邊，則稱則稱G與與G同構(gòu)，記作同構(gòu)，記作G G

19、。精選ppt27兩圖同構(gòu)的一些必要條件：兩圖同構(gòu)的一些必要條件：1.結(jié)點數(shù)目相同；結(jié)點數(shù)目相同；2.邊數(shù)相等；邊數(shù)相等；3.度數(shù)相同的結(jié)點數(shù)目相等。度數(shù)相同的結(jié)點數(shù)目相等。以上幾個條件不是兩個圖同構(gòu)的充分條件。以上幾個條件不是兩個圖同構(gòu)的充分條件。見見279頁圖頁圖7-1.10同構(gòu)必須是結(jié)點和邊分別存在一一對應(yīng)。同構(gòu)必須是結(jié)點和邊分別存在一一對應(yīng)。精選ppt28作業(yè)n279頁:(5)（6）精選ppt297-2 路與回路路與回路 在現(xiàn)實世界中，常常要考慮這樣的問題：如在現(xiàn)實世界中，常常要考慮這樣的問題：如何從一個圖中的給定結(jié)點出發(fā)，沿著一些邊連續(xù)何從一個圖中的給定結(jié)點出發(fā)，沿著一些邊連續(xù)移動而達

20、到另一指定結(jié)點，這種依次由點和邊組移動而達到另一指定結(jié)點，這種依次由點和邊組成的序列，就形成了路的概念。成的序列，就形成了路的概念。精選ppt30學(xué)習(xí)本節(jié)要熟悉如下術(shù)語(22個)：路、路的長度、跡、回路、通路、圈、連通、連通分支、點割集、連通圖、割點、點連通度、邊割集、邊連通度、割邊、可達、單側(cè)連通、 強連通、強分圖、弱連通、弱分圖、單側(cè)分圖掌握5個定理，一個推論。精選ppt31n路路n無向圖的連通性無向圖的連通性n有向圖的連通性有向圖的連通性7-2 路與回路路與回路精選ppt32一、路一、路 定義定義7-2.1圖圖G=,設(shè)設(shè) v0,v1,vn V， e1,en E, 其中其中ei是關(guān)聯(lián)于結(jié)點

21、是關(guān)聯(lián)于結(jié)點vi-1,vi的邊，交替序列的邊，交替序列v0e1v1e2envn稱為結(jié)點稱為結(jié)點v0到到vn的的路路（path） 。 v0和和vn分別稱為路的分別稱為路的起點起點和和終點終點，邊的數(shù)目邊的數(shù)目n稱作路的稱作路的長度長度。當當v0=vn時，這條路稱作時，這條路稱作回路回路 。若一條路中所有的邊若一條路中所有的邊e1, , en均不相同均不相同,稱作稱作跡跡 。若一條路中所有的結(jié)點若一條路中所有的結(jié)點v0, v1, vn均不相同均不相同,稱作稱作通路通路 。閉的通路閉的通路,即除即除v0=vn之外之外,其余結(jié)點均不相同的路其余結(jié)點均不相同的路,稱作稱作圈圈。精選ppt33例如例如路：

22、路：v1e2v3e3v2e3v3e4v2e6v5e7v3跡：跡：v5e8v4e5v2e6v5e7v3e4v2通路：通路：v4e8v5e6v2e1v1e2v3圈：圈：v2e1v1e2v3e7v5e6v2精選ppt34n在簡單圖中一條路在簡單圖中一條路v0e1v1e2envn，由它的結(jié)，由它的結(jié)點序列點序列v0，v1，vn確定，所以簡單圖的路，確定，所以簡單圖的路，可由其結(jié)點序列表示。可由其結(jié)點序列表示。n在有向圖中，結(jié)點數(shù)大于在有向圖中，結(jié)點數(shù)大于1的一條路亦可由邊的一條路亦可由邊序列序列e1e2en表示。表示。精選ppt35 定理定理7-2.1n個結(jié)點的圖中，如果從結(jié)個結(jié)點的圖中，如果從結(jié)點點

23、vj到結(jié)點到結(jié)點vk存在一條路，則從結(jié)點存在一條路，則從結(jié)點vj到結(jié)點到結(jié)點vk必存在必存在一條不多于一條不多于n-1條邊的條邊的路路。 證明思路：多于證明思路：多于n-1條邊的路中必有重復(fù)出現(xiàn)的結(jié)條邊的路中必有重復(fù)出現(xiàn)的結(jié)點，反復(fù)刪去夾在兩個重復(fù)結(jié)點之間的邊之后，剩余點，反復(fù)刪去夾在兩個重復(fù)結(jié)點之間的邊之后，剩余的邊數(shù)不會超過的邊數(shù)不會超過n-1條邊。條邊。 精選ppt36 定理定理7-2.1的證明的證明 如果從結(jié)點如果從結(jié)點vj到到vk存在一條路，該路上的結(jié)點存在一條路，該路上的結(jié)點序列是序列是vjvivk，如果在這條中有，如果在這條中有l(wèi)條邊，則序列條邊，則序列中必有中必有 l+1個結(jié)點

24、，若個結(jié)點，若ln-1，則必有結(jié)點，則必有結(jié)點vs，它在，它在序列中不止出現(xiàn)一次，即必有結(jié)點序列序列中不止出現(xiàn)一次，即必有結(jié)點序列vjvsvsvk，在路中去掉從，在路中去掉從vs到到vs的這些邊，仍的這些邊，仍是是vj到到vk的一條路，但此路比原來的路邊數(shù)要少，的一條路，但此路比原來的路邊數(shù)要少，如此重復(fù)進行下去，必可得到一條從如此重復(fù)進行下去，必可得到一條從vj到到vk的不多的不多于于n-1條邊的路。條邊的路。精選ppt37 定理定理7-2.1n個結(jié)點的圖中，如果從結(jié)個結(jié)點的圖中，如果從結(jié)點點vj到結(jié)點到結(jié)點vk存在一條路，則從結(jié)點存在一條路，則從結(jié)點vj到結(jié)點到結(jié)點vk必存在必存在一條不多

25、于一條不多于n-1條邊的條邊的路路。 推論推論 n個結(jié)點的圖中，如果從結(jié)點個結(jié)點的圖中，如果從結(jié)點vj到結(jié)點到結(jié)點vk存在一條路，則從結(jié)點存在一條路，則從結(jié)點vj到結(jié)點到結(jié)點vk必存在一條必存在一條邊數(shù)小于邊數(shù)小于n的的通路通路。精選ppt38如在圖如在圖7-2.1中有中有5個結(jié)點。個結(jié)點。 v1到到v3的一條路為：的一條路為：v1e2v3e3v2e3v3e4v2e6v5e7v3此路中有此路中有6條邊，去掉條邊，去掉e3有路有路v1e2v3e4v2e6v5e7v3有有4條邊。條邊。v1到到v3最短的路為最短的路為v1e2v3精選ppt39n路路n無向圖的連通性無向圖的連通性n有向圖的連通性有向

26、圖的連通性7-2 路與回路路與回路精選ppt40二、無向圖的連通性：二、無向圖的連通性：1、連通、連通 定義定義7-2.2圖圖G中，如果從結(jié)點中，如果從結(jié)點u和結(jié)點和結(jié)點v之間若之間若存在一條路，則稱結(jié)點存在一條路，則稱結(jié)點u和結(jié)點和結(jié)點v是是連通的連通的（connected） 。結(jié)點之間的連通性是結(jié)點集結(jié)點之間的連通性是結(jié)點集V上的等價關(guān)系，對上的等價關(guān)系，對應(yīng)該等價關(guān)系，必可將作出一個劃分，把應(yīng)該等價關(guān)系，必可將作出一個劃分，把V分成非空分成非空子集子集V1, V2, , Vm,使得兩個結(jié)點使得兩個結(jié)點vj和和vk是連通的，當是連通的，當且僅當它們屬于同一個且僅當它們屬于同一個Vi 。把子

27、圖把子圖G(V1) , G(V2) , , G(Vm)稱為圖稱為圖G的的連通分支連通分支（connected components）,圖圖G的連通分支數(shù)記為的連通分支數(shù)記為W(G) 。精選ppt41精選ppt422、連通圖、連通圖 定義定義7-2.3：若圖：若圖G只有一個連通分支，則稱只有一個連通分支，則稱G是連通圖。是連通圖。 顯然在連通圖中，任意兩個結(jié)點之間必是連顯然在連通圖中，任意兩個結(jié)點之間必是連通的。通的。精選ppt43對于連通圖，常常由于刪除了圖中的點或邊，而影響了對于連通圖，常常由于刪除了圖中的點或邊，而影響了圖的連通性。圖的連通性。結(jié)點結(jié)點v，即是把即是把v以及與以及與v關(guān)關(guān)聯(lián)

28、的邊都刪除。聯(lián)的邊都刪除。：，即是把該邊刪除。，即是把該邊刪除。 v3v2v1v6v4(a)v5v5v1v2v3v6v4(c)ev3v2v6v4(b)v5e精選ppt443、割點、割點定義定義7-2.4 圖圖G =是連通圖是連通圖,若有結(jié)點集若有結(jié)點集V1 V,使圖使圖G中中V1V1連通圖連通圖,則稱則稱V1是是G的一個的一個點割集點割集(cut-set of nodes) 。若某一個點構(gòu)成一個點割集，則稱該點為若某一個點構(gòu)成一個點割集，則稱該點為割點。割點。sabcdabcdba精選ppt45點連通度：是為了產(chǎn)生一個不連通圖需要刪去的點的最點連通度：是為了產(chǎn)生一個不連通圖需要刪去的點的最少數(shù)

29、目，也稱為連通度，記為少數(shù)目，也稱為連通度，記為k(G) 。即即k(G)=min|V1| V1是是G的點割集的點割集 稱為圖稱為圖G的的點連通度點連通度(1)若若G是平凡圖，則是平凡圖，則V1= ，k(G)=0(2)k(Kn)=n-1(3)若圖存在割點，則若圖存在割點，則k(G)=1(4)規(guī)定非連通圖的連通度規(guī)定非連通圖的連通度k(G)=0v5v1v2v3v4v5v1v3v4點割集點割集V1=v2精選ppt464、割邊、割邊 定義定義7-2.5 圖圖G =是連通圖是連通圖,若有邊若有邊集集E1 E E，使圖，使圖 G中中E1E1連通圖，則稱連通圖，則稱E1是是G的一個的一個邊割集邊割集(cut

30、-set of edges) 。若某一條邊就構(gòu)成一個邊割集，則稱若某一條邊就構(gòu)成一個邊割集，則稱該邊為該邊為割邊割邊或或橋橋。 割邊割邊e使圖使圖G滿足滿足W(G-e)W(G) 。精選ppt47連通度連通度(edge-connectivity) (G)定義定義：非平凡：非平凡圖的邊連通度為圖的邊連通度為 (G)=min |E1| | E1是是G G的邊割集的邊割集 邊連通度邊連通度 (G)是為了產(chǎn)生一個不連通圖需要刪是為了產(chǎn)生一個不連通圖需要刪去的邊的最少數(shù)目。去的邊的最少數(shù)目。(1)若若G是平凡圖則是平凡圖則E1= ，(G)=0(2)若若G存在割邊，則存在割邊，則 (G)=1， (3)規(guī)定非

31、連通圖的邊連通度為規(guī)定非連通圖的邊連通度為 (G)=0精選ppt485、定理定理7-2.2 圖圖G,有有k(G) (G)(G) 。在在7-2.2節(jié)定義了圖的最小度：節(jié)定義了圖的最小度： (G)=min(deg(v)，v V) 下面的定理給出了點連通度下面的定理給出了點連通度k(G) 、邊連通度、邊連通度 (G)和圖的和圖的最小度最小度 (G)之間的關(guān)系。之間的關(guān)系。282頁圖7- 2.3(a)k(G)=1,(G)=1,(G)=2282頁圖7- 2. 4k(G)=1,(G)=2,(G)=2精選ppt49證明：證明： 若若G不連通，則不連通，則k(G)= (G)=0，故上式成立。，故上式成立。 若

32、若G連通，連通，可分兩步證明上式也成立：可分兩步證明上式也成立： 1)先證明先證明 (G) (G)： 如果如果G是平凡圖，則是平凡圖，則 (G)=0 (G)， 若若G是非平凡圖，則因每一結(jié)點的所有關(guān)聯(lián)邊必含一是非平凡圖，則因每一結(jié)點的所有關(guān)聯(lián)邊必含一個邊割集，個邊割集，(因因 (G)=mindeg(v)|v V，設(shè)，設(shè)u V使的使的deg(u)=(G)，與，與u相關(guān)聯(lián)的相關(guān)聯(lián)的 條邊必包含一個邊割集，至條邊必包含一個邊割集，至少這少這 條邊刪除使圖不連通。條邊刪除使圖不連通。)故故 (G) (G)。5、定理定理7-2.2 圖圖G,有有k(G) (G)(G) 。精選ppt502)再證再證k(G)

33、 (G)：(a)設(shè)設(shè) (G)=1，即，即G有一割邊，顯然這時有一割邊，顯然這時k(G)=l，上式成立。，上式成立。(b)設(shè)設(shè) (G)2，則必可刪去某，則必可刪去某 (G)條邊，使條邊，使G不連通，而刪去不連通，而刪去其中其中 (G)-1條邊，它仍是連通的，且有一條橋條邊，它仍是連通的，且有一條橋e=(u，v)。對。對 (G)-1條邊中的每一條邊都選取一個不同于條邊中的每一條邊都選取一個不同于u，v的端點，把的端點，把這些端點刪去則必至少刪去這些端點刪去則必至少刪去 (G)-1條邊。若這樣產(chǎn)生的圖是條邊。若這樣產(chǎn)生的圖是不連通的，則不連通的，則k(G) (G)-1 (G)，若這樣產(chǎn)生的圖是連通的

34、，若這樣產(chǎn)生的圖是連通的，則則e仍是橋，此時再刪去仍是橋，此時再刪去u或或v就必產(chǎn)生一個不連通圖，故就必產(chǎn)生一個不連通圖，故k(G) (G)。由。由1)和和2)得得k(G) (G) (G)。精選ppt516.定理定理7-2.3 無向圖無向圖G的結(jié)點的結(jié)點v是割點的充分必要條是割點的充分必要條件是存在兩個結(jié)點件是存在兩個結(jié)點u和和w,使得結(jié)點使得結(jié)點u和和w的每一條路都通過的每一條路都通過v 。 證明思路：證明思路： 1) 先證先證:v是割點是割點存在結(jié)點存在結(jié)點u和和w的每條路都通過的每條路都通過v 若若v是連通圖是連通圖G=割點，設(shè)刪去割點，設(shè)刪去v得到的子圖得到的子圖G , 則則G至少包至

35、少包含兩個連通分支含兩個連通分支G1=和和G2= 。任取任取u V1，w V2，因為因為G是連通的，故在是連通的，故在G中必有一條連結(jié)中必有一條連結(jié)u和和w的路的路C，但但u和和w在在G中屬于兩個不同的連通分支，故中屬于兩個不同的連通分支，故u和和w必不連通，因此必不連通，因此C必須通過必須通過v，故故u和和w之間的任意一條路都通過之間的任意一條路都通過v 。 2)再證再證:存在結(jié)點存在結(jié)點u和和w的每條路都通過的每條路都通過v v是割點是割點 若連通圖若連通圖G中的某兩個結(jié)點的每一條路都通過中的某兩個結(jié)點的每一條路都通過v，則刪去，則刪去v得到子得到子圖圖G ，在，在G中這兩個結(jié)點必然不連通

36、，故中這兩個結(jié)點必然不連通，故v是圖是圖G的割點。的割點。 精選ppt52n路路n無向圖的連通性無向圖的連通性n有向圖的連通性有向圖的連通性7-2 路與回路路與回路精選ppt53三、有向圖的連通性：三、有向圖的連通性：1、可達：、可達： 在無向圖在無向圖G中，從結(jié)點中，從結(jié)點u到到v若存在一條路，則若存在一條路，則稱結(jié)點稱結(jié)點u到結(jié)點到結(jié)點v是可達的。是可達的。有向圖的可達性：有向圖的可達性：圖圖G=, 從從結(jié)點結(jié)點u u和到結(jié)點和到結(jié)點v v有一條路有一條路,稱為從稱為從u u可達可達v v。 可達性可達性(accesible),是結(jié)點集上的二元關(guān)系，它是是結(jié)點集上的二元關(guān)系，它是自反的和傳遞的，但是一般來說不是對稱的。故可自反的和傳遞的，但是一般來說不是對稱的。故可達性不是等價關(guān)系。達性不是等價關(guān)系。精選ppt54 如果如果u可達可達v，它們之間可能不止一條路，在所有這，它們之間可能不止一條路，在所有這些路中，最短路的長度稱為些路中，最短路的長度稱為u和和v之間的距離（或短程之間的距離（或短程線），記作線），記作d，它滿足下列性質(zhì)：，它滿足下列性質(zhì)：nd0nd =0nd + d