離散數(shù)學(xué)第六章

1、第六章第六章 圖論圖論(1/2)I.圖的基本概念圖的基本概念 一無向圖與有向圖一無向圖與有向圖 1.無向圖的定義：一個無向圖是一個有序的二元無向圖的定義：一個無向圖是一個有序的二元組組,記作記作G，其中，其中（1）非空集）非空集V 稱為頂點(diǎn)集，其元素稱為頂點(diǎn)稱為頂點(diǎn)集，其元素稱為頂點(diǎn)或結(jié)點(diǎn)或結(jié)點(diǎn).（2）E稱為邊集，它是無序積稱為邊集，它是無序積V&V的多重子的多重子集，其元素稱為無向邊，簡稱邊集，其元素稱為無向邊，簡稱邊. 2.有向圖的定義：一個有向圖是一個有序的二元有向圖的定義：一個有向圖是一個有序的二元組組，記作，記作D，其中，其中 （1）V同無向圖同無向圖.（2）E為邊集，它是笛

2、卡兒積為邊集，它是笛卡兒積VV的多重子的多重子集，其元素稱為有向邊，簡稱邊集，其元素稱為有向邊，簡稱邊. 3. 例例: (1) 給定無向圖給定無向圖G=，其中，其中， V=v1,v2,v3,v4,v5E=(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v5). (2) 給定有向圖給定有向圖D=，其中，其中， V=a,b,c,d，E=,. 畫出畫出G與與D的圖形的圖形.解：解： 4.一些概念和規(guī)定一些概念和規(guī)定(1) n階圖階圖:在圖的定義中，用在圖的定義中，用G表示無向圖，表示無向圖，D表示有向圖，但有時用表示有向圖，但有時用G泛指圖泛指

3、圖(無向的或無向的或有向的有向的)，可是，可是D只能表示有向圖只能表示有向圖.另外，為另外，為方便起見，有時用方便起見，有時用V(G)，E(G)分別表示分別表示G的的頂點(diǎn)集和邊集，若頂點(diǎn)集和邊集，若|V(G)|=n,則稱則稱G為為n階圖，階圖，對有向圖可做類似規(guī)定對有向圖可做類似規(guī)定.(2)有限圖有限圖 : 若若|V(G)|與與|E(G)|均為有限數(shù)，則均為有限數(shù)，則稱稱G為有限圖為有限圖. (3) n階零圖與平凡圖階零圖與平凡圖 :在圖在圖G中，若邊集中，若邊集E(G)為空集為空集 ,則稱則稱G為零圖，此時，又若為零圖，此時，又若G為為n階階圖，則稱圖，則稱G為為n階零圖，記作階零圖，記作N

