《圖的基本概念》

1、第14章 圖的基本概念,離 散 數(shù) 學(xué),中國地質(zhì)大學(xué)本科生課程,整理ppt,2,本章內(nèi)容,14.1 圖 14.2 通路與回路 14.3 圖的連通性 14.4 圖的矩陣表示 14.5 圖的運算 基本要求 作業(yè),整理ppt,3,14.1 圖的基本概念,圖的定義 圖的一些概念和規(guī)定 簡單圖和多重圖 頂點的度數(shù)與握手定理 圖的同構(gòu) 完全圖與正則圖 子圖與補圖,整理ppt,4,無序積與多重集合,元素可以重復(fù)出現(xiàn)的集合稱為多重集合或者多重集，某元素重復(fù)出現(xiàn)的次數(shù)稱為該元素的重復(fù)度。 例如 在多重集合a,a,b,b,b,c,d中， a,b,c,d的重復(fù)度分別為2,3,1,1,整理ppt,5,定義14.1 一

2、個無向圖是一個有序的二元組,記作G，其中 （1）V稱為頂點集，其元素稱為頂點或結(jié)點。 （2）E稱為邊集，它是無序積V&V的多重子集，其元素稱為無向邊，簡稱邊。 定義14.2 一個有向圖是一個有序的二元組，記作D，其中 （1）V稱為頂點集，其元素稱為頂點或結(jié)點。 （2）E為邊集，它是笛卡兒積VV的多重子集，其元素稱為有向邊，簡稱邊,無向圖和有向圖,說明,可以用圖形表示圖，即用小圓圈（或?qū)嵭狞c）表示頂點，用頂點之間的連線表示無向邊，用有方向的連線表示有向邊,整理ppt,6,例14.1,例14.1 (1) 給定無向圖G，其中 Vv1,v2,v3,v4,v5，E=(v1,v1),(v1,v2),(v2

3、,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v5). (2) 給定有向圖D=，其中 Va,b,c,d，E,。 畫出G與D的圖形,整理ppt,7,圖的一些概念和規(guī)定,G表示無向圖，但有時用G泛指圖(無向的或有向的)。 D只能表示有向圖。 V(G)，E(G)分別表示G的頂點集和邊集。 若|V(G)|n，則稱G為n階圖。 若|V(G)|與|E(G)|均為有限數(shù)，則稱G為有限圖。 若邊集E(G)，則稱G為零圖，此時，又若G為n階圖，則稱G為n階零圖，記作Nn，特別地，稱N1為平凡圖。 在圖的定義中規(guī)定頂點集V為非空集，但在圖的運算中可能產(chǎn)生頂點集為空集的運算結(jié)果，為此規(guī)定頂點集為

4、空集的圖為空圖，并將空圖記為,整理ppt,8,標定圖與非標定圖、基圖,將圖的集合定義轉(zhuǎn)化成圖形表示之后，常用ek表示無向邊(vi,vj)（或有向邊），并稱頂點或邊用字母標定的圖為標定圖，否則稱為非標定圖。 將有向圖各有向邊均改成無向邊后的無向圖稱為原來圖的基圖。 易知標定圖與非標定圖是可以相互轉(zhuǎn)化的，任何無向圖G的各邊均加上箭頭就可以得到以G為基圖的有向圖,整理ppt,9,關(guān)聯(lián)與關(guān)聯(lián)次數(shù)、環(huán)、孤立點,設(shè)G為無向圖，ek(vi,vj)E， 稱vi,vj為ek的端點，ek與vi或ek與vj是彼此相關(guān)聯(lián)的。 若vivj，則稱ek與vi或ek與vj的關(guān)聯(lián)次數(shù)為1。 若vivj，則稱ek與vi的關(guān)聯(lián)次數(shù)

5、為2，并稱ek為環(huán)。 若端點vl不與邊ek關(guān)聯(lián)，則稱ek與vl的關(guān)聯(lián)次數(shù)為0。 設(shè)D為有向圖，ekE， 稱vi,vj為ek的端點。 若vivj，則稱ek為D中的環(huán)。 無論在無向圖中還是在有向圖中，無邊關(guān)聯(lián)的頂點均稱為孤立點,整理ppt,10,相鄰與鄰接,設(shè)無向圖G，vi，vjV，ek，elE。 若etE，使得et(vi，vj)，則稱vi與vj是相鄰的。 若ek與el至少有一個公共端點，則稱ek與el是相鄰的。 設(shè)有向圖D，vi，vjV，ek，elE。 若etE，使得et，則稱vi為et的始點，vj為et的終點，并稱vi鄰接到vj ， vj鄰接于vi。 若ek的終點為el的始點，則稱ek與el相

