《圖的基本概念--第一章ppt課件.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《圖的基本概念--第一章ppt課件.ppt（115頁(yè)珍藏版）》請(qǐng)?jiān)趨R文網(wǎng)上搜索。

1、第1章 圖的基本概念,本章內(nèi)容,1 圖2 通路與回路3 圖的連通性4 圖的矩陣表示5 圖的運(yùn)算,1.1 圖的基本概念,圖的定義圖的一些概念和規(guī)定簡(jiǎn)單圖和多重圖頂點(diǎn)的度數(shù)與握手定理圖的同構(gòu)完全圖與正則圖子圖與補(bǔ)圖,無(wú)序積與多重集合,設(shè)A，B為任意的兩個(gè)集合，稱a,b|aAbB為A與B的無(wú)序積，記作A&B?？蓪o(wú)序積中的無(wú)序?qū),b記為(a,b)，并且允許ab。無(wú)論a,b是否相等，均有(a,b)(b,a)，因而A&BB&A。元素可以重復(fù)出現(xiàn)的集合稱為多重集合或者多重集，某元素重復(fù)出現(xiàn)的次數(shù)稱為該元素的重復(fù)度。例如 在多重集合a,a,b,b,b,c,d中， a,b,c,d的重復(fù)度分別為2,3,1,1

2、。,笛卡爾積,設(shè)A，B為任意的兩個(gè)集合，稱|aAbB為A與B的笛卡爾積，記作AXB。笛卡爾積中的是有序?qū)?。只有a,b相等的時(shí)候才有(a,b)(b,a). 也只有A=B時(shí)才有AXBBXA。,定義1 一個(gè)無(wú)向圖是一個(gè)有序的二元組,記作G，其中（1）V稱為頂點(diǎn)集，其元素稱為頂點(diǎn)或結(jié)點(diǎn)。（2）E稱為邊集，它是無(wú)序積V&V的多重子集，其元素稱為無(wú)向邊，簡(jiǎn)稱邊。定義2 一個(gè)有向圖是一個(gè)有序的二元組，記作D，其中（1）V稱為頂點(diǎn)集，其元素稱為頂點(diǎn)或結(jié)點(diǎn)。（2）E為邊集，它是笛卡兒積VV的多重子集，其元素稱為有向邊，簡(jiǎn)稱邊。,無(wú)向圖和有向圖,說(shuō)明,可以用圖形表示圖，即用小圓圈（或?qū)嵭狞c(diǎn)）表示頂點(diǎn)，用頂點(diǎn)之間的

3、連線表示無(wú)向邊，用有方向的連線表示有向邊。,例1.1,例1.1 (1) 給定無(wú)向圖G，其中 Vv1,v2,v3,v4,v5，E=(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v5). (2) 給定有向圖D=，其中 Va,b,c,d，E,。 畫出G與D的圖形。,圖的一些概念和規(guī)定,G表示無(wú)向圖，但有時(shí)用G泛指圖(無(wú)向的或有向的)。D只能表示有向圖。V(G)，E(G)分別表示G的頂點(diǎn)集和邊集。若|V(G)|n，則稱G為n階圖。若|V(G)|與|E(G)|均為有限數(shù)，則稱G為有限圖。 若邊集E(G)，則稱G為零圖，此時(shí)，又若G為n階圖，則稱G

4、為n階零圖，記作Nn，特別地，稱N1為平凡圖。 在圖的定義中規(guī)定頂點(diǎn)集V為非空集，但在圖的運(yùn)算中可能產(chǎn)生頂點(diǎn)集為空集的運(yùn)算結(jié)果，為此規(guī)定頂點(diǎn)集為空集的圖為空?qǐng)D，并將空?qǐng)D記為。,標(biāo)定圖與非標(biāo)定圖、基圖,將圖的集合定義轉(zhuǎn)化成圖形表示之后，常用ek表示無(wú)向邊(vi,vj)（或有向邊），并稱頂點(diǎn)或邊用字母標(biāo)定的圖為標(biāo)定圖，否則稱為非標(biāo)定圖。將有向圖各有向邊均改成無(wú)向邊后的無(wú)向圖稱為原來(lái)圖的基圖。易知標(biāo)定圖與非標(biāo)定圖是可以相互轉(zhuǎn)化的; 任何無(wú)向圖G的各邊均加上箭頭就可以得到以G為基圖的有向圖。,關(guān)聯(lián)與關(guān)聯(lián)次數(shù)、環(huán)、孤立點(diǎn),設(shè)G為無(wú)向圖，ek(vi,vj)E，稱vi,vj為ek的端點(diǎn)，ek與vi或ek與v

