離散數(shù)學(xué)第十四章的課件

1、1第五部分第五部分 圖論圖論本部分主要內(nèi)容本部分主要內(nèi)容l 圖的基本概念圖的基本概念l 歐拉圖、哈密頓圖歐拉圖、哈密頓圖l 樹(shù)樹(shù)l 平面圖平面圖l 支配集、覆蓋集、獨(dú)立集、匹配與著色支配集、覆蓋集、獨(dú)立集、匹配與著色2第十四章第十四章 圖的基本概念圖的基本概念主要內(nèi)容主要內(nèi)容l 圖圖l 通路與回路通路與回路l 圖的連通性圖的連通性l 圖的矩陣表示圖的矩陣表示l 圖的運(yùn)算圖的運(yùn)算3預(yù)備知識(shí)預(yù)備知識(shí)l 多重集合多重集合元素可以重復(fù)出現(xiàn)的集合元素可以重復(fù)出現(xiàn)的集合 某元素重復(fù)出現(xiàn)的次數(shù)稱為該元素的某元素重復(fù)出現(xiàn)的次數(shù)稱為該元素的重復(fù)度重復(fù)度 例如，在多重集合例如，在多重集合a,a,b,b,b,c,d

2、中，中，a,b,c,d的重復(fù)度分的重復(fù)度分別為別為2,3,1,1. l 無(wú)序積無(wú)序積A B=(x,y) | x A y B 設(shè)設(shè)A，B為任意的兩個(gè)集合，稱為任意的兩個(gè)集合，稱a,b|aAbB為為A與與B的的無(wú)序積無(wú)序積，記作，記作A&B. 通常，將無(wú)序積中的無(wú)序?qū)νǔ?，將無(wú)序積中的無(wú)序?qū),b,記為記為(a,b),并且允許并且允許a=b. 且無(wú)論且無(wú)論a,b是否相等均有是否相等均有(a,b)=(b,a),因而因而A&B=B&A. 414.1 圖圖定義定義14.1一個(gè)一個(gè)無(wú)向圖無(wú)向圖是一個(gè)有序的二元組是一個(gè)有序的二元組 =,記作記作G,其中其中(1) V 稱為頂點(diǎn)集稱為頂點(diǎn)集，其元素稱為其元素稱

3、為頂點(diǎn)頂點(diǎn)或或結(jié)點(diǎn)結(jié)點(diǎn)(2) E稱為邊集稱為邊集,它是無(wú)序積它是無(wú)序積V V 的的多重子集多重子集，其元素稱為無(wú)向，其元素稱為無(wú)向邊，簡(jiǎn)稱邊，簡(jiǎn)稱邊邊實(shí)例實(shí)例 設(shè)設(shè) V = v1, v2, ,v5, E = (v1,v1), (v1,v2), (v2,v3), (v2,v3), (v2,v5), (v1,v5), (v4,v5) 則則 G = 為一無(wú)向圖為一無(wú)向圖5有向圖有向圖定義定義14.2一個(gè)一個(gè)有向圖有向圖是一個(gè)有序的二元組是一個(gè)有序的二元組,記作記作D,其中其中（1）V同無(wú)向圖。同無(wú)向圖。（2） E是是笛卡兒積笛卡兒積V V的多重子集，稱為邊集，其元素稱為有向邊，簡(jiǎn)稱為的多重子集，稱為

4、邊集，其元素稱為有向邊，簡(jiǎn)稱為邊邊。圖圖2表示的是一個(gè)有向圖，試寫(xiě)出它的表示的是一個(gè)有向圖，試寫(xiě)出它的V 和和 E 注意：圖的數(shù)學(xué)定義與圖形表示，在同構(gòu)（待敘）的意義下注意：圖的數(shù)學(xué)定義與圖形表示，在同構(gòu)（待敘）的意義下是一一對(duì)應(yīng)的是一一對(duì)應(yīng)的V = a,b,c,d, E = , , 6相關(guān)概念相關(guān)概念1. 圖圖 可用可用G泛指圖（無(wú)向的或有向的），泛指圖（無(wú)向的或有向的），D表示有向圖表示有向圖 V(G), E(G), V(D), E(D)，|V(G)| ，|E(G)| n階圖階圖2. n 階零圖階零圖Nn與平凡圖與平凡圖N1（1階零圖）階零圖）3. 空?qǐng)D空?qǐng)D4. 標(biāo)定圖與非標(biāo)定圖標(biāo)定圖與非

5、標(biāo)定圖5. 基圖基圖6. 用用 ek 表示無(wú)向邊或有向邊表示無(wú)向邊或有向邊7. 頂點(diǎn)與邊的關(guān)聯(lián)關(guān)系頂點(diǎn)與邊的關(guān)聯(lián)關(guān)系 關(guān)聯(lián)、關(guān)聯(lián)次數(shù)關(guān)聯(lián)、關(guān)聯(lián)次數(shù) 環(huán)環(huán) 孤立點(diǎn)孤立點(diǎn)8. 頂點(diǎn)之間的相鄰與邊之間的相鄰、鄰接頂點(diǎn)之間的相鄰與邊之間的相鄰、鄰接9. 鄰域與關(guān)聯(lián)集鄰域與關(guān)聯(lián)集71n階圖階圖 在圖的定義中，用在圖的定義中，用G表示無(wú)向圖，表示無(wú)向圖，D表示有向圖，但有時(shí)用表示有向圖，但有時(shí)用G泛指圖泛指圖(無(wú)向的或有向的無(wú)向的或有向的)，可是，可是D只能表示有向圖。另外，為方只能表示有向圖。另外，為方便起見(jiàn)，有時(shí)用便起見(jiàn)，有時(shí)用V(G)，E(G)分別表示分別表示G的頂點(diǎn)集和邊集，若的頂點(diǎn)集和邊集，若|

6、V(G)|=n,則稱則稱G為為n階圖階圖，對(duì)有向圖可做類(lèi)似規(guī)定。，對(duì)有向圖可做類(lèi)似規(guī)定。 2有限圖有限圖 若若|V(G)|與與|E(G)|均為有限數(shù)，則稱均為有限數(shù)，則稱G為為有限圖有限圖。 3n階零圖與平凡圖階零圖與平凡圖 在圖在圖G中，若邊集中，若邊集E(G)= ,則稱則稱G為為零圖零圖，此時(shí)，又若，此時(shí)，又若G為為n階階圖，則稱圖，則稱G為為n階零圖階零圖，記作，記作Nn，特別地，稱，特別地，稱N1為為平凡圖平凡圖。 4空?qǐng)D空?qǐng)D 在圖的定義中規(guī)定頂點(diǎn)集在圖的定義中規(guī)定頂點(diǎn)集V為非空集，但在圖的運(yùn)算中可能產(chǎn)為非空集，但在圖的運(yùn)算中可能產(chǎn)生頂點(diǎn)集為空集的運(yùn)算結(jié)果，為此規(guī)定生頂點(diǎn)集為空集的運(yùn)算