6、鄰,整理ppt,11,鄰域,設(shè)無向圖G，vV， 稱u|uV(u,v)Euv為v的鄰域，記做NG(v)。 稱NG(v)v為v的閉鄰域，記做NG(v)。 稱e|eEe與v相關(guān)聯(lián)為v的關(guān)聯(lián)集，記做IG(v)。 設(shè)有向圖D，vV， 稱u|uVEuv為v的后繼元集，記做+D(v)。 稱u|uVEuv為v的先驅(qū)元集，記做-D(v)。 稱+D(v)-D(v)為v的鄰域，記做ND(v)。 稱ND(v)v為v的閉鄰域，記做ND(v,整理ppt,12,舉例,NG(v1),D(d ),v2，v5,NG(v1),v1，v2，v5,IG(v1),e1，e2，e3,c,D(d ),a，c,ND(d ),a，c,ND(d

7、),a，c，d,整理ppt,13,簡單圖與多重圖,定義14.3 在無向圖中，關(guān)聯(lián)一對頂點的無向邊如果多于1條，則稱這些邊為平行邊，平行邊的條數(shù)稱為重數(shù)。 在有向圖中，關(guān)聯(lián)一對頂點的有向邊如果多于1條，并且這些邊的始點和終點相同(也就是它們的方向相同)，則稱這些邊為平行邊。 含平行邊的圖稱為多重圖。 既不含平行邊也不含環(huán)的圖稱為簡單圖。 例如：在圖14.1中， (a)中e5與e6是平行邊， (b)中e2與e3是平行邊，但e6與e7不是平行邊。 (a)和(b)兩個圖都不是簡單圖,整理ppt,14,頂點的度數(shù),定義14.4 設(shè)G為一無向圖，vV，稱v作為邊的端點次數(shù)之和為v的度數(shù)，簡稱為度，記做 d

8、G(v)。 在不發(fā)生混淆時，簡記為d(v)。 設(shè)D為有向圖，vV， 稱v作為邊的始點次數(shù)之和為v的出度，記做d+D(v)，簡記作d+(v)。 稱v作為邊的終點次數(shù)之和為v的入度，記做d -D(v)，簡記作d-(v)。 稱d+(v)+d-(v)為v的度數(shù)，記做d(v,整理ppt,15,圖的度數(shù)的相關(guān)概念,在無向圖G中， 最大度(G)maxd(v)|vV(G) 最小度(G)mind(v)|vV(G) 在有向圖D中， 最大出度+(D)maxd+(v)|vV(D) 最小出度+(D)mind+(v)|vV(D) 最大入度-(D)maxd-(v)|vV(D) 最小入度-(D)mind-(v)|vV(D)

9、稱度數(shù)為1的頂點為懸掛頂點，與它關(guān)聯(lián)的邊稱為懸掛邊。度為偶數(shù)(奇數(shù))的頂點稱為偶度(奇度)頂點,整理ppt,16,圖的度數(shù)舉例,d(v1)4(注意，環(huán)提供2度)， 4，1， v4是懸掛頂點，e7是懸掛邊,d+(a)4，d-(a)1(環(huán)e1提供出度1，提供入度1)， d(a)4+15。5，3， +4 (在a點達到) +0(在b點達到) -3(在b點達到) -1(在a和c點達到,整理ppt,17,握手定理,定理14.1 設(shè)G為任意無向圖，Vv1,v2,vn， |E|m，則,說明任何無向圖中，各頂點度數(shù)之和等于邊數(shù)的兩倍。 證明G中每條邊(包括環(huán))均有兩個端點， 所以在計算G中各頂點度數(shù)之和時， 每

10、條邊均提供2度，當然，m條邊，共提供2m度,定理14.2 設(shè)D為任意有向圖，Vv1,v2,vn， |E|m，則,整理ppt,18,握手定理的推論,推論任何圖(無向的或有向的)中，奇度頂點的個數(shù)是偶數(shù)。 證明設(shè)G為任意一圖，令 V1v|vVd(v)為奇數(shù) V2v|vVd(v)為偶數(shù) 則V1V2V，V1V2 ，由握手定理可知,由于2m和,所以,為偶數(shù),但因V1中頂點度數(shù)為奇數(shù),所以|V1|必為偶數(shù),整理ppt,19,問題研究,問題：在一個部門的25個人中間，由于意見不同，是否可能每個人恰好與其他5個人意見一致？ 解答：不可能?？紤]一個圖，其中頂點代表人，如果兩個人意見相同，可用邊連接，所以每個頂點

11、都是奇數(shù)度。存在奇數(shù)個度數(shù)為奇數(shù)的圖，這是不可能的。 說明： (1)很多離散問題可以用圖模型求解。 (2)為了建立一個圖模型，需要決定頂點和邊分別代表什么。 (3)在一個圖模型中，邊經(jīng)常代表兩個頂點之間的關(guān)系,整理ppt,20,度數(shù)列,設(shè)G為一個n階無向圖，Vv1,v2,vn，稱d(v1)，d(v2)，d(vn)為G的度數(shù)列。 對于頂點標定的無向圖，它的度數(shù)列是唯一的。 反之，對于給定的非負整數(shù)列dd1,d2,dn，若存在Vv1,v2,vn為頂點集的n階無向圖G，使得d(vi)di，則稱d是可圖化的。 特別地，若所得圖是簡單圖，則稱d是可簡單圖化的。 類似地，設(shè)D為一個n階有向圖，Vv1,v2

12、,vn，稱d(v1)，d(v2)，d(vn)為D的度數(shù)列，另外稱d+(v1)，d+(v2)，d+(vn)與d-(v1)，d-(v2)，d-(vn)分別為D的出度列和入度列,整理ppt,21,度數(shù)列舉例,按頂點的標定順序，度數(shù)列為 4,4,2,1,3,按字母順序，度數(shù)列，出度列，入度列分別為 5,3,3,3 4,0,2,1 1,3,1,2,整理ppt,22,可圖化的充要條件,定理14.3 設(shè)非負整數(shù)列d(d1，d2，dn)，則d是可圖化的當且僅當,證明必要性。由握手定理顯然得證。 充分性。由已知條件可知，d中有偶數(shù)個奇數(shù)度點。 奇數(shù)度點兩兩之間連一邊，剩余度用環(huán)來實現(xiàn),整理ppt,23,定理14

13、.3的證明,由握手定理可知必然性顯然。 下面證明充分性。 由已知條件可知，d中有2k(0kn/2)個奇數(shù)， 不妨設(shè)它們?yōu)閐1，d2，dk，dk+1，dk+2，d2k。 可用多種方法做出n階無向圖G，Vv1,v2,vn。 比如邊集如下產(chǎn)生：在頂點vr與vr+k之間連邊，r1,2,k。 若di為偶數(shù)，令didi，若di為奇數(shù)，令didi-1， 得d(d1，d2，dn)，則di均為偶數(shù)。 再在vi處做出di/2條環(huán),i1,n， 將所得各邊集合在一起組成E，則G的度數(shù)列為d。 其實，di為偶數(shù)時，d(vi)2di/22di/2di， 當di為奇數(shù)時，d(vi)1+2di/21+di1+di-1di，

14、這就證明了d是可圖化的,整理ppt,24,可圖化舉例,由定理14.3立即可知， (3,3,2,1)，(3,2,2,1,1)等是不可圖化的， (3,3,2,2)，(3,2,2,2,1)等是可圖化的,整理ppt,25,定理14.4,定理14.4 設(shè)G為任意n階無向簡單圖，則(G)n-1。 證明因為G既無平行邊也無環(huán)， 所以G中任何頂點v至多與其余的n-1個頂點均相鄰， 于是d(v)n-1，由于v的任意性，所以(G)n-1。 例14.2 判斷下列各非負整數(shù)列哪些是可圖化的？哪些是可簡單圖化的？ (1) (5,5,4,4,2,1) 不可圖化。 (2) (5,4,3,2,2) 可圖化，不可簡單圖化。若它

15、可簡單圖化， 設(shè)所得圖為G，則(G)max5,4,3,2,25， 這與定理14.4矛盾,整理ppt,26,例14.2,3) (3,3,3,1) 可圖化，不可簡單圖化。假設(shè)該序列可以簡單圖化， 設(shè)G以該序列為度數(shù)列。 不妨設(shè)Vv1,v2,v3,v4 且 d(v1)d(v2)d(v3)3,d(v4)1， 由于d(v4)1，因而v4只能與v1，v2，v3之一相鄰， 于是v1，v2，v3不可能都是3度頂點，這是矛盾的， 因而(3)中序列也不可簡單圖化,4) (d1,d2,dn)，d1d2dn1 且 為偶數(shù),可圖化，不可簡單圖化,整理ppt,27,例14.2,5) (4,4,3,3,2,2) 可簡單圖化