4、n，特別地，特別地，稱稱N1為平凡圖為平凡圖. （4）空圖：在圖的定義中規(guī)定頂點(diǎn)集）空圖：在圖的定義中規(guī)定頂點(diǎn)集V為非為非空集，但在圖的運(yùn)算中可能產(chǎn)生頂點(diǎn)集為空空集，但在圖的運(yùn)算中可能產(chǎn)生頂點(diǎn)集為空集的運(yùn)算結(jié)果，為此規(guī)定定點(diǎn)集為空集的圖集的運(yùn)算結(jié)果，為此規(guī)定定點(diǎn)集為空集的圖為空圖，并將空圖記為為空圖，并將空圖記為（5）關(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=為無向圖，為無向圖，ek=(vi，vj)E，則，則稱稱vi，vj為為ek的端點(diǎn)，的端點(diǎn)，ek與與vi或或ek與與vj是彼此相關(guān)是彼此相關(guān)聯(lián)的聯(lián)的.若若vivj，則稱，則稱ek與與vi或或ek與與vj的關(guān)聯(lián)次數(shù)為的關(guān)

5、聯(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，若，若vlvi且且vlvj，則稱，則稱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)中的環(huán).無論無論在無向圖中還是在有向圖中，無邊關(guān)聯(lián)的頂在無向圖中還是在有向圖中，無邊關(guān)聯(lián)的頂點(diǎn)均稱孤立點(diǎn)點(diǎn)均稱孤立點(diǎn). （6） 相鄰與鄰接相鄰與鄰接 ： 設(shè)無向圖設(shè)無向圖G=，vi，vjV，ek，elE.若若 etE，使得，使得et=（vi，vj），則稱），則稱vi與與vj是

6、相鄰的是相鄰的.若若ek與與el至少有一個公共端點(diǎn)，至少有一個公共端點(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相鄰相鄰. 二簡單圖與多重圖二簡單圖與多重圖 1.定義：在無向圖中，關(guān)聯(lián)一對頂點(diǎn)的無向邊如定義：在無向圖中，關(guān)聯(lián)一對頂點(diǎn)的無向邊如果多于果多于1條，則稱這些邊為平行邊，平行邊的條，則稱這些邊為平行邊，平行邊的條數(shù)稱為重數(shù)條數(shù)

7、稱為重數(shù).在有向圖中，關(guān)聯(lián)一對頂點(diǎn)的在有向圖中，關(guān)聯(lián)一對頂點(diǎn)的有向邊如果多于有向邊如果多于1條，并且這些邊的始點(diǎn)和終條，并且這些邊的始點(diǎn)和終點(diǎn)相同點(diǎn)相同(也就是它們的方向相同也就是它們的方向相同)，則稱這些邊，則稱這些邊為平行邊為平行邊.含平行邊的圖稱為多重圖，既不含含平行邊的圖稱為多重圖，既不含平行邊也不含環(huán)的圖稱為簡單圖平行邊也不含環(huán)的圖稱為簡單圖2.例：例：(1)中中e5與與e6是平是平行邊，在行邊，在(2)中，中，e2與與e3是平行邊，是平行邊，注意，注意，e6與與e7不不是平行邊是平行邊.(1)，(2)兩個圖都不是簡兩個圖都不是簡單圖單圖 三頂點(diǎn)的度數(shù)與握手定理三頂點(diǎn)的度數(shù)與握手定理

8、 1頂點(diǎn)的度數(shù)：頂點(diǎn)的度數(shù)： 設(shè)設(shè)G=為一無向圖，為一無向圖， vV，稱，稱v作為作為邊的端點(diǎn)次數(shù)之和為邊的端點(diǎn)次數(shù)之和為v的度數(shù)，簡稱為度，的度數(shù)，簡稱為度，記做記做 dG(v)，在不發(fā)生混淆時，簡記為，在不發(fā)生混淆時，簡記為d(v). 設(shè)設(shè)D=為有向圖，為有向圖， vV，稱，稱v作為邊作為邊的始點(diǎn)次數(shù)之和為的始點(diǎn)次數(shù)之和為v的出度，記做的出度，記做 (v),簡記簡記作作 (v).稱稱v作為邊的終點(diǎn)次數(shù)之和為作為邊的終點(diǎn)次數(shù)之和為v的入度，的入度，記做記做 (v)，簡記作，簡記作 (v)，稱，稱 (v)+ (v)為為v的度數(shù)，記做的度數(shù)，記做d(v). DddDdddd證：證： G中每條邊中

9、每條邊(包括環(huán)包括環(huán))均有兩個端點(diǎn)，所均有兩個端點(diǎn)，所以在計算以在計算G中各頂點(diǎn)度數(shù)之和時，每條邊均中各頂點(diǎn)度數(shù)之和時，每條邊均提供提供2度，當(dāng)然，度，當(dāng)然，m條邊，共提供條邊，共提供2m度度. 2握手定理握手定理 定理定理1 (握手定理握手定理) 設(shè)設(shè)G=為任意無向?yàn)槿我鉄o向圖，圖，V=v1,v2,vn，|E|=m，則，則 =2m 1niid v 定理定理2(握手定理握手定理) 設(shè)設(shè)D=為任意有向圖，為任意有向圖，V=v1,v2,vn，|E|=m，則，則 =2m，且且 = =m. 1niid v 1niidv 1niidv握手定理的推論：握手定理的推論： 任何圖任何圖(無向的或有向的無向的或

10、有向的)中，中，奇度頂點(diǎn)的個數(shù)是偶數(shù)奇度頂點(diǎn)的個數(shù)是偶數(shù). 證：證： 設(shè)設(shè)G=為任意一圖，令為任意一圖，令 V1=v|vVd(v)為奇數(shù)為奇數(shù) V2=v|vVd(v)為偶數(shù)為偶數(shù) 則則V1V2=V，V1V2= ，由握手定理可知，由握手定理可知 2m= = + 由于由于2m， 均為偶數(shù)，所以均為偶數(shù)，所以 為為偶數(shù)，但因偶數(shù)，但因V1中頂點(diǎn)的度數(shù)為奇數(shù)，所以中頂點(diǎn)的度數(shù)為奇數(shù)，所以|V1|必為偶數(shù)必為偶數(shù). v Vd v 2v Vd v 1v Vd v 2v Vd v 1v Vd v3.頂點(diǎn)度數(shù)有關(guān)的概念頂點(diǎn)度數(shù)有關(guān)的概念（1）無向圖）無向圖G中的最大度和最小度中的最大度和最小度: 在無向圖在無

11、向圖G中，令中，令 (G)=maxd(v)|vV(G) (G)=mind(v)|vV(G)稱稱(G)，(G)分別為分別為G的最大度的最大度 和最小度和最小度. 在不引起混淆的情況下，將在不引起混淆的情況下，將(G)，(G)分分別簡記為別簡記為和和. (2) 有向圖有向圖D中的最大度、最大出度、最大入中的最大度、最大出度、最大入度與最小度、最小出度、最小入度度與最小度、最小出度、最小入度: 在有向圖在有向圖D中，類似無向圖，可以定義最大中，類似無向圖，可以定義最大度度(D)，最小度，最小度(D)，另外，令，另外，令 + (D)=maxd- -(v)|vV(D) + (D)=min d+ (v)|

12、vV(D) - - (D)=maxd- -(v)|vV(D) - - (D)=mind- -(v)|vV(D)分別稱為分別稱為D的最大出度，最小出度，的最大出度，最小出度， 最大最大入度，最小入度入度，最小入度. 以上記號可分別簡記為以上記號可分別簡記為 ，+ ， + ， - - ， - -.(3) 懸掛頂點(diǎn)與懸掛邊懸掛頂點(diǎn)與懸掛邊;奇度頂點(diǎn)與偶度頂點(diǎn)奇度頂點(diǎn)與偶度頂點(diǎn): 稱度數(shù)稱度數(shù)為為1的頂點(diǎn)為懸掛頂點(diǎn)，與它關(guān)聯(lián)的邊稱為懸掛邊的頂點(diǎn)為懸掛頂點(diǎn)，與它關(guān)聯(lián)的邊稱為懸掛邊.度為偶數(shù)度為偶數(shù)(奇數(shù)奇數(shù))的頂點(diǎn)稱為偶度的頂點(diǎn)稱為偶度(奇度奇度)頂點(diǎn)頂點(diǎn).(4)例：例：#15. 幻燈片幻燈片 15 (

13、1)的的d(v1)=4(注意注意, 環(huán)提環(huán)提供供2度度), = 4, = 1,v4是懸掛頂點(diǎn)，是懸掛頂點(diǎn)，e7是懸掛是懸掛邊邊.(2)的的d+ +(a)=4d- -(a)=1(環(huán)環(huán)e1提供出度提供出度1, 提供入提供入度度1), d(a)=4+1=5.=5，=3, + +=4 (在在a點(diǎn)達(dá)到點(diǎn)達(dá)到), + +=0(在在b點(diǎn)達(dá)到點(diǎn)達(dá)到), - -=3(在在b點(diǎn)達(dá)到點(diǎn)達(dá)到)，- -=1(在在a和和c點(diǎn)達(dá)到點(diǎn)達(dá)到). （5）度數(shù)列：）度數(shù)列： 設(shè)設(shè)G=為一個為一個n階無向圖階無向圖,V=v1,v2,vn,稱稱d(v1),d(v2),d(vn)為為G的度數(shù)列，對于頂點(diǎn)的度數(shù)列，對于頂點(diǎn)標(biāo)定的無向圖，它

14、的度數(shù)列是唯一的標(biāo)定的無向圖，它的度數(shù)列是唯一的. 設(shè)設(shè)D=為一個為一個n階有向圖，階有向圖，V=v1,v2,vn，稱，稱d(v1),d(v2),d(vn)為為D的度的度數(shù)列，另外稱數(shù)列，另外稱d+ (v1), d+ (v2), d+ (vn)與與d- - (v1), d- -(v2), d- -(vn)分別為分別為D的出度列和入度列的出度列和入度列.如：如：#14. 幻燈片幻燈片 14 (1)中，按頂點(diǎn)的標(biāo)定順序，中，按頂點(diǎn)的標(biāo)定順序，度數(shù)列為度數(shù)列為4,4,2,1,3.在在(2)中，中，按字母順序，度數(shù)列，出按字母順序，度數(shù)列，出度列，入度列分別為度列，入度列分別為5,3,3,3；4,0,

15、2,1；1,3,1,2. （6）可圖化的與可簡單圖化的非負(fù)整數(shù)列：）可圖化的與可簡單圖化的非負(fù)整數(shù)列：1）對于給定的非負(fù)整數(shù)列）對于給定的非負(fù)整數(shù)列d=(d1,d2, ,dn),若存若存在以在以V=v1,v2,vn為頂點(diǎn)集的為頂點(diǎn)集的n階無向圖階無向圖G,使使得得d(vi)=di,則稱則稱d是可圖化的是可圖化的.特別地特別地,若所得圖若所得圖是簡單圖是簡單圖,則稱則稱d是可簡單圖化的是可簡單圖化的. 2）判別定理）判別定理: 設(shè)非負(fù)整數(shù)列設(shè)非負(fù)整數(shù)列d=(d1,d2,dn)，則則d是可圖化的當(dāng)且僅當(dāng)是可圖化的當(dāng)且僅當(dāng) 0(mod 2).3）例）例: (3，3，2，1),(3，2，2，1，1)等