7、結(jié)果，為此規(guī)定頂點(diǎn)集為空集的圖為空頂點(diǎn)集為空集的圖為空?qǐng)D圖，并將空?qǐng)D記為，并將空?qǐng)D記為 。 相關(guān)概念相關(guān)概念8相關(guān)概念相關(guān)概念5標(biāo)定圖與非標(biāo)定圖、基圖標(biāo)定圖與非標(biāo)定圖、基圖 稱稱頂點(diǎn)或邊用字母標(biāo)定頂點(diǎn)或邊用字母標(biāo)定的圖為標(biāo)定圖，否則稱為非標(biāo)定圖。的圖為標(biāo)定圖，否則稱為非標(biāo)定圖。 將有向圖各將有向圖各有向邊均改成無(wú)向邊有向邊均改成無(wú)向邊后的無(wú)向圖稱為原來(lái)圖的基圖。后的無(wú)向圖稱為原來(lái)圖的基圖。 易知標(biāo)定圖與非標(biāo)定圖是可以相互轉(zhuǎn)化的。易知標(biāo)定圖與非標(biāo)定圖是可以相互轉(zhuǎn)化的。 6關(guān)聯(lián)與關(guān)聯(lián)次數(shù)、環(huán)、孤立點(diǎn)關(guān)聯(lián)與關(guān)聯(lián)次數(shù)、環(huán)、孤立點(diǎn) 設(shè)設(shè)G=為無(wú)向圖，為無(wú)向圖，ek=(vi，vj)E，則稱，則稱vi，vj

8、為為ek的端點(diǎn)，的端點(diǎn)，ek與與vi或或ek與與vj是彼此相關(guān)聯(lián)的。若是彼此相關(guān)聯(lián)的。若vivj，則稱，則稱ek與與vi或或ek與與vj的關(guān)聯(lián)次數(shù)為的關(guān)聯(lián)次數(shù)為1，若若vi=vj，則稱，則稱ek與與vi的關(guān)聯(lián)次數(shù)為的關(guān)聯(lián)次數(shù)為2，并稱，并稱ek為環(huán)。任意的為環(huán)。任意的vlV，若頂，若頂點(diǎn)點(diǎn)vl 不與邊不與邊ek關(guān)聯(lián)，則稱關(guān)聯(lián)，則稱ek與與vl的關(guān)聯(lián)次數(shù)為的關(guān)聯(lián)次數(shù)為0。 設(shè)設(shè)D=為有向圖，為有向圖，ek=E，稱，稱vi，vj為為ek的端點(diǎn)，若的端點(diǎn)，若vi=vj，則稱，則稱ek為為D中的環(huán)。無(wú)論在無(wú)向圖中還是在有向圖中，無(wú)邊關(guān)聯(lián)中的環(huán)。無(wú)論在無(wú)向圖中還是在有向圖中，無(wú)邊關(guān)聯(lián)的頂點(diǎn)均稱孤立點(diǎn)。的

9、頂點(diǎn)均稱孤立點(diǎn)。 7相鄰與鄰接相鄰與鄰接 設(shè)無(wú)向圖設(shè)無(wú)向圖G=，vi，vjV，ek，elE.若若etE，使得，使得et=（vi，vj），則稱），則稱vi與與vj是相鄰的。若是相鄰的。若ek與與el至少有一個(gè)公共端點(diǎn)，則稱至少有一個(gè)公共端點(diǎn)，則稱ek與與el是相鄰的。是相鄰的。 設(shè)有向圖設(shè)有向圖D=，vi，vjV，ek，elE.若若etE，使得，使得et=，則稱，則稱vi為為et的始點(diǎn)，的始點(diǎn)，vj為為et的終點(diǎn)，并稱的終點(diǎn)，并稱vi鄰接到鄰接到vj，vj鄰接于鄰接于vi。若若ek的終點(diǎn)為的終點(diǎn)為el的始點(diǎn)，則稱的始點(diǎn)，則稱ek與與el相鄰。相鄰。 9)()()(),()(|)(vvNvNvvu

10、GEvuGVuuvNv的閉鄰域的鄰域)(|)(關(guān)關(guān)聯(lián)聯(lián)與與veGEeevI 8. 鄰域與關(guān)聯(lián)集鄰域與關(guān)聯(lián)集 v V(G) (G為無(wú)向圖為無(wú)向圖) v 的關(guān)聯(lián)集的關(guān)聯(lián)集相關(guān)概念相關(guān)概念)()()(),()(|)(vvNvNvvuGEvuGVuuvNv的閉鄰域的鄰域)(|)(關(guān)關(guān)聯(lián)聯(lián)與與veGEeevI v 的關(guān)聯(lián)集的關(guān)聯(lián)集111111( )( )( )GGGvNvvNvvIv的鄰域 的閉鄰域 的關(guān)聯(lián)集 10)()()()()()(,)(|)()(,)(|)(vvNvNvvvvNvvuDEvuDVuuvvvuDEuvDVuuvvDDDDDDD 的的閉閉鄰鄰域域的的鄰鄰域域的的先先驅(qū)驅(qū)元元集集的的后

11、后繼繼元元集集8. 鄰域與關(guān)聯(lián)集鄰域與關(guān)聯(lián)集 v V(D) (D為有向圖為有向圖)相關(guān)概念相關(guān)概念( )( )( )( )DDDDdddddNddNd的后繼元集的先驅(qū)元集的鄰域的閉鄰域11多重圖與簡(jiǎn)單圖多重圖與簡(jiǎn)單圖定義定義14.3 (1) 無(wú)向圖中的平行邊及重?cái)?shù)無(wú)向圖中的平行邊及重?cái)?shù) 在無(wú)向圖中，關(guān)聯(lián)一對(duì)頂點(diǎn)的無(wú)向邊如果多于在無(wú)向圖中，關(guān)聯(lián)一對(duì)頂點(diǎn)的無(wú)向邊如果多于1條，則稱條，則稱這些邊為這些邊為平行邊平行邊，平行邊的條數(shù)稱為，平行邊的條數(shù)稱為重?cái)?shù)重?cái)?shù) (2) 有向圖中的平行邊及重?cái)?shù)（注意方向性）有向圖中的平行邊及重?cái)?shù)（注意方向性） 在有向圖中，關(guān)聯(lián)一對(duì)頂點(diǎn)的有向邊如果多于在有向圖中，關(guān)聯(lián)一

12、對(duì)頂點(diǎn)的有向邊如果多于1條，并且條，并且這些邊的始點(diǎn)和終點(diǎn)相同這些邊的始點(diǎn)和終點(diǎn)相同(也就是它們的方向相同也就是它們的方向相同)，則稱，則稱這些邊為這些邊為平行邊平行邊 (3) 多重圖：多重圖：含平行邊的圖含平行邊的圖 (4) 簡(jiǎn)單圖：簡(jiǎn)單圖：既不含平行邊也不含環(huán)的圖既不含平行邊也不含環(huán)的圖 在定義在定義14.3中定義的簡(jiǎn)單圖是極其重要的概念中定義的簡(jiǎn)單圖是極其重要的概念 12頂點(diǎn)的度數(shù)頂點(diǎn)的度數(shù)定義定義14.4 (1) 設(shè)設(shè)G=為為無(wú)向圖無(wú)向圖, v V,稱稱v作為邊的端點(diǎn)次數(shù)之和為作為邊的端點(diǎn)次數(shù)之和為v的度數(shù)，的度數(shù)， 簡(jiǎn)記為簡(jiǎn)記為 d(v)v的度數(shù)的度數(shù), 簡(jiǎn)稱簡(jiǎn)稱度度 (2) 設(shè)設(shè)D