16、。下圖中兩個6階無向簡單圖都以(5)中序列為度數(shù)列,整理ppt,28,圖的同構(gòu),定義14.5 設(shè)G1，G2為兩個無向圖， 若存在雙射函數(shù)f：V1V2，對于vi,vjV1，(vi,vj)E1 當且僅當(f(vi),f(vj)E2， 并且(vi,vj)與(f(vi),f(vj)的重數(shù)相同， 則稱G1與G2是同構(gòu)的，記做G1G2。 說明(1) 類似地，可以定義兩個有向圖的同構(gòu)。 (2) 圖的同構(gòu)關(guān)系看成全體圖集合上的二元關(guān)系。 (3) 圖的同構(gòu)關(guān)系是等價關(guān)系。 (4) 在圖同構(gòu)的意義下，圖的數(shù)學(xué)定義與圖形表示 是一一對應(yīng)的,整理ppt,29,圖的同構(gòu)舉例,彼得森(Petersen)圖,整理ppt,3

17、0,完全圖,定義14.6 設(shè)G為n階無向簡單圖，若G中每個頂點均與其余的n-1個頂點相鄰，則稱G為n階無向完全圖，簡稱n階完全圖，記做Kn(n1)。 設(shè)D為n階有向簡單圖，若D中每個頂點都鄰接到其余的n-1個頂點，又鄰接于其余的n-1個頂點，則稱D是n階有向完全圖。 設(shè)D為n階有向簡單圖，若D的基圖為n階無向完全圖Kn，則稱D是n階競賽圖,整理ppt,31,完全圖舉例,n階無向完全圖的邊數(shù)為：n(n-1)/2 n階有向完全圖的邊數(shù)為：n(n-1) n階競賽圖的邊數(shù)為：n(n-1)/2,K5,3階有向完全圖,4階競賽圖,整理ppt,32,正則圖,定義14.7 設(shè)G為n階無向簡單圖，若vV(G)，

18、均有d(v)k，則稱G為k-正則圖。 舉例n階零圖是0-正則圖 n階無向完全圖是(n-1)-正則圖 彼得森圖是3-正則圖 說明n階k-正則圖中，邊數(shù)mkn/2。 當k為奇數(shù)時，n必為偶數(shù),整理ppt,33,子圖,定義14.8 設(shè)G，G為兩個圖(同為無向圖或同為有向圖)，若V V且E E，則稱G是G的子圖，G為G 的母圖，記作G G。 若V V或E E，則稱G 為G的真子圖。 若V V，則稱G 為G的生成子圖。 設(shè)G為一圖，V1V且V1，稱以V1為頂點集，以G中兩個端點都在V1中的邊組成邊集E1的圖為G的V1導(dǎo)出的子圖，記作GV1。 設(shè)E1E且E1，稱以E1為邊集，以E1中邊關(guān)聯(lián)的頂點為頂點集V

19、1的圖為G的E1導(dǎo)出的子圖，記作GE1,整理ppt,34,導(dǎo)出子圖舉例,在上圖中，設(shè)G為(1)中圖所表示， 取V1a,b,c，則V1的導(dǎo)出子圖GV1為(2)中圖所示。 取E1e1,e3，則E1的導(dǎo)出子圖GE1為(3)中圖所示,整理ppt,35,例14.3,1) 畫出4階3條邊的所有非同構(gòu)的無向簡單圖。 由握手定理可知，所畫的無向簡單圖各頂點度數(shù)之和為236，最大度小于或等于3。于是所求無向簡單圖的度數(shù)列應(yīng)滿足的條件是，將6分成4個非負整數(shù)，每個整數(shù)均大于或等于0且小于或等于3，并且奇數(shù)的個數(shù)為偶數(shù)。將這樣的整數(shù)列排出來只有下面三種情況,1) 2，2，1，1(2) 3，1，1，1(3) 2，2，