16、是不等是不可圖化的可圖化的,而而(3，3，2，2),(3，2，2，2，1)等等是可圖化的是可圖化的. 1niid4）簡單圖定理：）簡單圖定理： 設(shè)設(shè)G為任意為任意n階無向簡單圖，階無向簡單圖，則則(G)n- -1. 證：證： 因?yàn)橐驗(yàn)镚既無既無平行邊平行邊也無也無環(huán)環(huán)，所以，所以G中任中任何頂點(diǎn)何頂點(diǎn)v至多與其余的至多與其余的n- -1個頂點(diǎn)均相鄰，于個頂點(diǎn)均相鄰，于是是d(v)n- -1，由于，由于v的任意性，所以的任意性，所以(G)n- -1. 5）判斷下列各非負(fù)整數(shù)列哪些是）判斷下列各非負(fù)整數(shù)列哪些是可圖化的可圖化的？哪？哪些是些是可簡單圖化的可簡單圖化的？1) (5,5,4,4,2,1

17、)；2) (5,4,3,2,2)；3) (3,3,3,1)；4) (d1,d2,dn)，d1d2dn1 且且 為偶數(shù)為偶數(shù)5) (4,4,3,3,2,2).1niid解解 ：易知，除：易知，除(1)中序列不可圖化外，其余各序列都可中序列不可圖化外，其余各序列都可圖化圖化.但除了但除了(5)中序列外，其余的都是不可簡單圖化的中序列外，其余的都是不可簡單圖化的. (2)中序列有中序列有5個數(shù)，若它可簡單圖化，設(shè)所得圖為個數(shù)，若它可簡單圖化，設(shè)所得圖為G，則則(G)=max5,4,3,2,2=5，這與簡單圖定理矛盾，這與簡單圖定理矛盾.所以所以(2)中序列不可簡單圖化中序列不可簡單圖化.類似可證類似

18、可證(4)中序列不可簡單圖化中序列不可簡單圖化.假設(shè)假設(shè)(3)中序列可以簡單圖化，設(shè)中序列可以簡單圖化，設(shè)G=以以(3)中序列中序列為度數(shù)列為度數(shù)列.不妨設(shè)不妨設(shè)V=v1，v2，v3，v4 且且 d(v1)=d(v2)=d(v3)=3,d(v4)=1，由于，由于d(v4)1，因而，因而v4只能只能與與v1，v2，v3之一相鄰，于是之一相鄰，于是v1，v2，v3不可能都是不可能都是3度度頂點(diǎn)，這是矛盾的，因而頂點(diǎn)，這是矛盾的，因而(3)中序列也不可簡單圖化中序列也不可簡單圖化. (5)中序列是可簡單圖化的，下圖中兩個中序列是可簡單圖化的，下圖中兩個6階無向簡單圖階無向簡單圖都以都以(5)中序列為