13、=為為有向圖有向圖, v V, d-(v)稱稱v作為邊的始點(diǎn)次數(shù)之和作為邊的始點(diǎn)次數(shù)之和 為為v的的出度出度 d+(v)稱稱v作為邊的終點(diǎn)次數(shù)之和為作為邊的終點(diǎn)次數(shù)之和為v的的入度入度 d(v) d+(v) +d (v)為為 v的的度度或度數(shù)或度數(shù) (3) 無(wú)向圖無(wú)向圖G的的最大度最大度 (G), 最小度最小度 (G) (4) 有向圖有向圖D的的最大度最大度 (D)、最大出度、最大出度 (D)、最大入度、最大入度 +(D)與最小度與最小度 (D) 、最小出度、最小出度 (D)、最小入度、最小入度 +(D)13 (5) 奇奇度度頂點(diǎn)與偶度頂點(diǎn)頂點(diǎn)與偶度頂點(diǎn) 稱度數(shù)為稱度數(shù)為1的頂點(diǎn)為的頂點(diǎn)為懸掛

14、頂點(diǎn)懸掛頂點(diǎn)，與它關(guān)聯(lián)的邊稱為，與它關(guān)聯(lián)的邊稱為懸掛邊懸掛邊。度為偶數(shù)度為偶數(shù)(奇數(shù)奇數(shù))的頂點(diǎn)稱為的頂點(diǎn)稱為偶度偶度(奇度奇度)頂點(diǎn)頂點(diǎn)。 14無(wú)向圖中，無(wú)向圖中，d(v1)（環(huán)提供（環(huán)提供2度），度），最大度最大度 、最小度最小度 ，v4為懸掛頂點(diǎn)，為懸掛頂點(diǎn)，e7為懸掛邊。為懸掛邊。有向圖中，有向圖中， d+(a)、 d-(a) （環(huán)提供一個(gè)出度、一個(gè)入度）、（環(huán)提供一個(gè)出度、一個(gè)入度）、d(a)、 、 、最大出度最大出度 -、最小出度最小出度 、最大入度最大入度 +、最小入度最小入度 +15mvdnii2)(1 mvdvdmvdniiniinii 111)()(,2)(且且定理定理14

15、.1 設(shè)設(shè)G=為任意為任意無(wú)向圖無(wú)向圖，V=v1,v2,vn, |E|=m, 則則證證 G中每條邊中每條邊 (包括環(huán)包括環(huán)) 均有兩個(gè)端點(diǎn)，所以在計(jì)算均有兩個(gè)端點(diǎn)，所以在計(jì)算G中各頂點(diǎn)中各頂點(diǎn)度數(shù)之和時(shí)，每條邊均提供度數(shù)之和時(shí)，每條邊均提供2度，度，m 條邊共提供條邊共提供 2m 度度.本定理的證明類(lèi)似于定理本定理的證明類(lèi)似于定理14.1握手定理握手定理定理定理14.2 設(shè)設(shè)D=為任意為任意有向圖有向圖，V=v1,v2,vn, |E|=m, 則則16握手定理推論握手定理推論推論推論 任何圖任何圖 (無(wú)向或有向無(wú)向或有向) 中，奇度頂點(diǎn)的個(gè)數(shù)是偶數(shù)中，奇度頂點(diǎn)的個(gè)數(shù)是偶數(shù).證證 設(shè)設(shè)G=為任意圖

16、，令為任意圖，令 V1=v | v V d(v)為奇數(shù)為奇數(shù) V2=v | v V d(v)為偶數(shù)為偶數(shù) 則則V1 V2=V, V1 V2=，由握手定理可知，由握手定理可知由于由于2m, 均為偶數(shù)，所以均為偶數(shù)，所以 為偶數(shù)，但因?yàn)闉榕紨?shù)，但因?yàn)閂1中中頂點(diǎn)度數(shù)為奇數(shù)，所以頂點(diǎn)度數(shù)為奇數(shù)，所以|V1|必為偶數(shù)必為偶數(shù). 21)()()(2VvVvVvvdvdvdm 2)(Vvvd 1)(Vvvd17例例 無(wú)向圖無(wú)向圖G有有16條邊，條邊，3個(gè)個(gè)4度頂點(diǎn)，度頂點(diǎn)，4個(gè)個(gè)3度頂點(diǎn)，其余頂度頂點(diǎn)，其余頂點(diǎn)度數(shù)均小于點(diǎn)度數(shù)均小于3，問(wèn)，問(wèn)G的階數(shù)的階數(shù)n為幾？為幾？解解 本題的關(guān)鍵是應(yīng)用握手定理本題的

17、關(guān)鍵是應(yīng)用握手定理. 設(shè)除設(shè)除3度與度與4度頂點(diǎn)外，還有度頂點(diǎn)外，還有x個(gè)頂點(diǎn)個(gè)頂點(diǎn)v1, v2, , vx， 則則 d(vi) 2，i =1, 2, , x，于是得不等式于是得不等式 32 24+2x得得 x 4, 階數(shù)階數(shù) n 4+4+3=11. 握手定理應(yīng)用握手定理應(yīng)用P292 第第8題題18圖的度數(shù)列圖的度數(shù)列1 . V=v1, v2, , vn為無(wú)向圖為無(wú)向圖G的頂點(diǎn)集，稱的頂點(diǎn)集，稱d(v1), d(v2), , d(vn)為為G的的度數(shù)列度數(shù)列 注：注：對(duì)于頂點(diǎn)標(biāo)定的無(wú)向圖，它的度數(shù)列是唯一的。對(duì)于頂點(diǎn)標(biāo)定的無(wú)向圖，它的度數(shù)列是唯一的。 2. V=v1, v2, , vn為有向圖

18、為有向圖D的頂點(diǎn)集，的頂點(diǎn)集， D的的度數(shù)列度數(shù)列：d(v1), d(v2), , d(vn) D的的出度列出度列：d-(v1), d-(v2), , d-(vn) D的的入度列入度列：d+(v1), d+(v2), , d+(vn) 例：例：在圖在圖14.1(a)中，按頂點(diǎn)的標(biāo)定順序，度數(shù)列為中，按頂點(diǎn)的標(biāo)定順序，度數(shù)列為4,4,2,1,3. 在圖在圖14.1(b)中，按字母順序，度數(shù)列，出度列，入度列分別中，按字母順序，度數(shù)列，出度列，入度列分別為為5,3,3,3；4,0,2,1；1,3,1,2.3. 對(duì)于給定的非負(fù)整數(shù)列對(duì)于給定的非負(fù)整數(shù)列d=(d1,d2,dn)，若存在以，若存在以V=

19、v1,v2,vn為頂點(diǎn)集的為頂點(diǎn)集的n階無(wú)向圖階無(wú)向圖G，使得，使得d(vi)=di，則稱，則稱d是是可圖化的可圖化的。特別地，若所得圖是簡(jiǎn)單圖，則稱。特別地，若所得圖是簡(jiǎn)單圖，則稱d是是可簡(jiǎn)單圖可簡(jiǎn)單圖化化的。的。19圖的度數(shù)列圖的度數(shù)列d=(d1,d2,dn)是否為可圖化的，可由下面定理判別。是否為可圖化的，可由下面定理判別。 定理定理14.3 設(shè)非負(fù)整數(shù)列設(shè)非負(fù)整數(shù)列d=(d1,d2,dn)，則，則d是可圖化的當(dāng)且是可圖化的當(dāng)且僅當(dāng)僅當(dāng) 為偶數(shù)為偶數(shù). 易知：易知：(2, 4, 6, 8, 10)，(1, 3, 3, 3, 4) 是可圖化的，而是可圖化的，而 (3, 3, 3, 4) 不

20、是可圖化的。不是可圖化的。定理定理14.4 設(shè)設(shè)G為任意為任意n階無(wú)向簡(jiǎn)單圖，則階無(wú)向簡(jiǎn)單圖，則(G)n-1. 證證 因?yàn)橐驗(yàn)镚既無(wú)既無(wú)平行邊平行邊也無(wú)也無(wú)環(huán)環(huán)，所以，所以G中任何頂點(diǎn)中任何頂點(diǎn)v至多與至多與其余的其余的n-1個(gè)頂點(diǎn)均相鄰，于是個(gè)頂點(diǎn)均相鄰，于是d(v)n-1，由于，由于v的任意性，的任意性，所以所以(G)n-1. niid120例例14.2 判斷下列各非負(fù)整數(shù)列哪些是判斷下列各非負(fù)整數(shù)列哪些是可圖化的可圖化的？(1) (5,5,4,4,2,1)(2) (5,4,3,2,2)(3) (3,3,3,1)(4) (d1,d2,dn)，d1d2dn1 且為且為 偶數(shù)偶數(shù)(5) (4,

21、4,3,3,2,2) niid121圖的同構(gòu)圖的同構(gòu)定義定義14.5 設(shè)設(shè)G1=, G2=為兩個(gè)無(wú)向圖為兩個(gè)無(wú)向圖(兩個(gè)有向兩個(gè)有向圖圖)，若存在雙射函數(shù)，若存在雙射函數(shù)f:V1V2, 對(duì)于對(duì)于vi,vj V1, (vi,vj) E1 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) (f(vi),f(vj) E2 （ E1 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) E2 )并且并且, (vi,vj)（）與）與 (f(vi),f(vj)（）的重?cái)?shù)相）的重?cái)?shù)相同，則稱同，則稱G1與與G2是是同構(gòu)同構(gòu)的，記作的，記作G1 G2. l 圖之間的同構(gòu)關(guān)系具有自反性、對(duì)稱性和傳遞性圖之間的同構(gòu)關(guān)系具有自反性、對(duì)稱性和傳遞性.l 能找到多條同構(gòu)的必要條件，但它