20、2，0,將每種度數(shù)列所有非同構(gòu)的圖都畫出來即得所要求的全部非同構(gòu)的圖,對于給定的正整數(shù)n和m(mn(n-1)/2)，構(gòu)造出所有非同構(gòu)的n階m條邊的所有非同構(gòu)的無向(有向)簡單圖，這是目前還沒有解決的難題,整理ppt,36,例14.3,2) 畫出3階2條邊的所有非同構(gòu)的有向簡單圖。 由握手定理可知，所畫有向簡單圖各頂點度數(shù)之和為4，最大出度和最大入度均小于或等于2。度數(shù)列及入度出度列為,1,2,1,入度列為 0,1,1 或 0,2,0 或 1,0,1,出度列為 1,1,0 或 1,0,1 或 0,2,0,2,2,0,入度列為 1,1,0,出度列為 1,1,0,整理ppt,37,定義14.9,定義

21、14.9 設(shè)G為n階無向簡單圖，以V為頂點集，以所有使G成為完全圖Kn的添加邊組成的集合為邊集的圖，稱為G的補圖，記作G。 若圖GG，則稱為G是自補圖,1)為自補圖 (2)和(3)互為補圖,整理ppt,38,定義14.10,定義14.10 設(shè)G為無向圖。 (1)設(shè)eE，用G-e表示從G中去掉邊e，稱為刪除e。 設(shè)E E，用G-E 表示從G中刪除E 中所有的邊，稱為刪除E 。 (2)設(shè)vV，用G-v表示從G中去掉v及所關(guān)聯(lián)的一切邊，稱為刪除頂點v。 設(shè)V V，用G-V 表示從G中刪除V 中所有頂點，稱為刪除V 。 (3)設(shè)邊e(u,v)E，用Ge表示從G中刪除e后，將e的兩個端點u,v用一個新的