19、度數(shù)列中序列為度數(shù)列. 四圖的同構(gòu)四圖的同構(gòu) 1.兩圖同構(gòu)的定義兩圖同構(gòu)的定義 ： 設(shè)設(shè)G1=，G2=為兩個無向圖為兩個無向圖(兩個有向圖兩個有向圖)，若存，若存在在雙射函數(shù)雙射函數(shù)f：V1V2，對于，對于 vi，vj V1，(vi，vj)E1(E1)當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)(f(vi)，f(vj)E2(E2)，并且，并且(vi，vj)()與與(f(vi)，f(vj)()的重數(shù)相同，則稱的重數(shù)相同，則稱G1與與G2是同構(gòu)的，記做是同構(gòu)的，記做G1 G2 .2.例例:(1)為彼得松為彼得松(Petersen)圖，圖，(2)，(3)均與均與(1)同構(gòu)同構(gòu).(4)，(5)，(6)各圖彼此間都不同構(gòu)各圖彼此間

20、都不同構(gòu). 五完全圖與正則圖五完全圖與正則圖 1 完全圖完全圖 設(shè)設(shè)G為為n階無向階無向簡單圖簡單圖，若，若G中每個中每個頂點(diǎn)均與其余的頂點(diǎn)均與其余的n- -1個頂點(diǎn)相鄰，個頂點(diǎn)相鄰， 則稱則稱G為為n階階無向完全圖，簡稱無向完全圖，簡稱n階完全圖，記做階完全圖，記做Kn(n1). 設(shè)設(shè)D為為n階有向簡單圖，若階有向簡單圖，若D中每個頂點(diǎn)都中每個頂點(diǎn)都鄰接到其余的鄰接到其余的n- -1個頂點(diǎn)，又鄰接于其余的個頂點(diǎn)，又鄰接于其余的n- -1個頂點(diǎn)，個頂點(diǎn)， 則稱則稱D是是n階有向完全圖階有向完全圖. 設(shè)設(shè)D為為n階有向簡單圖，若階有向簡單圖，若D的基圖為的基圖為n階無階無向完全圖向完全圖Kn ，

21、則稱，則稱D是是n階競賽圖階競賽圖. 2.例：例：(1)為為K5，(2)為為3階有向完全圖，階有向完全圖，(3)為為4階階競賽圖競賽圖.易知，易知，n階無向完全圖，階無向完全圖，n階有向完全階有向完全圖，圖，n階競賽圖的邊數(shù)分別為階競賽圖的邊數(shù)分別為 n(n- -1)/2，n(n1)，n(n-1)/2. 3正則圖正則圖 ： 設(shè)設(shè)G為為n階無向簡單圖，若階無向簡單圖，若 vV(G)，均有，均有d(v)=k，則稱，則稱G為為k-正則圖正則圖. 4.注：注：n階零圖是階零圖是0-正則圖，正則圖，n階無向完全圖階無向完全圖是是(n-1)正則圖，彼得松圖是正則圖，彼得松圖是3-正則圖正則圖. 由由握手定

22、理握手定理可知，可知，n階階k-正則圖中，邊數(shù)正則圖中，邊數(shù)m=kn/2，因而當(dāng)，因而當(dāng)k為奇數(shù)時，為奇數(shù)時，n必為偶數(shù)必為偶數(shù). 六子圖與補(bǔ)圖六子圖與補(bǔ)圖 1子圖子圖 :設(shè)設(shè)G=, G=為兩個為兩個圖圖(同為無向圖或同為有向圖同為無向圖或同為有向圖), 若若V V且且E E,則稱則稱G是是G的的子圖子圖, G為為G的的母圖母圖，記作，記作G G. 又若又若V V或或E E, 則稱則稱G為為G的真子圖的真子圖.若若V=V, 則稱則稱G為為G的的生成子圖生成子圖. 設(shè)設(shè)G=為一圖為一圖, V1 V且且V1 , 稱以稱以V1為頂點(diǎn)集為頂點(diǎn)集, 以以G中兩個端點(diǎn)都在中兩個端點(diǎn)都在V1中的邊組成邊中的

23、邊組成邊集集E1的圖為的圖為G的的V1導(dǎo)出的子圖導(dǎo)出的子圖, 記作記作GV1. 又設(shè)又設(shè)E1 E且且E1 , 稱以稱以E1為邊集為邊集, 以以E1中邊關(guān)聯(lián)的頂點(diǎn)中邊關(guān)聯(lián)的頂點(diǎn)為頂點(diǎn)集為頂點(diǎn)集V1的圖為的圖為G的的E1導(dǎo)出的子圖導(dǎo)出的子圖, 記作記作GE1. 2.例：設(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)中圖所示中圖所示. 2補(bǔ)圖與自補(bǔ)圖補(bǔ)圖與自補(bǔ)圖 設(shè)設(shè)G=為為n階無向簡單圖，以階無向簡單圖，以V為頂點(diǎn)為頂點(diǎn)集，以所有使集，以所有使G成

24、為成為完全圖完全圖Kn的添加邊組成的的添加邊組成的集合為邊集的圖，稱為集合為邊集的圖，稱為G的的補(bǔ)圖補(bǔ)圖，記做，記做 . 若圖若圖 , 則稱則稱G是是自補(bǔ)圖自補(bǔ)圖. GGGII.通路與回路通路與回路一通路與回路的定義一通路與回路的定義 定義定義: 設(shè)設(shè)G為無向標(biāo)定圖，為無向標(biāo)定圖，G中頂點(diǎn)與邊的中頂點(diǎn)與邊的交替序列交替序列=v0e1v1e2elvl 稱為稱為v0 到到vl 的通路，的通路，其中其中vr-1 ，vr 為為er 的端點(diǎn)，的端點(diǎn)，r=1，2，l，v0 ，vl 分別稱為分別稱為的始點(diǎn)與終點(diǎn)，的始點(diǎn)與終點(diǎn)，中邊的中邊的條數(shù)稱為它的長度條數(shù)稱為它的長度.若若v0=vl ，則稱通路為回，則稱

25、通路為回路路. 若若的所有邊各異，則稱的所有邊各異，則稱為簡單通路，為簡單通路，又若又若v0=vl ，則稱，則稱為簡單回路為簡單回路.若若的所有頂?shù)乃许旤c(diǎn)點(diǎn)(除除 v0與與vl 可能相同外可能相同外)各異，所有邊也各各異，所有邊也各異，則稱異，則稱為初級通路或路徑，此時又若為初級通路或路徑，此時又若 v0=vl，則稱，則稱為初級回路或圈為初級回路或圈.將長度為奇數(shù)將長度為奇數(shù)的圈稱為奇圈，長度為偶數(shù)的圈稱為偶圈的圈稱為奇圈，長度為偶數(shù)的圈稱為偶圈. 注意，在初級通路與初級回路的定義中，注意，在初級通路與初級回路的定義中，仍將初級回路看成初級通路仍將初級回路看成初級通路(路徑路徑)的特殊情的特

26、殊情況，只是在應(yīng)用中初級通路況，只是在應(yīng)用中初級通路(路徑路徑)都是始點(diǎn)都是始點(diǎn)與終點(diǎn)不相同的，長為與終點(diǎn)不相同的，長為1的圈只能由環(huán)生成，的圈只能由環(huán)生成，長為長為2的圈只能由平行邊生成，因而在簡單的圈只能由平行邊生成，因而在簡單無向圖中，圈的長度至少為無向圖中，圈的長度至少為3. 另外，若另外，若中有邊重復(fù)出現(xiàn)，則稱中有邊重復(fù)出現(xiàn)，則稱為復(fù)為復(fù)雜通路，又若雜通路，又若 v0=vl，則稱，則稱為復(fù)雜回路為復(fù)雜回路.二二. n階圖中通路與回路的性質(zhì)階圖中通路與回路的性質(zhì) 定理定理1. 在在n階圖階圖G中中, 若從頂點(diǎn)若從頂點(diǎn)vi到到vj（vivj）存）存在通路在通路, 則從則從vi到到vj存在

27、長度小于或等于存在長度小于或等于 （n- -1）的通路）的通路. 證：設(shè)證：設(shè)=v0e1v1e2elvl（v0=vi,vl=vj）為）為G中一條長度為中一條長度為l的通路的通路, 若若ln- -1, 則則滿足要求，滿足要求，否則必有否則必有l(wèi)+1n, 即即上的頂點(diǎn)數(shù)大于上的頂點(diǎn)數(shù)大于G中的頂中的頂點(diǎn)數(shù)點(diǎn)數(shù), 于是必存在于是必存在k,s,0ksl,使得使得vs=vk,即在即在上存在上存在vs到自身的回路到自身的回路Csk,在在上刪除上刪除Csk上的上的一切邊及除一切邊及除vs外的一切頂點(diǎn)外的一切頂點(diǎn), 得得= v0e1v1e2vkes+1 elvl, 仍為仍為vi到到vj的通路的通路, 且且長度

28、至少比長度至少比減少減少1.若若還不滿足要求還不滿足要求, 則重復(fù)則重復(fù)上述過程上述過程, 由于由于G是有限圖是有限圖, 經(jīng)過有限步后經(jīng)過有限步后, 必必得到得到vi到到vj長度小于或等于長度小于或等于n- -1的通路的通路. 推論推論 在在n階圖階圖G中，若從頂點(diǎn)中，若從頂點(diǎn)vi到到vj（vivj）存在）存在通路，則通路，則vi到到vj一定存在長度小于或等于一定存在長度小于或等于n- -1的初的初級通路（路徑）級通路（路徑）. 定理定理2.在一個在一個n階圖階圖G中，若存在中，若存在vi到自身的回路，到自身的回路，則一定存在則一定存在vi到自身長度小于或等于到自身長度小于或等于n的回路的回路

29、. 推論推論. 在一個在一個n階圖階圖G中，若存在中，若存在vi到自身的簡單到自身的簡單回路，則一定存在回路，則一定存在vi到自身長度小于或等于到自身長度小于或等于n的的初級回路初級回路. III. 圖的連通性圖的連通性 一、無向圖的連通性一、無向圖的連通性 1.定義定義: 1）設(shè)無向圖）設(shè)無向圖G=, 任意任意u,vV，若，若u,v之之間存在通路，則稱間存在通路，則稱u,v是連通的，記作是連通的，記作uv. vV，規(guī)定，規(guī)定vv.2）若無向圖）若無向圖G是平凡圖或是平凡圖或G中任何兩個頂點(diǎn)中任何兩個頂點(diǎn)都是連通的，則稱都是連通的，則稱G為連通圖，否則稱為連通圖，否則稱G是是非連通圖或分離圖非

30、連通圖或分離圖. 2.無向圖中頂點(diǎn)之間的連通關(guān)系無向圖中頂點(diǎn)之間的連通關(guān)系 =（u,v）|u,vV且且u與與v之間有通路之間有通路是自反的，對稱的，傳遞的，因而是自反的，對稱的，傳遞的，因而是是V上的上的等價關(guān)系等價關(guān)系.3.連通分支的定義：設(shè)無向圖連通分支的定義：設(shè)無向圖G=，V關(guān)于關(guān)于頂點(diǎn)之間的連通關(guān)系頂點(diǎn)之間的連通關(guān)系的的商集商集V/=V1,V2,Vk，Vi為為等價類等價類，稱，稱導(dǎo)出子圖導(dǎo)出子圖GVi(i=1,2,k)為為G的連通分支，連通分支數(shù)的連通分支，連通分支數(shù)k常記為常記為p(G).4.例：若例：若G為連通圖，則為連通圖，則p(G)=1，若，若G為非連通為非連通圖，則圖，則p(

31、G)2，在所有的，在所有的n階無向圖中，階無向圖中，n階零階零圖是連通分支最多的，圖是連通分支最多的，p(Nn)= n二、無向圖中頂點(diǎn)之間的短程線及距離二、無向圖中頂點(diǎn)之間的短程線及距離1.定義：設(shè)定義：設(shè)u,v為無向圖為無向圖G中任意兩個頂點(diǎn)，若中任意兩個頂點(diǎn)，若 u v，稱，稱u,v之間長度最短的通路為之間長度最短的通路為u,v之間之間 的短程線，短程線的長度稱為的短程線，短程線的長度稱為u,v之間的距離之間的距離 記作記作d(u,v).當(dāng)當(dāng)u,v不連通時，規(guī)定不連通時，規(guī)定d(u,v)=. 2. 性質(zhì)性質(zhì): (1) d(u,v)0，u=v時，等號成立時，等號成立. (2)具有對稱性，具有

32、對稱性，d(u,v)=d(v,u). (3)滿足三角不等式：滿足三角不等式： u,v,wV(G)，則，則 d(u,v)+d(v,w)d(u,w) 三三.有向圖的連通性有向圖的連通性1.定義：設(shè)定義：設(shè)D=為一個有向圖，任意為一個有向圖，任意vi,vjV，若從，若從vi到到vj存在通路，則稱存在通路，則稱vi可達(dá)可達(dá)vj，記作，記作vivj，規(guī)定，規(guī)定vi總是可達(dá)自身的，即總是可達(dá)自身的，即vivi.若若vivj且且vjvi，則稱，則稱vi與與vj是相互可是相互可達(dá)的，記作達(dá)的，記作vi vj.規(guī)定規(guī)定vi vi. 2.距離：設(shè)距離：設(shè)D=為有向圖，為有向圖， vi,vjV，若，若vivj，稱，

33、稱vi到到vj長度最短的通路為長度最短的通路為vi到到vj的短的短程線，短程線的長度為程線，短程線的長度為vi到到vj的距離，記作的距離，記作d. 3.分類：設(shè)分類：設(shè)D=為一個有向圖為一個有向圖.若若D的的基圖基圖是連通圖，則稱是連通圖，則稱D是弱連通圖，簡稱為連通圖是弱連通圖，簡稱為連通圖.若任意若任意 vi,vjV ，vivj與與vjvi至少成立其一，至少成立其一，則稱則稱D是單向連通圖是單向連通圖.若均有若均有vi vj，則，則稱稱D是強(qiáng)連通圖是強(qiáng)連通圖.4.例：例： （1）為強(qiáng)連通圖，（2）為單連通圖，（3）是弱連通圖.由定義可知，強(qiáng)連通圖一定是單向連通圖，單向連通圖一定是弱連通圖.

34、 IV.圖的矩陣表示圖的矩陣表示一一.無向圖與有向圖的關(guān)聯(lián)矩陣無向圖與有向圖的關(guān)聯(lián)矩陣 1.無向圖的關(guān)聯(lián)矩陣無向圖的關(guān)聯(lián)矩陣: 設(shè)無向圖設(shè)無向圖G=，V=v1,v2,vn，E=e1,e2,em，令，令mij為頂為頂點(diǎn)點(diǎn)vi與邊與邊ej的關(guān)聯(lián)次數(shù)，則稱的關(guān)聯(lián)次數(shù)，則稱(mij)nm為為G的的關(guān)聯(lián)矩陣，記作關(guān)聯(lián)矩陣，記作M(G). 2.例：例：M(G)= 3.M（G）的性質(zhì)：）的性質(zhì)：1） mij=2(j=1,2,m)即即M(G)每列元素之和均為每列元素之和均為2，這正說明每條邊關(guān)聯(lián)兩個頂點(diǎn)（環(huán)所關(guān)聯(lián)的，這正說明每條邊關(guān)聯(lián)兩個頂點(diǎn)（環(huán)所關(guān)聯(lián)的兩個端點(diǎn)重合）兩個端點(diǎn)重合）.2） mij =d(vi)

35、，即，即M(G)第第i行元素之和為行元素之和為vi的度的度數(shù)，數(shù)，i=1,2,n. 3） d(vi)= mij= mij= 2=2m,這個結(jié)果正這個結(jié)果正是是握手定理握手定理的內(nèi)容，即各頂點(diǎn)的度數(shù)之和等于的內(nèi)容，即各頂點(diǎn)的度數(shù)之和等于邊數(shù)的邊數(shù)的2倍倍. 4）第）第j列與第列與第k行相同，當(dāng)且僅當(dāng)邊行相同，當(dāng)且僅當(dāng)邊ej與與ek是是平行平行邊邊. 5） mij=0當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)vi是是孤立點(diǎn)孤立點(diǎn). 1mj 1ni 1ni 1ni 1mj 1mj 1ni 1mj 1mj 4.有向圖的關(guān)聯(lián)矩陣有向圖的關(guān)聯(lián)矩陣:設(shè)有向圖設(shè)有向圖D=中無環(huán)，中無環(huán)，V=v1,v2,vn，E=e1,e2,em,令令