22、們?nèi)皇浅浞謼l件：能找到多條同構(gòu)的必要條件，但它們?nèi)皇浅浞謼l件： 邊數(shù)相同，頂點(diǎn)數(shù)相同邊數(shù)相同，頂點(diǎn)數(shù)相同; 度數(shù)列相同度數(shù)列相同; 對(duì)應(yīng)頂點(diǎn)的關(guān)聯(lián)集及鄰域的元素個(gè)數(shù)相同，等等對(duì)應(yīng)頂點(diǎn)的關(guān)聯(lián)集及鄰域的元素個(gè)數(shù)相同，等等 若破壞必要條件，則兩圖不同構(gòu)若破壞必要條件，則兩圖不同構(gòu)l 判斷兩個(gè)圖同構(gòu)是個(gè)難題判斷兩個(gè)圖同構(gòu)是個(gè)難題22圖同構(gòu)的實(shí)例圖同構(gòu)的實(shí)例 (1) (2) (3) (4) 圖中，圖中，(1)與與(2)不同構(gòu)（度數(shù)列不同），不同構(gòu)（度數(shù)列不同），(3)與與(4)也不同構(gòu)也不同構(gòu).23n 階完全圖與競(jìng)賽圖階完全圖與競(jìng)賽圖定義定義14.6 (1) n (n 1) 階無(wú)向完全圖階無(wú)向完全圖