22、頂點w(或用u或v充當w)代替，使w關(guān)聯(lián)除e外u,v關(guān)聯(lián)的所有邊，稱為邊e的收縮。 (4)設(shè)u,vV(u,v可能相鄰，也可能不相鄰)，用G(u,v)(或G+(u,v)表示在u,v之間加一條邊(u,v)，稱為加新邊。 說明在收縮邊和加新邊過程中可能產(chǎn)生環(huán)和平行邊,整理ppt,39,舉例,G,Ge5,Ge1, e4,Gv5,Gv4, v5,Ge5,整理ppt,40,14.2 通路與回路,定義14.11 設(shè)G為無向標定圖，G中頂點與邊的交替序列vi0ej1vi1ej2vi2ejivil稱為vi0到vil的通路，其中，vir-1,vir為ejr的端點，r 1，2，l，vi0，vil分別稱為的始點與終點

23、，中邊的條數(shù)稱為它的長度。 若vi0vil，則稱通路為回路。 若的所有邊各異，則稱為簡單通路， 又若vi0vil，則稱為簡單回路。 若的所有頂點(除vi0與vij可能相同外)各異，所有邊也各異，則稱為初級通路或路徑， 又若vi0vil，則稱為初級回路或圈。 將長度為奇數(shù)的圈稱為奇圈，長度為偶數(shù)的圈稱為偶圈,整理ppt,41,關(guān)于通路與回路的說明,在初級通路與初級回路的定義中，仍將初級回路看成初級通路(路徑)的特殊情況，只是在應(yīng)用中初級通路(路徑)都是始點與終點不相同的，長為1的圈只能由環(huán)生成，長為2的圈只能由平行邊生成，因而在簡單無向圖中，圈的長度至少為3。 若中有邊重復(fù)出現(xiàn)，則稱為復(fù)雜通路，

24、 又若vi0vil，則稱為復(fù)雜回路。 在有向圖中，通路、回路及分類的定義與無向圖中非常相似，只是要注意有向邊方向的一致性。 在以上的定義中，將回路定義成通路的特殊情況，即回路也是通路，又初級通路(回路)是簡單通路(回路)，但反之不真,整理ppt,42,通路和回路的簡單表示法,只用邊的序列表示通路(回路)。定義14.11中的可以表示成ej1 ,ej2 , ,ejl。 在簡單圖中也可以只用頂點序列表示通路(回路)。定義中的也可以表示成vi0 ,vi2 , ,vil。 為了寫出非標定圖中的通路(回路)，可以先將非標定圖標成標定圖，再寫出通路與回路。 在非簡單標定圖中，當只用頂點序列表示不出某些通路(

25、回路)時，可在頂點序列中加入一些邊(這些邊是平行邊或環(huán))，可稱這種表示法為混合表示法,整理ppt,43,定理14.5,定理14.5 在n階圖G中，若從頂點vi到vj（vivj）存在通路，則從vi到vj存在長度小于或等于n-1的通路。 證明 設(shè)v0e1v1e2elvl(v0vi ,vlvj)為G中一條長度為l的通路， 若ln-1，則滿足要求， 否則必有l(wèi)+1n，即上的頂點數(shù)大于G中的頂點數(shù)， 于是必存在k,s,0ksl，使得 vsvk, 即在上存在vs到自身的回路Csk, 在上刪除Csk上的一切邊及除vs外的一切頂點， 得v0e1v1e2vkes+1 elvl ,仍為vi到vj的通路， 且長度至

26、少比減少1。 若還不滿足要求，則重復(fù)上述過程，由于G是有限圖，經(jīng)過有限步后，必得到vi到vj長度小于或等于n-1的通路,整理ppt,44,定理14.6,推論 在n階圖G中，若從頂點vi到vj（vivj）存在通路，則vi到vj一定存在長度小于或等于n-1的初級通路（路徑）。 定理14.6 在一個n階圖G中，若存在vi 到自身的回路，則一定存在vi 到自身長度小于或等于n的回路。 推論 在一個n階圖G中，若存在vi 到自身的簡單回路，則一定存在vi 到自身長度小于或等于n的初級回路,整理ppt,45,例14.4,例14.4 無向完全圖Kn(n3)中有幾種非同構(gòu)的圈？ 解答長度相同的圈都是同構(gòu)的，

27、因而只有長度不同的圈才是非同構(gòu)的， 易知Kn(n3)中含長度為3，4，n的圈， 所以Kn(n3)中有n-2種非同構(gòu)的圈,整理ppt,46,例14.5,例14.5 無向完全圖K3的頂點依次標定為a,b,c。在定義意義下K3中有多少個不同的圈？ 解答在同構(gòu)意義下，K3中只有一個長度為3的圈。 但在定義意義下，不同起點(終點)的圈是不同的， 頂點間排列順序不同的圈也看成是不同的， 因而K3中有6個不同的長為3的圈： abca ，acba ，bacb ，bcab ，cabc ，cbac 如果只考慮起點(終點)的差異， 而不考慮順時針逆時針的差異，應(yīng)有3種不同的圈， 當然它們都是同構(gòu)的，畫出圖來只有一個

28、,整理ppt,47,14.3 圖的連通性,無向圖的連通性 無向圖中頂點之間的短程線及距離 無向圖的連通程度：點割集、割點、邊割集、割邊、連通度 有向圖的連通性及判別方法 擴大路徑法與極大路徑 二部圖及其判別方法,整理ppt,48,無向圖的連通性,定義14.12 設(shè)無向圖G，u,vV，若u,v之間存在通路，則稱u,v是連通的，記作uv。 vV，規(guī)定vv。 無向圖中頂點之間的連通關(guān)系 （u,v）| u,vV且u與v之間有通路 是自反的、對稱的、傳遞的，因而是V上的等價關(guān)系,整理ppt,49,連通圖與連通分支,若無向圖G是平凡圖或G中任何兩個頂點都是連通的，則稱G為連通圖，否則稱G是非連通圖或分離圖

29、。 說明：完全圖Kn(n1)都是連通圖 零圖Nn(n2)都是分離圖。 定義14.13 設(shè)無向圖G，V關(guān)于頂點之間的連通關(guān)系的商集V/V1,V2,Vk，Vi為等價類，稱導(dǎo)出子圖GVi(i1,2,k)為G的連通分支，連通分支數(shù)k常記為p(G)。 說明若G為連通圖，則p(G)1。 若G為非連通圖，則p(G)2。 在所有的n階無向圖中，n階零圖是連通分支最多的，p(Nn)n,整理ppt,50,無向圖中頂點之間的短程線及距離,定義14.14 設(shè)u,v為無向圖G中任意兩個頂點，若uv，稱u,v之間長度最短的通路為u,v之間的短程線，短程線的長度稱為u,v之間的距離，記作d(u,v)。 當u,v不連通時，規(guī)

30、定d(u,v)。 距離有以下性質(zhì)： (1)d(u,v)0，uv時，等號成立。 (2)具有對稱性，d(u,v)d(v,u)。 (3)滿足三角不等式： u,v,wV(G)，則 d(u,v)+d(v,w)d(u,w) 說明：在完全圖Kn(n2)中，任何兩個頂點之間的距離都是1。 在n階零圖Nn(n2)中，任何兩個頂點之間的距離都為,整理ppt,51,如何定義連通度,問題：如何定量地比較無向圖的連通性的強與弱？ 點連通度：為了破壞連通性，至少需要刪除多少個頂點？ 邊連通度：為了破壞連通性，至少需要刪除多少條邊？ “破壞連通性”是指“變得更加不連通”,整理ppt,52,無向圖的點割集,定義14.15 設(shè)

31、無向圖G，若存在V V，且V ，使得p(G-V )p(G)，而對于任意的V V ，均有p(G-V )p(G)，則稱V 是G的點割集。 若V 是單元集，即V v，則稱v為割點,v2,v4,v3,v5都是點割集 v3,v5都是割點 v1與v6不在任何割集中,整理ppt,53,無向圖的邊割集,定義14.16設(shè)無向圖G，若存在E E，且E ，使得p(G-E )p(G)，而對于任意的E E，均有p(G-E )p(G)，則稱E是G的邊割集，或簡稱為割集。 若E 是單元集，即E e，則稱e為割邊或橋,e6,e5,e2,e3,e1,e2,e3,e4,e1,e4,e1,e3,e2,e4都是割集， e6,e5是橋

32、,整理ppt,54,點連通度,定義14.17設(shè)G為無向連通圖且為非完全圖，則稱 K(G)min|V |V 為G的點割集 為G的點連通度，簡稱連通度。 說明 連通度是為了產(chǎn)生一個不連通圖需要刪去的點的最少數(shù)目。 規(guī)定完全圖Kn(n1)的點連通度為n-1， 規(guī)定非連通圖的點連通度為0， 若K(G)k，則稱G是k-連通圖，k為非負整數(shù)。 說明K(G)有時簡記為K。 上例中圖的點連通度為1，此圖為1-連通圖。 K5的點連通度K4，所以K5是1-連通圖，2-連通圖，3-連通圖，4-連通圖。 若G是k-連通圖（k1）則在G中刪除任何k-1個頂點后，所得圖一定還是連通的,整理ppt,55,邊連通度,定義14

33、.18 設(shè)G是無向連通圖，稱 (G )min|E | E 是G的邊割集 為G的邊連通度。 規(guī)定非連通圖的邊連通度為0。 若(G)r，則稱G是r 邊-連通圖。 說明 (G)也可以簡記為。 若G是 r 邊-連通圖，則在G中任意刪除r-1條邊后，所得圖依然是連通的。 完全圖Kn的邊連通度為n-1，因而Kn是r邊-連通圖，0rn-1。 圖14.8中圖的邊連通度1，它只能是1邊-連通圖,整理ppt,56,例14.6,求所示各圖的點連通度，邊連通度，并指出它們各是幾連通圖及幾邊連通圖。最后將它們按點連通程度及邊連通程度排序,K4,K3,K2,K1,K=1 =2,K2,K0,K0,整理ppt,57,例14.

34、6的解答,設(shè)第i個圖的點連通度為Ki，邊連通度為i，I1,2,8。 容易看出，K114，K223，K332，K441， K5=1 5=2，K662，K770，K880。 (1)是k-連通圖，k邊-連通圖，k1,2,3,4。 (2)是k-連通圖，k邊-連通圖，k1,2,3。 (3)是k-連通圖，k邊-連通圖，k1,2。 (4)是1-連通圖，1邊-連通圖。 (5)是1-連通圖，k邊-連通圖，k1,2。 (6)是k-連通圖，k邊-連通圖，k1,2。 (7)是0-連通圖，0邊-連通圖。 (8)是0-連通圖，0邊-連通圖。 點連通程度為(1)(2)(3)(6)(4)(5)(7)(8)。 邊連通程度為(1

35、)(2)(3)(5)(6)(4)(7)(8,整理ppt,58,定理14.7,定理14.7 對于任何無向圖G，有 K(G)(G)(G) 例14.7 (1)給出一些無向簡單圖，使得 K。 (2)給出一些無向簡單圖，使得 K。 解答 (1) n階無向完全圖Kn和n階零圖Nn都滿足要求。 (2)在兩個Kn(n4)之間放置一個頂點v，使v與兩個Kn中的每一個的任意兩個不同的頂點相鄰，所得簡單圖滿足要求。 因為這樣的圖中有一個割點，所以點連通度為1， 又因為無橋，而有兩條邊組成的邊割集，所以邊連通度為2， 當n4時，3，當n5時，4,整理ppt,59,有向圖的連通性,定義14.19 設(shè)D為一個有向圖。vi

36、,vjV，若從vi到vj存在通路，則稱vi可達vj，記作vivj， 規(guī)定vi總是可達自身的，即vivi。 若vivj且vjvi，則稱vi與vj是相互可達的，記作vi vj。 規(guī)定vivi。 說明 與都是V上的二元關(guān)系，并且不難看出是V上的等價關(guān)系。 定義14.20 設(shè)D為有向圖，vi,vjV，若vivj，稱vi到vj長度最短的通路為vi到vj的短程線， 短程線的長度為vi到vj的距離，記作d 。 說明 與無向圖中頂點vi與vj之間的距離d(vi,vj)相比，d除無對稱性外，具有d(vi,vj)所具有的一切性質(zhì),整理ppt,60,連通圖,定義14.21 設(shè)D為一個有向圖。若D的基圖是連通圖，則稱

37、D是弱連通圖，簡稱為連通圖。 若vi,vjV，vivj與vjvi至少成立其一，則稱D是單向連通圖。 若均有vi vj，則稱D是強連通圖。 說明 強連通圖一定是單向連通圖， 單向連通圖一定是弱連通圖,強連通圖,單向連通圖,弱連通圖,整理ppt,61,強連通圖與單向連通圖的判定定理,定理14.8 設(shè)有向圖D，Vv1,v2,vn。D是強連通圖當且僅當D中存在經(jīng)過每個頂點至少一次的回路。 證明 充分性顯然。 下面證明必要性。 由D的強連通性可知，vivi+1，i1,2,n-1。 設(shè)i為vi到vi+1的通路。 又因為vnv1，設(shè)n為vn到v1的通路，則1,2,n-1,n所圍成的回路經(jīng)過D中每個頂點至少一

38、次。 定理14.9 設(shè)D是n階有向圖，D是單向連通圖當且僅當D中存在經(jīng)過每個頂點至少一次的通路。 證明略,整理ppt,62,強連通圖與單向連通圖的判定定理,定理14.8 設(shè)有向圖D，Vv1,v2,vn。D是強連通圖當且僅當D中存在經(jīng)過每個頂點至少一次的回路。 證明 充分性顯然。 下面證明必要性。 由D的強連通性可知，vivi+1，i1,2,n-1。 設(shè)i為vi到vi+1的通路。 又因為vnv1，設(shè)n為vn到v1的通路，則1,2,n-1,n所圍成的回路經(jīng)過D中每個頂點至少一次。 定理14.9 設(shè)D是n階有向圖，D是單向連通圖當且僅當D中存在經(jīng)過每個頂點至少一次的通路。 證明略。 問題 設(shè)有向圖D

39、是單向連通圖，但不是強連通圖，問在D中至少加幾條邊所得圖D 就能成為強連通圖,整理ppt,63,擴大路徑法,設(shè)G為n階無向圖，E，設(shè)l為G中一條路徑， 若此路徑的始點或終點與通路外的頂點相鄰，就將它們擴到通路中來。 繼續(xù)這一過程，直到最后得到的通路的兩個端點不與通路外的頂點相鄰為止。 設(shè)最后得到的路徑為l+k(長度為l的路徑擴大成了長度為l+k的路徑)，稱l+k為“極大路徑”， 稱使用此種方法證明問題的方法為“擴大路徑法”。 有向圖中可以類似地討論，只須注意，在每步擴大中保持有向邊方向的一致性,整理ppt,64,關(guān)于極大路徑的說明,由某條路經(jīng)擴大出的極大路徑不唯一。 極大路徑不一定是圖中最長的

40、路徑,整理ppt,65,例14.8,例14.8 設(shè)G為n（n4）階無向簡單圖，(G)3。 證明G中存在長度大于或等于4的圈。 證明 不妨設(shè)G是連通圖，否則，因為G的各連通分支的最小度也都大于或等于3，因而可對它的某個連通分支進行討論。 設(shè)u,v為G中任意兩個頂點，由G是連通圖，因而u,v之間存在通路，由定理14.5的推論可知，u,v之間存在路徑，用“擴大路徑法”擴大這條路徑，設(shè)最后得到的“極大路徑”為lv0v1vl，易知l3。 若v0與vl相鄰，則l(v0,vl)為長度大于或等于4的圈。 否則，由于d(v0)(G)3，因而v0除與l上的v1相鄰?fù)?，還存在l上的頂點vk(k1)和vt(kt l

41、)與v0相鄰，則v0v1vkvtv0為一個圈且長度大于或等于4，見圖,整理ppt,66,二部圖,定義14.22 設(shè)G為一個無向圖，若能將V分成V1和V2(V1V2V,V1V2)，使得G中的每條邊的兩個端點都是一個屬于V1，另一個屬于V2，則稱G為二部圖（或稱二分圖，偶圖等），稱V1和V2為互補頂點子集。 常將二部圖G記為。 若G是簡單二部圖，V1中每個頂點均與V2中所有頂點相鄰，則稱G為完全二部圖，記為Kr,s，其中r|V1|，s|V2|。 說明n階零圖為二部圖,整理ppt,67,二部圖舉例,K6的子圖,K6的子圖,K3,3,K2,3,K3,3,K2,3,整理ppt,68,二部圖的判定定理,定

42、理14.10 一個無向圖G是二部圖當且僅當G中無奇數(shù)長度的回路。 證明必要性。 若G中無回路，結(jié)論顯然成立。 若G中有回路，只需證明G中無奇圈。 設(shè)C為G中任意一圈，令Cvi1vi2vilvi1，易知 l2。 不妨設(shè)vi1V1，則必有vilV-V1=V2， 而l必為偶數(shù)，于是C為偶圈， 由C的任意性可知結(jié)論成立,整理ppt,69,二部圖的判定定理,充分性。 不妨設(shè)G為連通圖，否則可對每個連通分支進行討論。 設(shè)v0為G中任意一個頂點，令 V1v|vV(G)d(v0,v)為偶數(shù) V2v|vV(G)d(v0,v)為奇數(shù) 易知，V1,V2,V1V2，V1V2V(G)。 下面只要證明V1中任意兩頂點不相

43、鄰,V2中任意兩點也不相鄰。 若存在vi,vjV1相鄰，令(vi,vj)e， 設(shè)v0到vi,vj的短程線分別為i,j， 則它們的長度d(v0,vi),d(v0,vj)都是偶數(shù)， 于是ije中一定含奇圈，這與已知條件矛盾。 類似可證，V2中也不存在相鄰的頂點，于是G為二部圖,整理ppt,70,14.4 圖的矩陣表示,定義14.23 設(shè)無向圖G，Vv1,v2,vn，Ee1,e2,em，令mij為頂點vi與邊ej的關(guān)聯(lián)次數(shù)，則稱(mij)nm為G的關(guān)聯(lián)矩陣，記作M(G,整理ppt,71,有向圖的關(guān)聯(lián)矩陣,定義14.24 設(shè)有向圖D中無環(huán)，Vv1,v2,vn，Ee1,e2,em，令,則稱(mij)nm為D的關(guān)聯(lián)矩陣，記作M(D,整理ppt,72,有向圖的鄰接矩陣,定義14.25 設(shè)有向圖