36、 mij= 則稱則稱(mij)nm為為D的關(guān)聯(lián)矩陣，記作的關(guān)聯(lián)矩陣，記作M(D). 5.例：例：M(D)= 6.M(D)的性質(zhì)：的性質(zhì)： (1) mij=0，j=1,2,m，從而，從而 mij =0，這說明這說明M(D)中所有元素之和為中所有元素之和為0. (2)M(D)中，負(fù)中，負(fù)1的個數(shù)等于正的個數(shù)等于正1的個數(shù)，都的個數(shù)，都等于邊數(shù)等于邊數(shù)m，這正是有向圖握手定理的內(nèi)容，這正是有向圖握手定理的內(nèi)容. (3)第第i行中，正行中，正1的個數(shù)等于的個數(shù)等于d+(vi)，負(fù)，負(fù)1的個的個數(shù)等于數(shù)等于d- -(vi). (4) 平行邊所對應(yīng)的列相同平行邊所對應(yīng)的列相同. 1ni1mj1ni二二.有

37、向圖的鄰接矩陣有向圖的鄰接矩陣1.設(shè)有向圖設(shè)有向圖D=，V=v1,v2,vn，E=e1,e2,，em，令，令aij為頂點(diǎn)為頂點(diǎn)vi鄰接到頂點(diǎn)鄰接到頂點(diǎn)vj邊的條數(shù)，稱邊的條數(shù)，稱(aij)nn為為D的鄰接矩陣，記的鄰接矩陣，記作作A(D)，或簡記為，或簡記為A. 2.例：例： A 3.性質(zhì)：性質(zhì)：（1）設(shè)）設(shè)A為有向圖為有向圖D的鄰接矩陣，的鄰接矩陣， V=v1,v2,vn為為D的頂點(diǎn)集的頂點(diǎn)集,則則A的的l次冪次冪Al（l1）中元素）中元素aij(l)為為D中中vi到到vj長度為長度為l的通路的通路 數(shù)數(shù),其中其中aii(l) 為為vi到自身長度為到自身長度為l的回路數(shù)的回路數(shù),而而aij(

38、l) 為為D中長度為中長度為l的通路總數(shù)的通路總數(shù),其中其中 aii(l) 為為D中中長度為長度為l的回路總數(shù)的回路總數(shù). （2）設(shè)）設(shè)Bl=A+A2+Al（l1）,則則Bl中元素中元素 bij(l)為為D中長度小于或等于中長度小于或等于l的通路數(shù)的通路數(shù), 其中其中 bii(l)為為D中長度小于或等于中長度小于或等于l的回路數(shù)的回路數(shù).1nj 1ni1ni 1ni1nj 1 2 0 00 0 1 0( )1 0 0 10 0 1 0A G2341解：解：2341200120012200010001010011001100112100010001010013222564212102221222