23、每個(gè)頂點(diǎn)與其余頂點(diǎn)均相鄰的每個(gè)頂點(diǎn)與其余頂點(diǎn)均相鄰的無(wú)向簡(jiǎn)單圖，記作無(wú)向簡(jiǎn)單圖，記作 Kn.簡(jiǎn)單性質(zhì)：邊數(shù)簡(jiǎn)單性質(zhì)：邊數(shù)(2) n (n 1)階階有向完全圖有向完全圖每對(duì)頂點(diǎn)之間均有兩條方向相每對(duì)頂點(diǎn)之間均有兩條方向相反的有向邊的有向簡(jiǎn)單圖反的有向邊的有向簡(jiǎn)單圖.簡(jiǎn)單性質(zhì)：簡(jiǎn)單性質(zhì)： (3) n (n 1) 階階競(jìng)賽圖競(jìng)賽圖基圖為基圖為Kn的有向簡(jiǎn)單圖的有向簡(jiǎn)單圖.簡(jiǎn)單性質(zhì)：邊數(shù)簡(jiǎn)單性質(zhì)：邊數(shù)1,2)1( nnnm 1121n),n(),n( nm 1,2)1( nnnm 24n 階階 k -正則圖正則圖(1)為為K5，(2)為為3階有向完全圖，階有向完全圖，(3)為為4階競(jìng)賽圖階競(jìng)賽圖. (

24、1) (2) (3)定義定義14.7 n 階階k-正則圖正則圖均有均有 d(v)=k ( = =k) 的無(wú)向簡(jiǎn)單圖的無(wú)向簡(jiǎn)單圖簡(jiǎn)單性質(zhì)：邊數(shù)（由握手定理得）簡(jiǎn)單性質(zhì)：邊數(shù)（由握手定理得）Nn是是0-正則圖正則圖Kn是是 n 1-正則圖，正則圖，彼得松圖是彼得松圖是3-正則圖（見(jiàn)書(shū)上圖正則圖（見(jiàn)書(shū)上圖14.3(a) 所示，記住它）所示，記住它）2nkm 25子圖子圖定義定義14.8 G=, G =(1) GG G 為為G的的子圖子圖，G為為G 的的母圖母圖(2) 若若GG且且V =V，則稱，則稱G 為為G的的生成子圖生成子圖(3) 若若VV或或EE，稱，稱G 為為G的的真子圖真子圖(4) V （

25、VV且且V）的）的導(dǎo)出子圖導(dǎo)出子圖，記作，記作GV (5) E （EE且且E）的）的導(dǎo)出子圖導(dǎo)出子圖，記作，記作GE 在圖中，設(shè)在圖中，設(shè)G為為(1)中圖所表示，取中圖所表示，取V1=a，b，c，則，則V1的導(dǎo)出子圖的導(dǎo)出子圖GV1為為(2)中圖所示。取中圖所示。取E1=e1，e3，則，則E1的導(dǎo)出子圖的導(dǎo)出子圖GE1為為(3)中中圖所示。圖所示。26補(bǔ)圖補(bǔ)圖定義定義14.9 設(shè)設(shè)G=為為n階無(wú)向簡(jiǎn)單圖，以階無(wú)向簡(jiǎn)單圖，以V為頂點(diǎn)集，以為頂點(diǎn)集，以所有使所有使G成為完全圖成為完全圖Kn的添加邊組成的集合為邊集的圖，的添加邊組成的集合為邊集的圖，稱為稱為G的的補(bǔ)圖補(bǔ)圖，記作，記作 .若若G ,

26、則稱則稱G是是自補(bǔ)圖自補(bǔ)圖. GG27刪除與加新邊刪除與加新邊定義定義14.9 設(shè)設(shè)G=為無(wú)向圖。為無(wú)向圖。(1) 設(shè)設(shè)eE，從，從G中去掉邊中去掉邊e，稱為，稱為刪除刪除e，并用，并用G-e表示表示從從G中刪除中刪除e所得子圖。又設(shè)所得子圖。又設(shè)E E，從，從G中刪除中刪除E中所有的中所有的邊，稱為刪除邊，稱為刪除E，并用，并用G-E表示刪除表示刪除E后所得子圖。后所得子圖。(2) 設(shè)設(shè)vV，從，從G中去掉中去掉v及所關(guān)聯(lián)的一切邊稱為及所關(guān)聯(lián)的一切邊稱為刪除頂點(diǎn)刪除頂點(diǎn)v，并用，并用G-v表示刪除表示刪除v后所得子圖。又設(shè)后所得子圖。又設(shè)V V，稱從，稱從G中刪中刪除除V中所有頂點(diǎn)為中所有頂

27、點(diǎn)為刪除刪除V，并用，并用G-V表示所得子圖。表示所得子圖。(3) 設(shè)邊設(shè)邊e=(u，v)E，先從，先從G中刪除中刪除e，然后將，然后將e的兩個(gè)端的兩個(gè)端點(diǎn)點(diǎn)u，v用一個(gè)新的頂點(diǎn)用一個(gè)新的頂點(diǎn)w(或用或用u或或v充當(dāng)充當(dāng)w)代替，使代替，使w關(guān)聯(lián)關(guān)聯(lián)除除e外外u，v關(guān)聯(lián)的一切邊，稱為關(guān)聯(lián)的一切邊，稱為邊邊e的收縮的收縮，并用，并用Ge表示所表示所得新圖。得新圖。(4) 設(shè)設(shè)u，vV(u，v可能相鄰，也可能不相鄰，且可能相鄰，也可能不相鄰，且uv)，在在u，v之間加新邊之間加新邊(u，v)，稱為，稱為加新邊加新邊，并用，并用G(u，v) (或或G(u，v)表示所得新圖。表示所得新圖。注：注：在收

28、縮邊和加新邊過(guò)程中可能產(chǎn)生在收縮邊和加新邊過(guò)程中可能產(chǎn)生環(huán)環(huán)和和平行邊平行邊。 28在圖中，設(shè)在圖中，設(shè)(1)中圖為中圖為G，則，則(2)為為G-e5，(3)為為G-e1，e4，(4)為為G-v5 ，(5)為為G-v4,v5，而，而(6)為為Ge5. 2914.2 通路與回路通路與回路定義定義14.11 給定圖給定圖G=（無(wú)向或有向的），（無(wú)向或有向的），G中中頂點(diǎn)與頂點(diǎn)與邊的交替序列邊的交替序列 = v0e1v1e2elvl，vi 1, vi 是是 ei 的端點(diǎn)的端點(diǎn).(1) 通路與回路：通路與回路： 為為通路通路；若；若 v0=vl， 為為回路回路，l 為為回路長(zhǎng)回路長(zhǎng) 度度.(2) 簡(jiǎn)單

29、通路與回路：所有邊各異，簡(jiǎn)單通路與回路：所有邊各異， 為為簡(jiǎn)單通路簡(jiǎn)單通路，又若，又若v0=vl， 為為簡(jiǎn)單回路簡(jiǎn)單回路(3) 初級(jí)通路初級(jí)通路(路徑路徑)與初級(jí)回路與初級(jí)回路(圈圈)： 中所有頂點(diǎn)各異，所中所有頂點(diǎn)各異，所有邊也各異，則稱有邊也各異，則稱 為為初級(jí)通路初級(jí)通路(路徑路徑)，又若除，又若除v0=vl，所，所有的頂點(diǎn)各不相同且所有的邊各異，則稱有的頂點(diǎn)各不相同且所有的邊各異，則稱 為為初級(jí)回路初級(jí)回路(圈圈)(4) 復(fù)雜通路與回路：有邊重復(fù)出現(xiàn)復(fù)雜通路與回路：有邊重復(fù)出現(xiàn)30幾點(diǎn)說(shuō)明幾點(diǎn)說(shuō)明表示法表示法 定義表示法定義表示法 只用邊表示法只用邊表示法 只用頂點(diǎn)表示法（在簡(jiǎn)單圖中）

30、只用頂點(diǎn)表示法（在簡(jiǎn)單圖中） 混合表示法混合表示法環(huán)環(huán)（長(zhǎng)為（長(zhǎng)為1的圈）的長(zhǎng)度為的圈）的長(zhǎng)度為1，兩條平行邊構(gòu)成的圈長(zhǎng)度為，兩條平行邊構(gòu)成的圈長(zhǎng)度為 2，無(wú)向簡(jiǎn)單圖中，圈長(zhǎng)，無(wú)向簡(jiǎn)單圖中，圈長(zhǎng) 3，有向簡(jiǎn)單圖中圈的長(zhǎng)度，有向簡(jiǎn)單圖中圈的長(zhǎng)度 2. 31通路與回路的長(zhǎng)度通路與回路的長(zhǎng)度定理定理14.5 在在n 階圖階圖G中，若從頂點(diǎn)中，若從頂點(diǎn)vi 到到vj（vi vj）存在通路，）存在通路，則從則從vi 到到 vj 存在長(zhǎng)度小于或等于存在長(zhǎng)度小于或等于n 1 的通路的通路.推論推論 在在 n 階圖階圖G中，若從頂點(diǎn)中，若從頂點(diǎn)vi 到到 vj（vi vj）存在通路，則）存在通路，則從從vi

31、到到vj 存在長(zhǎng)度小于或等于存在長(zhǎng)度小于或等于n 1的初級(jí)通路（路徑）的初級(jí)通路（路徑）.定理定理14.6 在一個(gè)在一個(gè)n 階圖階圖G中，若存在中，若存在 vi 到自身的回路，則一到自身的回路，則一定存在定存在vi 到自身長(zhǎng)度小于或等于到自身長(zhǎng)度小于或等于 n 的回路的回路.推論推論 在一個(gè)在一個(gè)n 階圖階圖G中，若存在中，若存在 vi 到自身的簡(jiǎn)單回路，則一到自身的簡(jiǎn)單回路，則一定存在長(zhǎng)度小于或等于定存在長(zhǎng)度小于或等于n 的初級(jí)回路的初級(jí)回路.3214.3 圖的連通性圖的連通性無(wú)向圖的連通性無(wú)向圖的連通性定義定義14.12 設(shè)無(wú)向圖設(shè)無(wú)向圖G=,u,vV，若，若u,v之間存在通路，則稱之間存

32、在通路，則稱u,v是連通是連通的，記作的，記作uv. vV，規(guī)定，規(guī)定vv. 由定義不難看出，無(wú)向圖中頂點(diǎn)之間的連通關(guān)系由定義不難看出，無(wú)向圖中頂點(diǎn)之間的連通關(guān)系 =（u,v）|u,vV且且u與與v之間有通路之間有通路 是自反的，對(duì)稱的，傳遞的，因而是自反的，對(duì)稱的，傳遞的，因而連通關(guān)系是連通關(guān)系是V上的等價(jià)關(guān)系上的等價(jià)關(guān)系。 若無(wú)向圖若無(wú)向圖G是平凡圖或是平凡圖或G中任何兩個(gè)頂點(diǎn)都是中任何兩個(gè)頂點(diǎn)都是連通連通的，則稱的，則稱G為連通圖，否為連通圖，否則稱則稱G是非連通圖或分離圖。是非連通圖或分離圖。 易知，完全圖易知，完全圖Kn(n1)都是連通圖，而都是連通圖，而零圖零圖Nn(n2)都是分離

33、圖。都是分離圖。 定義定義14.13 設(shè)無(wú)向圖設(shè)無(wú)向圖G=，V關(guān)于頂點(diǎn)之間的連通關(guān)系的關(guān)于頂點(diǎn)之間的連通關(guān)系的商集商集V/R=V1,V2,Vk，Vi為為等價(jià)類(lèi)等價(jià)類(lèi)，稱，稱導(dǎo)出子圖導(dǎo)出子圖GVi(i=1,2,k)為為G的的連通分支，連通分支數(shù)連通分支，連通分支數(shù)k常記為常記為p(G). 由定義可知，若由定義可知，若G為連通圖，則為連通圖，則p(G)=1，若，若G為非連通圖，則為非連通圖，則p(G)2，在所有的在所有的n階無(wú)向圖中，階無(wú)向圖中，n階零圖是連通分支最多的，階零圖是連通分支最多的，p(Nn)=n. 33短程線與距離短程線與距離短程線與距離短程線與距離 （設(shè)（設(shè)u ，v為無(wú)向圖為無(wú)向圖

34、G中任意兩個(gè)頂點(diǎn)中任意兩個(gè)頂點(diǎn) ） u與與v之間的之間的短程線短程線：u v，u與與v之間長(zhǎng)度最短的通路之間長(zhǎng)度最短的通路 u與與v之間的之間的距離距離：d(u,v)短程線的長(zhǎng)度短程線的長(zhǎng)度 u v時(shí)時(shí),d(u,v)= d(u,v)的性質(zhì)：的性質(zhì)： d(u,v) 0, 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)u=v時(shí)等號(hào)成立時(shí)等號(hào)成立 對(duì)稱性：對(duì)稱性：d(u,v)=d(v,u) 滿足三角不等式：滿足三角不等式：d(u,v)+d(v,w) d(u,w) 在完全圖在完全圖Kn(n2)中，任何兩個(gè)頂點(diǎn)之間的距離都是中，任何兩個(gè)頂點(diǎn)之間的距離都是1，而，而在在n階零圖階零圖Nn(n2)中，任何兩個(gè)頂點(diǎn)之間的距離都為中，任何兩

35、個(gè)頂點(diǎn)之間的距離都為. 34無(wú)向圖的連通程度無(wú)向圖的連通程度定義定義14.15 設(shè)無(wú)向圖設(shè)無(wú)向圖G = 。若存在。若存在V V 使得使得 p(G V ) p(G)，且對(duì)于任意的，且對(duì)于任意的V V ，均有，均有 p(G V ) = p(G)，則稱，則稱V 是是G的的點(diǎn)割集點(diǎn)割集。若點(diǎn)割集。若點(diǎn)割集 V = v ，則稱，則稱 v 為為割點(diǎn)割點(diǎn)。在上圖中，在上圖中，v2,v4 ，v3 ，v5 都是點(diǎn)割集，其中都是點(diǎn)割集，其中v3、 v5都是割點(diǎn)。而都是割點(diǎn)。而v2,v5、v1,v6不是點(diǎn)割集。不是點(diǎn)割集。 v1v2v5v6v3v4e4e1e2e3e5e635無(wú)向圖的連通程度無(wú)向圖的連通程度定義定義

36、14.16 設(shè)無(wú)向圖設(shè)無(wú)向圖G = , 若存在若存在 E E 使得使得 p(G E ) p(G) ，且對(duì)于任意的，且對(duì)于任意的E E ，均有，均有 p(G E ) = p(G)，則稱，則稱E 是是G的的邊割集邊割集（簡(jiǎn)稱割集）。（簡(jiǎn)稱割集）。 若邊割集若邊割集E = e ，則稱，則稱 e 為為割邊割邊（或橋）。（或橋）。在上圖中，在上圖中，e6 ，e5 ，e2,e3， e1,e2 ，e3,e4 ，e1,e4， e1,e3 ， e2,e4都是邊割集，其中都是邊割集，其中e6 、 e5是橋。是橋。而而e5,e6不是邊割集。不是邊割集。 v1v2v5v6v3v4e4e1e2e3e5e636點(diǎn)連通度與

37、邊連通度點(diǎn)連通度與邊連通度定義定義14.17 G是無(wú)向連通圖且不是完全圖是無(wú)向連通圖且不是完全圖 點(diǎn)連通度點(diǎn)連通度 (G) = min |V | V 為點(diǎn)割集為點(diǎn)割集 規(guī)定規(guī)定 (Kn) = n 1 若若G非連通，非連通， (G) = 0 若若 (G) k，則稱，則稱G為為 k-連通圖連通圖 定義定義14.18 設(shè)設(shè)G為無(wú)向連通圖為無(wú)向連通圖 邊連通度邊連通度 (G) = min|E | E 為邊割集為邊割集 若若G非連通，則非連通，則 (G) = 0 若若 (G) r，則稱，則稱G是是 r 邊邊-連通圖連通圖圖中，圖中， = =1，它是，它是 1-連通圖連通圖 和和 1邊邊-連通圖連通圖v1

38、v2v5v6v3v4e4e1e2e3e5e637幾點(diǎn)說(shuō)明幾點(diǎn)說(shuō)明l (Kn)= (Kn)=n 1l G非連通，則非連通，則 = =0l 若若G中有割點(diǎn)，則中有割點(diǎn)，則 =1，若有橋，則，若有橋，則 =1l 若若 (G)=k, 則則G是是1-連通圖，連通圖，2-連通圖，連通圖，k-連通圖，但連通圖，但不是不是(k+s)-連通圖，連通圖，s 1l 若若 (G)=r, 則則G是是1-邊連通圖，邊連通圖，2-邊連通圖，邊連通圖，r-邊連通邊連通圖，但不是圖，但不是(r+s)-邊連通圖，邊連通圖，s 1l , , 之間的關(guān)系之間的關(guān)系.定理定理14.7 對(duì)于任何無(wú)向圖對(duì)于任何無(wú)向圖G,有有 (G)(G)

39、(G)38有向圖的連通性有向圖的連通性定義定義14.19 D=為有向圖為有向圖 vi vj（vi 可達(dá)可達(dá) vj）vi 到到vj 有通路有通路 vi vj（vi 與與vj 相互可達(dá)）相互可達(dá)）性質(zhì)性質(zhì) 具有自反性具有自反性(vi vi)、傳遞性、傳遞性 具有自反性、對(duì)稱性、傳遞性具有自反性、對(duì)稱性、傳遞性 （它是（它是V上的等價(jià)關(guān)系）上的等價(jià)關(guān)系）vi 到到vj 的短程線與距離（見(jiàn)書(shū)本的短程線與距離（見(jiàn)書(shū)本285頁(yè)頁(yè)定義定義14.20）類(lèi)似于無(wú)向圖中，只需注意距離表示法的不同類(lèi)似于無(wú)向圖中，只需注意距離表示法的不同(無(wú)向圖中無(wú)向圖中d(vi,vj)，有向圖中，有向圖中d) 及及 d無(wú)對(duì)稱性無(wú)對(duì)

40、稱性39有向圖的連通性及分類(lèi)有向圖的連通性及分類(lèi)定義定義14.21 D=為有向圖為有向圖 D弱連通弱連通(連通連通)D的基圖為連通圖的基圖為連通圖 D單向連通單向連通 vi,vj V，vivj 與與 vjvi 至少成立其一至少成立其一 D強(qiáng)連通強(qiáng)連通 vi,vj V，均有，均有 vivj易知，強(qiáng)連通易知，強(qiáng)連通單向連通單向連通弱連通弱連通判別法判別法定理定理14.8 D強(qiáng)連通當(dāng)且僅當(dāng)強(qiáng)連通當(dāng)且僅當(dāng)D中存在經(jīng)過(guò)每個(gè)頂點(diǎn)至少一次中存在經(jīng)過(guò)每個(gè)頂點(diǎn)至少一次的回路的回路定理定理14.9 D單向連通當(dāng)且僅當(dāng)單向連通當(dāng)且僅當(dāng)D中存在經(jīng)過(guò)每個(gè)頂點(diǎn)至少一中存在經(jīng)過(guò)每個(gè)頂點(diǎn)至少一次的通路次的通路4014.4 圖

41、的矩陣表示圖的矩陣表示無(wú)向圖的關(guān)聯(lián)矩陣無(wú)向圖的關(guān)聯(lián)矩陣定義定義14.23 無(wú)向圖無(wú)向圖G=，|V|=n，|E|=m，令，令 mij 為頂點(diǎn)為頂點(diǎn) vi 與邊與邊 ej的關(guān)聯(lián)次數(shù)，稱的關(guān)聯(lián)次數(shù)，稱(mij)n m為為G 的的關(guān)聯(lián)矩陣關(guān)聯(lián)矩陣，記為，記為M(G). 重點(diǎn)掌握書(shū)本上重點(diǎn)掌握書(shū)本上288頁(yè)圖頁(yè)圖14.14的關(guān)聯(lián)矩陣的表示。的關(guān)聯(lián)矩陣的表示。無(wú)向圖關(guān)聯(lián)矩陣無(wú)向圖關(guān)聯(lián)矩陣M(G)的性質(zhì)如下：的性質(zhì)如下：11,1(1)2(1,2,.,)( )2.(2)( )(1,2,., )( )(3)2(4)(5)0nijimijiijiji jmijijmjmM Gmd vinM Givmmmv，即每列

42、元素之和均為，即第 行元素之和為 的度數(shù)。，各頂點(diǎn)度數(shù)之和等于邊的兩倍（握手定理的內(nèi)容）平行邊的列相同當(dāng)且僅當(dāng) 是孤立點(diǎn)41平行邊所對(duì)應(yīng)的列相同容）（有向圖握手定理的內(nèi)的個(gè)數(shù)，都等于邊數(shù)的個(gè)數(shù)等于 (4),.,2 , 1),() 1(),() 1(3)11-(2),.,2 , 1(0(1)111mjmjiijiijniijnivdmvdmmmjm 的的終終點(diǎn)點(diǎn)為為，不不關(guān)關(guān)聯(lián)聯(lián)與與，的的始始點(diǎn)點(diǎn)為為jijijiijevevevm10,1有向圖的關(guān)聯(lián)矩陣（無(wú)環(huán)有向圖無(wú)環(huán)有向圖） 定義定義14.24 有向圖有向圖D=,V=v1,v2, ,vn, E=e1,e2, ,em，令令則稱則稱 (mij)n

43、 m為為D的的關(guān)聯(lián)矩陣關(guān)聯(lián)矩陣，記為，記為M(D). 有向圖關(guān)聯(lián)矩陣有向圖關(guān)聯(lián)矩陣M(D)的性質(zhì)如下：的性質(zhì)如下：有向圖的關(guān)聯(lián)矩陣有向圖的關(guān)聯(lián)矩陣42有向圖的鄰接矩陣有向圖的鄰接矩陣定義定義14.25 設(shè)有向圖設(shè)有向圖D=, V=v1, v2, , vn, E=e1, e2, , em, 令令 為頂點(diǎn)為頂點(diǎn) vi 鄰接到頂點(diǎn)鄰接到頂點(diǎn) vj 邊的條數(shù)，稱邊的條數(shù)，稱 為為D的的鄰接矩陣鄰接矩陣，記作，記作A(D)，或簡(jiǎn)記為，或簡(jiǎn)記為A. 重點(diǎn)掌握書(shū)本上重點(diǎn)掌握書(shū)本上289頁(yè)圖頁(yè)圖14.16的鄰接矩陣的表示和圖的邊數(shù)。的鄰接矩陣的表示和圖的邊數(shù)。有向圖的鄰接矩陣有向圖的鄰接矩陣A(D)的性質(zhì)如下

44、：的性質(zhì)如下：nnija)()1(的回路數(shù)中長(zhǎng)度為的通路數(shù)中長(zhǎng)度為數(shù)）中所有元素之和等于邊（1(5)1(4)()(,)(3),.,2 , 1),(2),.,2 , 1),(1)1)1(,)1(111)1(111)1(1)1(1)1(DaDmaDAmvdamvdanjvdanivdaniiijiijnjjnjniijniininjijjniijinjij )1(ija43推論推論 設(shè)設(shè)Bl=A+A2+Al（l 1），則），則 Bl中元素中元素為D中長(zhǎng)度為 l 的通路總數(shù)，其中)( lija)(liia ninjlija11)( niliia1)( ninjlijb11)( niliib1)(定理

45、定理14.11 設(shè)設(shè) A為有向圖為有向圖 D 的鄰接矩陣，的鄰接矩陣，V=v1, v2, , vn為為頂點(diǎn)集，則頂點(diǎn)集，則 A 的的 l 次冪次冪 Al（l 1）中元素）中元素為D中vi 到vj長(zhǎng)度為 l 的通路數(shù)，其中為vi到自身長(zhǎng)度為 l 的回路數(shù)，而為為D中長(zhǎng)度小于或等于中長(zhǎng)度小于或等于 l 的回路數(shù)的回路數(shù)為為D中長(zhǎng)度小于或等于中長(zhǎng)度小于或等于 l 的通路數(shù)的通路數(shù). 鄰接矩陣的應(yīng)用鄰接矩陣的應(yīng)用為為D 中長(zhǎng)度為中長(zhǎng)度為 l 的回路總數(shù)的回路總數(shù). 44例例 有向圖有向圖D如圖所示，求如圖所示，求 A, A2, A3, A4，并回答以下各問(wèn)題：，并回答以下各問(wèn)題：(1) D 中長(zhǎng)度為中

46、長(zhǎng)度為1, 2, 3, 4的通路各有多少條？其中回路分別為多的通路各有多少條？其中回路分別為多少條？少條？(2) D 中長(zhǎng)度小于或等于中長(zhǎng)度小于或等于4的通路為多少條？其中有多少條回路？的通路為多少條？其中有多少條回路？實(shí)例實(shí)例452341000100020103001100120101010200110001000401050013001401030104001AAAA(1) D中長(zhǎng)度為中長(zhǎng)度為1的通路為的通路為8條，其中有條，其中有1條是回路條是回路. D中長(zhǎng)度為中長(zhǎng)度為2的通路為的通路為11條，其中有條，其中有3條是回路條是回路. D中長(zhǎng)度為中長(zhǎng)度為3的通路為的通路為14條，其中有條，其

47、中有1條是回路條是回路. D中長(zhǎng)度為中長(zhǎng)度為4的通路為的通路為17條，其中有條，其中有3條是回路條是回路.(2) D中長(zhǎng)度小于等于中長(zhǎng)度小于等于4的通路為的通路為50條，其中有條，其中有8條是回路條是回路.實(shí)例求解實(shí)例求解(1) D 中長(zhǎng)度為中長(zhǎng)度為1, 2, 3, 4的通的通路各有多少條？其中回路分路各有多少條？其中回路分別為多少條？別為多少條？(2) D 中長(zhǎng)度小于或等于中長(zhǎng)度小于或等于4的的通路為多少條？其中有多少通路為多少條？其中有多少條回路？條回路？46否則可達(dá), 0, 1jiijvvp 1101110111110001P定義定義14.27 設(shè)設(shè)D=為有向圖為有向圖. V=v1, v

48、2, , vn, 令令 有向圖的可達(dá)矩陣有向圖的可達(dá)矩陣稱稱 (pij)n n 為為D的可達(dá)矩陣，記作的可達(dá)矩陣，記作P(D)，簡(jiǎn)記為，簡(jiǎn)記為P. 由于由于 vi V，vivi，所以，所以P(D)主對(duì)角線上的元素全為主對(duì)角線上的元素全為1. 由定義不難看出由定義不難看出, D 強(qiáng)連通當(dāng)且僅當(dāng)強(qiáng)連通當(dāng)且僅當(dāng) P(D)為全為全1矩陣矩陣. 下圖所示有向圖下圖所示有向圖 D 的可達(dá)矩陣為的可達(dá)矩陣為47圖的運(yùn)算圖的運(yùn)算定義定義14.27 設(shè)設(shè)G1=，G2=為兩個(gè)圖。若為兩個(gè)圖。若V1V2= ，則稱，則稱G1與與G2是不交的。若是不交的。若E1E2= ，則稱，則稱G1與與G2是邊不交的或邊不重的。是邊

49、不交的或邊不重的。 由定義可知，不交的圖，必然是邊不交的，但反之不真。由定義可知，不交的圖，必然是邊不交的，但反之不真。 定義定義14.28 設(shè)設(shè)G1=，G2=為不含孤立點(diǎn)的兩個(gè)圖（它們同為為不含孤立點(diǎn)的兩個(gè)圖（它們同為無(wú)向圖或同為有向圖）。無(wú)向圖或同為有向圖）。 （1）稱以）稱以E1E2為邊集，以為邊集，以E1E2中邊關(guān)聯(lián)的頂點(diǎn)組成的集合中邊關(guān)聯(lián)的頂點(diǎn)組成的集合V1 V2為頂點(diǎn)集的圖為為頂點(diǎn)集的圖為G1與與G2的并圖的并圖，記作，記作G1G2. （2）稱以）稱以E1-E2為邊集，以為邊集，以E1-E2中邊關(guān)聯(lián)的頂點(diǎn)組成的集合為頂點(diǎn)集中邊關(guān)聯(lián)的頂點(diǎn)組成的集合為頂點(diǎn)集的圖為的圖為G1與與G2的差

50、圖的差圖，記作，記作G1-G2. （3）稱以）稱以E1E2為邊集，以為邊集，以E1E2中邊關(guān)聯(lián)的頂點(diǎn)組成的集合為頂點(diǎn)中邊關(guān)聯(lián)的頂點(diǎn)組成的集合為頂點(diǎn)集的圖為集的圖為G1與與G2的交圖的交圖，記作，記作G1G2. （4）稱以）稱以E1 E2為邊集（為集合之間的對(duì)稱差運(yùn)算），以為邊集（為集合之間的對(duì)稱差運(yùn)算），以E1 E2中中邊關(guān)聯(lián)的頂點(diǎn)組成的集合為頂點(diǎn)集的圖為邊關(guān)聯(lián)的頂點(diǎn)組成的集合為頂點(diǎn)集的圖為G1與與G2的環(huán)和的環(huán)和，記作，記作G1 G2. 48定義定義14.28中應(yīng)注意以下幾點(diǎn)：中應(yīng)注意以下幾點(diǎn)： 1若若G1=G2，則，則G1G2= G1G2=G1(G2)，而，而G1-G2=G2-G1= ，這

51、就是在圖的定義中給出空?qǐng)D概念的原，這就是在圖的定義中給出空?qǐng)D概念的原因。因。 2當(dāng)當(dāng)G1與與G2邊不重時(shí)，邊不重時(shí)，G1G2= ，G1-G2=G1，而而G2-G1=G2 ，G1 G2=G1G2. 3圖之間環(huán)和的定義也可以用并、交、差給出，即圖之間環(huán)和的定義也可以用并、交、差給出，即G1 G2=（G1G2）-（G1G2）. 49作作業(yè)業(yè)書(shū)本第書(shū)本第294頁(yè)頁(yè)第第45題題50第十四章第十四章 習(xí)題課習(xí)題課主要內(nèi)容主要內(nèi)容l 無(wú)向圖、有向圖、關(guān)聯(lián)與相鄰、簡(jiǎn)單圖、完全圖、正則圖、無(wú)向圖、有向圖、關(guān)聯(lián)與相鄰、簡(jiǎn)單圖、完全圖、正則圖、子圖、補(bǔ)圖；握手定理與推論；圖的同構(gòu)子圖、補(bǔ)圖；握手定理與推論；圖的同構(gòu)