5、j是彼此相關(guān)聯(lián)的。若vivj，則稱ek與vi或ek與vj的關(guān)聯(lián)次數(shù)為1。若vivj，則稱ek與vi的關(guān)聯(lián)次數(shù)為2，并稱ek為環(huán)。任意的vlV，若vlvi且vlvj，則稱ek與vl的關(guān)聯(lián)次數(shù)為0。 設(shè)D為有向圖，ekE，稱vi,vj為ek的端點(diǎn)。若vivj，則稱ek為D中的環(huán)。無(wú)論在無(wú)向圖中還是在有向圖中，無(wú)邊關(guān)聯(lián)的頂點(diǎn)均稱為孤立點(diǎn)。,相鄰與鄰接,設(shè)無(wú)向圖G，vi，vjV，ek，elE。若etE，使得et(vi，vj)，則稱vi與vj是相鄰的。若ek與el至少有一個(gè)公共端點(diǎn)，則稱ek與el是相鄰的。 設(shè)有向圖D，vi，vjV，ek，elE。若etE，使得et，則稱vi為et的始點(diǎn)，vj為et的終

6、點(diǎn)，并稱vi鄰接到vj，vj鄰接于vi。若ek的終點(diǎn)為el的始點(diǎn)，則稱ek與el相鄰。,鄰域,設(shè)無(wú)向圖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) 為v的出鄰域, -D(v)為v 的入鄰域. +D(v)-D(v)為v的鄰域，記做ND(v)。稱ND(v)v為v的閉鄰域，記做ND(v)。,舉例,NG(v1) ,+D(d ) ,v2，v5,NG(v1) ,v

7、1，v2，v5,IG(v1) ,e1，e2，e3,c,-D(d ) ,a，c,ND(d ) ,a，c,ND(d ) ,a，c，d,簡(jiǎn)單圖與多重圖,定義1.3 在無(wú)向圖中，關(guān)聯(lián)一對(duì)頂點(diǎn)的無(wú)向邊如果多于1條，則稱這些邊為平行邊，平行邊的條數(shù)稱為重?cái)?shù)。在有向圖中，關(guān)聯(lián)一對(duì)頂點(diǎn)的有向邊如果多于1條，并且這些邊的始點(diǎn)和終點(diǎn)相同(也就是它們的方向相同)，則稱這些邊為平行邊。含平行邊的圖稱為多重圖。既不含平行邊也不含環(huán)的圖稱為簡(jiǎn)單圖。例如：在圖1.1中，(a)中e5與e6是平行邊，(b)中e2與e3是平行邊，但e6與e7不是平行邊。(a)和(b)兩個(gè)圖都不是簡(jiǎn)單圖。,頂點(diǎn)的度數(shù),定義1.4 設(shè)G為一無(wú)向圖，

8、vV，稱v作為邊的端點(diǎn)次數(shù)之和為v的度數(shù)，簡(jiǎn)稱為度，記做 dG(v)。在不發(fā)生混淆時(shí)，簡(jiǎn)記為d(v)。注: 某個(gè)點(diǎn)上的環(huán)要計(jì)算2次度數(shù).設(shè)D為有向圖，vV，稱v作為邊的始點(diǎn)次數(shù)之和為v的出度，記做d+D(v)，簡(jiǎn)記作d+(v)。稱v作為邊的終點(diǎn)次數(shù)之和為v的入度，記做d -D(v)，簡(jiǎn)記作d-(v)。稱d+(v)+d-(v)為v的度數(shù)，記做d(v)。注:某個(gè)點(diǎn)上的有向環(huán)要對(duì)這個(gè)點(diǎn)計(jì)算一次入度計(jì)算一次出度.,圖的度數(shù)的相關(guān)概念,在無(wú)向圖G中，最大度(G)maxd(v)|vV(G)最小度(G)mind(v)|vV(G) 稱度數(shù)為1的頂點(diǎn)為懸掛頂點(diǎn)，與它關(guān)聯(lián)的邊稱為懸掛邊。度為偶數(shù)(奇數(shù))的頂點(diǎn)稱為

9、偶度(奇度)頂點(diǎn)。 在有向圖D中，最大出度+(D)maxd+(v)|vV(D)最小出度+(D)mind+(v)|vV(D)最大入度-(D)maxd-(v)|vV(D)最小入度-(D)mind-(v)|vV(D),圖的度數(shù)舉例,d(v1)4(注意，環(huán)提供2度)，4，1，v4是懸掛頂點(diǎn)，e7是懸掛邊。,d+(a)4，d-(a)1(環(huán)e1提供出度1，提供入度1)，d(a)4+15。5，3，+4 (在a點(diǎn)達(dá)到)+0(在b點(diǎn)達(dá)到)-3(在b點(diǎn)達(dá)到)-1(在a和c點(diǎn)達(dá)到),握手定理,定理1.1 設(shè)G為任意無(wú)向圖，Vv1,v2,vn，|E|m，則,說(shuō)明任何無(wú)向圖中，各頂點(diǎn)度數(shù)之和等于邊數(shù)的兩倍。證明G中每條