39、1443212102221AAA4. 例：例： 求圖求圖G）的鄰接矩陣）的鄰接矩陣. 所以，由所以，由v1到到v3長度為長度為1、2、3、4的通路分別有的通路分別有0、2、2、4條，條，G中中共有長度為共有長度為4的通路的通路44條，其中回條，其中回路路11條，長度小于等于條，長度小于等于4的通路共的通路共有有88條，其中回路條，其中回路22條條.三三.有向圖的可達(dá)矩陣有向圖的可達(dá)矩陣1.定義：定義： 設(shè)設(shè)G=V,E是一有向圖，是一有向圖， V=v1，v2，vn，令，令10ijpvi可達(dá)可達(dá)vj 否則否則 稱（稱（p ij ） nn 為為G的可達(dá)矩陣，記作的可達(dá)矩陣，記作 P （G）.2 例例

40、.記下圖可達(dá)矩陣為記下圖可達(dá)矩陣為 P （G），則），則 1 1 1 11 1 1 1( )1 1 1 11 1 1 1P G2341一些特殊圖一些特殊圖一一.二部圖二部圖1.定義定義: 設(shè)設(shè)G=為一個無向圖，若能將為一個無向圖，若能將V分成分成V1和和V2（V1V2=V,V1V2= ），使得），使得G中的每條邊的兩個端點(diǎn)都是一個屬于中的每條邊的兩個端點(diǎn)都是一個屬于V1，另一個屬于另一個屬于V2，則稱，則稱G為二部圖（或稱二分為二部圖（或稱二分圖，偶圖等），稱圖，偶圖等），稱V1和和V2為互補(bǔ)頂點(diǎn)子集，為互補(bǔ)頂點(diǎn)子集，常將二部圖常將二部圖G記為記為.又若又若G是簡單是簡單二部圖，二部圖，V1中

41、每個頂點(diǎn)均與中每個頂點(diǎn)均與V2中所有頂點(diǎn)相中所有頂點(diǎn)相鄰，則稱鄰，則稱G為完全二部圖，記為為完全二部圖，記為Kr,s，其中，其中r=|V1|,s=|V2|. 2.例例:在左圖所示各圖在左圖所示各圖都是二部圖，其中，都是二部圖，其中，(1)，(2)，(3)為為K6的的子圖，子圖，(3)為完全二為完全二部圖部圖K3,3，常將，常將K3,3畫成與其同構(gòu)的畫成與其同構(gòu)的(5)的形式，的形式，K3,3是經(jīng)常是經(jīng)常遇到的圖遇到的圖.(4)是是K5的的子圖，它是完全二子圖，它是完全二部圖部圖K2,3，K2,3常畫常畫成成(6)的形式的形式. 3.定理定理: 一個無向圖一個無向圖G=V , E是二部圖當(dāng)且是二

42、部圖當(dāng)且僅當(dāng)僅當(dāng)G中無奇數(shù)長度的回路中無奇數(shù)長度的回路. 二二.歐拉圖歐拉圖1.定義定義: 通過圖（無向圖或有向圖）中所有邊通過圖（無向圖或有向圖）中所有邊一次且僅一次行遍圖中所有頂點(diǎn)的通路稱一次且僅一次行遍圖中所有頂點(diǎn)的通路稱為歐拉通路，通過圖中所有邊一次并且僅為歐拉通路，通過圖中所有邊一次并且僅一次行遍所有頂點(diǎn)的回路稱為歐拉回路一次行遍所有頂點(diǎn)的回路稱為歐拉回路.具具有歐拉回路的圖稱為歐拉圖，具有歐拉通有歐拉回路的圖稱為歐拉圖，具有歐拉通路而無歐拉回路的圖稱為半歐拉圖路而無歐拉回路的圖稱為半歐拉圖.2.例例: e1e2e3e4e5為（為（1）中的歐拉回路，所以（）中的歐拉回路，所以（1）圖

43、為歐拉圖圖為歐拉圖.e1e2e3e4e5為（為（2）中的一條歐拉通路，）中的一條歐拉通路，但圖中不存在歐拉回路，所以（但圖中不存在歐拉回路，所以（2）為半歐拉圖）為半歐拉圖.（3）中既沒有歐拉回路，也沒有歐拉通路）中既沒有歐拉回路，也沒有歐拉通路,所以所以（3）不是歐拉圖，也不是半歐拉圖）不是歐拉圖，也不是半歐拉圖.e1e2e3e4為為（4）圖中的歐拉回路，所以（）圖中的歐拉回路，所以（4）圖為歐拉圖）圖為歐拉圖.（5），（），（6）圖中都既沒有歐拉回路，也沒有歐）圖中都既沒有歐拉回路，也沒有歐拉通路（為什么？）拉通路（為什么？） 3.判別定理判別定理 :無向圖無向圖G是歐拉圖當(dāng)且僅當(dāng)是歐拉圖

44、當(dāng)且僅當(dāng)G是連通圖，且是連通圖，且G中沒有奇度頂點(diǎn)中沒有奇度頂點(diǎn).無向圖無向圖G是半歐拉圖當(dāng)且僅當(dāng)是半歐拉圖當(dāng)且僅當(dāng)G是連通的，是連通的，且且G中恰有兩個奇度頂點(diǎn)中恰有兩個奇度頂點(diǎn). 有向圖有向圖D是歐拉圖當(dāng)且僅當(dāng)是歐拉圖當(dāng)且僅當(dāng)D是強(qiáng)連通的且是強(qiáng)連通的且每個頂點(diǎn)的入度都等于出度每個頂點(diǎn)的入度都等于出度. 1) 有向圖有向圖D是半歐拉圖當(dāng)且僅當(dāng)是半歐拉圖當(dāng)且僅當(dāng)D是是單向連通單向連通的，且的，且D中恰有兩個奇度頂點(diǎn)，其中一個的中恰有兩個奇度頂點(diǎn)，其中一個的入度比出度大入度比出度大1，另一個的出度比入度大，另一個的出度比入度大1，而其余頂點(diǎn)的入度都等于出度而其余頂點(diǎn)的入度都等于出度. 三三.哈密

45、頓圖哈密頓圖 1.定義定義: 經(jīng)過圖（有向圖或無向圖）中所有頂經(jīng)過圖（有向圖或無向圖）中所有頂點(diǎn)一次且僅一次的通路稱為哈密頓通路點(diǎn)一次且僅一次的通路稱為哈密頓通路.經(jīng)經(jīng)過圖中所有頂點(diǎn)一次且僅一次的回路稱為過圖中所有頂點(diǎn)一次且僅一次的回路稱為哈密頓回路哈密頓回路.具有哈密頓回路的圖稱為哈密具有哈密頓回路的圖稱為哈密頓圖，具有哈密頓通路但不具有哈密頓回頓圖，具有哈密頓通路但不具有哈密頓回路的圖稱為半哈密頓圖路的圖稱為半哈密頓圖.平凡圖平凡圖是哈密頓圖是哈密頓圖. 2.例例: 三個無向圖都有哈密頓回路，所以都是哈三個無向圖都有哈密頓回路，所以都是哈密頓圖密頓圖.有向圖中，（有向圖中，（4）具有哈密頓