52、l 通路與回路及其分類(lèi)通路與回路及其分類(lèi)l 無(wú)向圖的連通性與連通度無(wú)向圖的連通性與連通度l 有向圖的連通性及其分類(lèi)有向圖的連通性及其分類(lèi)l 圖的矩陣表示圖的矩陣表示51基本要求基本要求l 深刻理解握手定理及推論的內(nèi)容并能靈活地應(yīng)用它們深刻理解握手定理及推論的內(nèi)容并能靈活地應(yīng)用它們l 深刻理解圖同構(gòu)、簡(jiǎn)單圖、完全圖、正則圖、子圖、補(bǔ)圖、深刻理解圖同構(gòu)、簡(jiǎn)單圖、完全圖、正則圖、子圖、補(bǔ)圖、二部圖的概念以及它們的性質(zhì)及相互之間的關(guān)系二部圖的概念以及它們的性質(zhì)及相互之間的關(guān)系l 記住通路與回路的定義、分類(lèi)及表示法記住通路與回路的定義、分類(lèi)及表示法l 深刻理解與無(wú)向圖連通性、連通度有關(guān)的諸多概念深刻理解與無(wú)向圖連通性、連通度有關(guān)的諸多概念l 會(huì)判別有向圖連通性的類(lèi)型會(huì)判別有向圖連通性的類(lèi)型l 熟練掌握用鄰接矩陣及其冪求有向圖中通路與回路數(shù)的方熟練掌握用鄰接矩陣及其冪求有向圖中通路與回路數(shù)的方法，會(huì)求可達(dá)矩陣法，會(huì)求可達(dá)矩陣 5219階無(wú)向圖階無(wú)向圖G中，每個(gè)頂點(diǎn)的度數(shù)不是中，每個(gè)頂點(diǎn)的度數(shù)不是5就是就是6. 證明證明G中至少有中至少有5個(gè)個(gè)6度頂點(diǎn)或至少有度頂點(diǎn)或至少有6個(gè)個(gè)5度頂點(diǎn)度頂點(diǎn). 練習(xí)練習(xí)1證證 關(guān)鍵是利用握手定理的推論關(guān)鍵是利用握手定理的推論. 方法一：窮舉法方法一：窮舉法設(shè)設(shè)G中有中有x個(gè)個(gè)5度頂點(diǎn)，則必有度頂點(diǎn)，則必有(9 x)個(gè)個(gè)6度頂點(diǎn)，由握手定度頂點(diǎn)，由握手