10、邊(包括環(huán))均有兩個(gè)端點(diǎn)，所以在計(jì)算G中各頂點(diǎn)度數(shù)之和時(shí)，每條邊均提供2度，當(dāng)然，m條邊，共提供2m度。,另外一個(gè)更嚴(yán)格的證明：當(dāng)G是簡(jiǎn)單圖時(shí)，,當(dāng)圖G不是簡(jiǎn)單圖時(shí)， 只要把每一個(gè)環(huán)與重邊上“嵌入”一個(gè)新的頂點(diǎn)得到新的圖G， G是簡(jiǎn)單圖. 假設(shè)有t個(gè)新的頂點(diǎn),圖G中原來(lái)G中的頂點(diǎn)度數(shù)不變， 而每個(gè)新的頂點(diǎn)的度數(shù)為2. 新圖G的邊數(shù)比圖G的邊數(shù)多了t條（原因是在環(huán)和重邊上加入新點(diǎn)后， 將原來(lái)的一條邊變成了兩條邊）。對(duì)G利用前面的證明結(jié)果：兩邊消去2t,得到結(jié)論。,握手定理,定理1.2 設(shè)D為任意有向圖，Vv1,v2,vn，|E|m，則,握手定理的推論,推論任何圖(無(wú)向的或有向的)中，奇度頂點(diǎn)的個(gè)

11、數(shù)是偶數(shù)。 證明設(shè)G為任意一圖，令V1v|vVd(v)為奇數(shù)V2v|vVd(v)為偶數(shù)則V1V2V，V1V2 ，由握手定理可知,由于2m和,，所以,為偶數(shù)，,但因V1中頂點(diǎn)度數(shù)為奇數(shù)，,所以|V1|必為偶數(shù)。,問(wèn)題研究,問(wèn)題：在一個(gè)部門的25個(gè)人中間，由于意見(jiàn)不同，是否可能每個(gè)人恰好與其他5個(gè)人意見(jiàn)一致？解答：不可能?？紤]一個(gè)圖，其中頂點(diǎn)代表人，如果兩個(gè)人意見(jiàn)相同，可用邊連接，所以每個(gè)頂點(diǎn)都是奇數(shù)度。存在奇數(shù)個(gè)度數(shù)為奇數(shù)的圖，這是不可能的。說(shuō)明：(1)很多離散問(wèn)題可以用圖模型求解。(2)為了建立一個(gè)圖模型，需要決定頂點(diǎn)和邊分別代表什么。(3)在一個(gè)圖模型中，邊經(jīng)常代表兩個(gè)頂點(diǎn)之間的關(guān)系。,例2

12、： 晚會(huì)上大家握手言歡，試證握過(guò)奇次手的人數(shù)是偶數(shù)。解答：構(gòu)造一個(gè)圖， 以參加晚會(huì)的人為頂，僅當(dāng)二人握手時(shí)在相應(yīng)的二頂間加一條邊。 于是每個(gè)人握手的次數(shù)為這個(gè)圖的相應(yīng)頂點(diǎn)的度數(shù)。 用握手定理的推論得到結(jié)論。例3： 空間中不可能有這樣的多面體存在， 它的面數(shù)是奇數(shù)，而且每個(gè)面是奇數(shù)條圍成的。解答：如果有這樣的多面體存在，以此多面體的面集合為頂點(diǎn)集構(gòu)造一個(gè)圖G,當(dāng)且僅當(dāng)兩個(gè)面有公共邊界線時(shí)在相應(yīng)的兩頂間連一條邊， 于是|V(G)|是奇數(shù)，而且對(duì)每個(gè)頂點(diǎn)v,d(v)是奇數(shù),則所有的頂點(diǎn)的度數(shù)之和為奇數(shù)， 與握手定理矛盾。,度數(shù)列,設(shè)G為一個(gè)n階無(wú)向圖，Vv1,v2,vn，稱d(v1)，d(v2)，d