46、回路，因）具有哈密頓回路，因而它是哈密頓圖而它是哈密頓圖.（5）只有哈密頓通路，但無）只有哈密頓通路，但無哈密頓回路，因而它是半哈密頓圖，而（哈密頓回路，因而它是半哈密頓圖，而（6）中既無哈密頓回路，也沒有哈密頓通路，因而中既無哈密頓回路，也沒有哈密頓通路，因而不是哈密頓圖，也不是半哈密頓圖不是哈密頓圖，也不是半哈密頓圖. 4.例例1:三個圖都是三個圖都是二部圖二部圖.它們中的那些是哈它們中的那些是哈密頓圖？哪些是半哈密頓圖？為什么？密頓圖？哪些是半哈密頓圖？為什么？ 3.哈密頓圖與半哈密頓圖的一些必要與充分哈密頓圖與半哈密頓圖的一些必要與充分條件條件 定理定理1. 設(shè)無向圖設(shè)無向圖G=是哈密

47、頓圖，對是哈密頓圖，對于任意非空于任意非空V1包含于包含于V,均有均有 p(G-V1)|V1| 其中，其中，p(G- -V1)為為G- -V1的的連通分支數(shù)連通分支數(shù). 定理定理2.設(shè)無向圖設(shè)無向圖G=是半哈密頓圖，是半哈密頓圖，對于任意非空對于任意非空V1包含于包含于V,均有均有 p(G- -V1)|V1|+1 解：解： 在（在（1）中）中,易知互補(bǔ)頂點(diǎn)子集易知互補(bǔ)頂點(diǎn)子集V1=a,f,V2=b,c,d,e.設(shè)此二部圖為設(shè)此二部圖為G1，則，則G1=. p(G1- -V1)=4|V1|=2，G1不是哈密不是哈密頓圖，也不是半哈密頓圖頓圖，也不是半哈密頓圖. 設(shè)（設(shè)（2）中圖為）中圖為G2，則

48、，則G2=，其中其中V1=a,g,h,i,c，V2=b,e,f,j,k,d，易知，易知，p(G2-V1)=|V2|=6|V1|=5，G2不是哈密頓圖，但不是哈密頓圖，但G2是半哈密頓圖，其實(shí)，是半哈密頓圖，其實(shí)，baegjckhfid為為G2中一中一條哈密頓通路條哈密頓通路. 設(shè)（設(shè)（3）中圖為）中圖為G3. G3=，其中，其中V1=a,c,g,h,e，V2=b,d,i,j,f，G3中存在哈密頓中存在哈密頓回路，如回路，如abcdgihjefa，所以，所以G3是哈密頓圖是哈密頓圖. 例例2:三個圖中哪些三個圖中哪些是哈密頓圖？哪些是哈密頓圖？哪些是半哈密頓圖？是半哈密頓圖？ 在（在（1）中，存

49、在哈密頓回路，所以（）中，存在哈密頓回路，所以（1）為哈密頓圖為哈密頓圖. 在（在（2）中，?。┲校1=a,b,c,d,e，從，從圖中刪除圖中刪除V1得得7個連通分支，個連通分支，(2)不是哈不是哈密頓圖，也不是半哈密頓圖密頓圖，也不是半哈密頓圖. 在（在（3）中，取）中，取V1=b,e,h，從圖中，從圖中刪除刪除V1得得4個連通分支，它不是哈密頓個連通分支，它不是哈密頓圖圖.但（但（3）中存在哈密頓通路，所以）中存在哈密頓通路，所以（3）是半哈密頓圖）是半哈密頓圖. 四四.平面圖平面圖 1.定義定義:如果圖如果圖G能以能以這樣的方式畫在曲面這樣的方式畫在曲面S上，即除頂點(diǎn)處外上，即除頂點(diǎn)

50、處外無邊相交，則稱無邊相交，則稱G可可嵌入曲面嵌入曲面S.若若G可嵌可嵌入平面，則稱入平面，則稱G是可是可平面圖或平面圖平面圖或平面圖.畫出畫出的無邊相交的圖稱為的無邊相交的圖稱為G的平面嵌入的平面嵌入.無平面無平面嵌入的圖稱為非平面嵌入的圖稱為非平面圖圖. 2.例例:3.平面圖的面與次數(shù)平面圖的面與次數(shù) 1).定義定義: 設(shè)設(shè)G是平面圖是平面圖(且已是平面嵌入且已是平面嵌入)，由，由G的邊將的邊將G所在的平面劃分成若干個區(qū)域，所在的平面劃分成若干個區(qū)域，每個區(qū)域都稱為每個區(qū)域都稱為G的一個面的一個面.其中面積無限其中面積無限的面稱為無限面或外部面，面積有限的面的面稱為無限面或外部面，面積有限

51、的面稱為有限面或內(nèi)部面稱為有限面或內(nèi)部面.包圍每個面的所有邊包圍每個面的所有邊組成的回路組稱為該面的邊界，邊界的長組成的回路組稱為該面的邊界，邊界的長度稱為該面的次數(shù)度稱為該面的次數(shù). 常記外部面為常記外部面為R0，內(nèi)部面為，內(nèi)部面為R1，R2，Rk，面，面R的次數(shù)記為的次數(shù)記為deg(R). 2).例例:圖是某圖的平面嵌圖是某圖的平面嵌入，它有入，它有5個面?zhèn)€面.R1的邊界的邊界為圈為圈abdc，deg(R1)4.R2的邊界也是圈，此圈的邊界也是圈，此圈為為efg，deg(R2)3，R3的邊界為環(huán)的邊界為環(huán)h,deg(R3)=1R4的邊界為圈的邊界為圈kjl，deg(R4)3.外部面外部面R

52、0的的邊界由一個簡單回路邊界由一個簡單回路abefgdc和一個復(fù)雜回路和一個復(fù)雜回路kjihil組成，組成，deg(R0)13. 3)定理定理: 平面圖平面圖G中所有面的次數(shù)之和等于邊中所有面的次數(shù)之和等于邊數(shù)數(shù)m的兩倍，即的兩倍，即 deg(Ri)=2m,其中其中r為為G的的面數(shù)面數(shù). 樹樹 TreeI.無向樹及其性質(zhì)無向樹及其性質(zhì) 一、無向樹的定義一、無向樹的定義 連通無回路的無向圖稱為無向樹，或簡稱樹，連通無回路的無向圖稱為無向樹，或簡稱樹，常用常用T表示樹表示樹.平凡圖稱為平凡樹平凡圖稱為平凡樹.若無向圖若無向圖G至至少有兩個連通分支，每個連通都是樹，則稱少有兩個連通分支，每個連通都是

53、樹，則稱G為森林為森林. 在無向圖中，在無向圖中，懸掛頂點(diǎn)懸掛頂點(diǎn)稱為樹葉，度數(shù)大于或稱為樹葉，度數(shù)大于或等于等于2的頂點(diǎn)稱為分支點(diǎn)的頂點(diǎn)稱為分支點(diǎn).二、無向樹的性質(zhì)二、無向樹的性質(zhì) 定理定理 設(shè)設(shè)G=是是n階階m條邊的無向圖，則下條邊的無向圖，則下面各命題是等價的：面各命題是等價的： （1）G是樹是樹. （2）G中任意兩個頂點(diǎn)之間存在唯一的路徑中任意兩個頂點(diǎn)之間存在唯一的路徑.（3）G中無回路且中無回路且m=n-1.（4）G是連通的且是連通的且m=n-1.（5）G是連通的且是連通的且G中任何邊均為中任何邊均為橋橋.（6）G中沒有回路，但在任何兩個不同的頂中沒有回路，但在任何兩個不同的頂點(diǎn)之間

54、加一條新邊，在所得圖中得到唯一的點(diǎn)之間加一條新邊，在所得圖中得到唯一的一個含新邊的圈一個含新邊的圈.定理定理 設(shè)設(shè)T是是n階非平凡的無向樹，則階非平凡的無向樹，則T中至少有中至少有兩片樹葉兩片樹葉. TII. 生成樹生成樹 一、生成樹的定義及存在定理一、生成樹的定義及存在定理 1.定義定義: 設(shè)設(shè)T是無向圖是無向圖G的子圖并且為樹，則的子圖并且為樹，則稱稱T為為G的樹的樹.若若T是是G的樹且為生成子圖，則的樹且為生成子圖，則稱稱T是是G的生成樹的生成樹.設(shè)設(shè)T是是G的生成樹的生成樹.eE(G)，若，若eE(T)，則稱，則稱e為為T的樹枝，否的樹枝，否則稱則稱e為為T的弦的弦.并稱并稱導(dǎo)出子圖導(dǎo)

55、出子圖GE(G)-E(T)為為T的余樹，記作的余樹，記作 . 2.例例:3.定理定理: 無向圖無向圖G具有生成樹，當(dāng)且僅當(dāng)具有生成樹，當(dāng)且僅當(dāng)G是是 連通圖連通圖.推論推論1：設(shè)：設(shè)G為為n階階m條邊的無向連通圖，則條邊的無向連通圖，則 mn-1. 推論推論2 ：設(shè)：設(shè)G是是n階階m條邊的無向連通圖，條邊的無向連通圖，T為為G的生成樹，則的生成樹，則T的余樹中的余樹中 含有含有m-n+1條邊條邊（即（即T有有m-n+1條弦）條弦）. TIII.基本回路及基本回路系統(tǒng)基本回路及基本回路系統(tǒng)1.定義定義: 設(shè)設(shè)T是是n階階m條邊的無向連通圖條邊的無向連通圖G的一的一棵生成樹，設(shè)棵生成樹，設(shè)e1,e

56、2,em-n+ +1為為T的弦，設(shè)的弦，設(shè)Cr為為T添加添加er產(chǎn)生的產(chǎn)生的G中只含弦中只含弦er，其余邊，其余邊均為樹枝的圈，稱均為樹枝的圈，稱Cr為為G的對應(yīng)的對應(yīng)T的弦的弦er的的基本回路或基本圈，基本回路或基本圈，r=1,2,m-n+1.并稱并稱C1,C2,Cm-n+1為為G對應(yīng)對應(yīng)T的基本回路系統(tǒng)的基本回路系統(tǒng) .2.例例:下圖對應(yīng)生成樹的下圖對應(yīng)生成樹的弦分別為弦分別為e6,e7,e8,e10,e11.設(shè)它們對應(yīng)的基本回路設(shè)它們對應(yīng)的基本回路分別為分別為C1,C2,C3,C4,C5，從對應(yīng)的弦開始，按順從對應(yīng)的弦開始，按順時針（也可都按逆時針）時針（也可都按逆時針）的順序?qū)懗鏊鼈儯?/p>

57、分別的順序?qū)懗鏊鼈?，分別為為 C1= e6e4e5 C2= e7e2e1 C3= e8e9e2e1 C4= e10e3e5e2 C5= e11e3e5e2e9 基本回路系統(tǒng)為基本回路系統(tǒng)為C1,C2,C3,C4,C5. IV.基本割集及基本割集系統(tǒng)基本割集及基本割集系統(tǒng) 1.定義定義: 設(shè)設(shè)T是是n階連通圖階連通圖G的一棵生成樹，的一棵生成樹，e1，e2，en-1為為T的樹枝，的樹枝，Si是是G的只含樹枝的只含樹枝ei的割集，則稱的割集，則稱Si為為G的對應(yīng)生成樹的對應(yīng)生成樹T由樹枝由樹枝ei生成的基本割集，生成的基本割集，i=1，2，n- -1.并稱并稱S1，S2，Sn-1為為G對應(yīng)對應(yīng)T的

58、基本割集系統(tǒng)的基本割集系統(tǒng). 2.例例:e1, e2, e3, e4, e5, e9為為T的的樹枝，設(shè)它們對應(yīng)的基本割樹枝，設(shè)它們對應(yīng)的基本割集分別為集分別為S1, S2, S3, S4, S5, S6.以以樹枝為集合中的第一個元素樹枝為集合中的第一個元素的方式寫出它們（當(dāng)然集合的方式寫出它們（當(dāng)然集合中的元素是不講順序的，這中的元素是不講順序的，這里為了區(qū)分樹枝和弦）里為了區(qū)分樹枝和弦）. S1=e1,e7,e8 S2=e2,e7,e8,e10,e11S3=e3,e10,e11 S4=e4,e6S5=e5,e6,e10,e11 S6=e9,e8,e11基本割集系統(tǒng)為基本割集系統(tǒng)為S1,S2,

59、S3,S4,S5,S6. V.最小生成樹最小生成樹 1.定義定義: 設(shè)無向連通帶權(quán)圖設(shè)無向連通帶權(quán)圖G=，T是是G的一棵生成樹的一棵生成樹.T的各邊權(quán)之和稱為的各邊權(quán)之和稱為T的權(quán)，記的權(quán)，記作作W(T).G的所有生成樹中權(quán)最小的生成樹稱的所有生成樹中權(quán)最小的生成樹稱為為G的最小生成樹的最小生成樹.2.求法求法:求最小生成樹已經(jīng)有許多種算法，這里求最小生成樹已經(jīng)有許多種算法，這里介紹避圈法（介紹避圈法（Kruskal算法）算法）. (1)設(shè)設(shè)n階無向連通帶權(quán)圖階無向連通帶權(quán)圖G=有有m條邊條邊.不妨設(shè)不妨設(shè)G中沒有環(huán)（否則，可以將所有的環(huán)中沒有環(huán)（否則，可以將所有的環(huán)先刪去），將先刪去），將m條邊按權(quán)從小到大順序排列，條邊按權(quán)從小到大順序排列，設(shè)為設(shè)為e1,e2,em. 2.求法求法:求最小生成樹已經(jīng)有許多種算法，這里求最小生成樹已經(jīng)有許多種算法，這里介紹避圈法（介紹避圈法（Kruskal算法）算法）. (1)設(shè)設(shè)n階無向連通帶權(quán)圖階無向連通帶權(quán)圖G=有有m條邊條邊.不妨設(shè)不妨設(shè)G中沒有環(huán)（否則，可以將所有的環(huán)中沒有環(huán)（否則，可以將所有的環(huán)先刪去），將先刪去），將m條邊按權(quán)從小到大順序排列，條邊按權(quán)從小到大順