13、(vn)為G的度數(shù)列。對(duì)于頂點(diǎn)標(biāo)定的無(wú)向圖，它的度數(shù)列是唯一的。反之，對(duì)于給定的非負(fù)整數(shù)列dd1,d2,dn，若存在Vv1,v2,vn為頂點(diǎn)集的n階無(wú)向圖G，使得d(vi)di，則稱d是可圖化的。特別地，若所得圖是簡(jiǎn)單圖，則稱d是可簡(jiǎn)單圖化的。類似地，設(shè)D為一個(gè)n階有向圖，Vv1,v2,vn，稱d(v1)，d(v2)，d(vn)為D的度數(shù)列，另外稱d+(v1)，d+(v2)，d+(vn)與d-(v1)，d-(v2)，d-(vn)分別為D的出度列和入度列。,度數(shù)列舉例,按頂點(diǎn)的標(biāo)定順序，度數(shù)列為4,4,2,1,3。,按字母順序，度數(shù)列，出度列，入度列分別為5,3,3,34,0,2,11,3,1,

14、2,可圖化的充要條件,定理1.3 設(shè)非負(fù)整數(shù)列d(d1，d2，dn)，則d是可圖化的當(dāng)且僅當(dāng),證明必要性。由握手定理顯然得證。充分性。由已知條件可知，d中有偶數(shù)個(gè)奇數(shù)度點(diǎn)。奇數(shù)度點(diǎn)兩兩之間連一邊，剩余度用環(huán)來(lái)實(shí)現(xiàn)。,可圖化舉例,由定理1.3立即可知，(3,3,2,1)，(3,2,2,1,1)等是不可圖化的，(3,3,2,2)，(3,2,2,2,1)等是可圖化的。,定理：若 是簡(jiǎn)單圖的次序列，且則 是偶數(shù)，且對(duì)1960年Erdos和Gallai已經(jīng)證明這也是充分條件。,證明：大致思路： 對(duì)任意的k, 把圖分成兩部分：一部分是1到k個(gè)點(diǎn)組成的， 設(shè)為V1， 另外的n-K點(diǎn)組成另外一部分,設(shè)為V2。

15、我們?cè)賮?lái)計(jì)算1到k點(diǎn)的總的度數(shù)之和。 這個(gè)度數(shù)由兩部分貢獻(xiàn)， 一是來(lái)自于V1的貢獻(xiàn)， 最多是V1構(gòu)成完全圖， 它們的度數(shù)之和為k(k-1), 第二部分來(lái)自于V2, V2中的每個(gè)點(diǎn)給V1的所有點(diǎn)貢獻(xiàn)的次數(shù)最多是d_i和k之間的最小值（原因是， V2的每個(gè)點(diǎn)的度數(shù)全部貢獻(xiàn)給V1,但V1中的點(diǎn)最多只有k個(gè)， 只能最多接收k次）。,定理1.4,定理1.4 設(shè)G為任意n階無(wú)向簡(jiǎn)單圖，則(G)n-1。 證明因?yàn)镚既無(wú)平行邊也無(wú)環(huán)，所以G中任何頂點(diǎn)v至多與其余的n-1個(gè)頂點(diǎn)均相鄰，于是d(v)n-1，由于v的任意性，所以(G)n-1。例1.2 判斷下列各非負(fù)整數(shù)列哪些是可圖化的？哪些是可簡(jiǎn)單圖化的？(1)

16、(5,5,4,4,2,1)不可圖化。(2) (5,4,3,2,2)可圖化，不可簡(jiǎn)單圖化。若它可簡(jiǎn)單圖化，設(shè)所得圖為G，則(G)max5,4,3,2,25，這與定理1.4矛盾。,例1.2,(3) (3,3,3,1)可圖化，不可簡(jiǎn)單圖化。假設(shè)該序列可以簡(jiǎn)單圖化，設(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度頂點(diǎn)，這是矛盾的，因而(3)中序列也不可簡(jiǎn)單圖化。,(4) (d1,d2,dn)，d1d2dn1 且 為偶數(shù)。,可圖化，不可簡(jiǎn)單圖化。原因?,例14.2,(5) (4,4,3,3,2,2) 可簡(jiǎn)單圖化。下圖中兩個(gè)6階無(wú)向簡(jiǎn)單圖都以(5)中序列為度數(shù)列。,圖的同構(gòu),定義1.5 設(shè)G1，G2為兩個(gè)無(wú)向圖，若存在雙射函數(shù)f：V1V2，對(duì)于vi,vjV1，(vi,vj)E1當(dāng)且僅當(dāng)(f(vi),f(vj)E2，并且 (vi,vj)與(f(vi),f(vj)的重?cái)?shù)相同，則稱G1與G2是同構(gòu)的，記做G1G2。說(shuō)明(1) 類似地，可以定義兩個(gè)有向圖的同構(gòu)