離散數(shù)學(xué)61圖基本概念PPT課件

1、16.1 圖的基本概念圖的基本概念 6.1.1 無向圖與有向圖 6.1.2 頂點(diǎn)的度數(shù)與握手定理 6.1.3 簡(jiǎn)單圖、完全圖、正則圖、圈圖、 輪圖、方體圖 6.1.4 子圖、補(bǔ)圖 6.1.5 圖的同構(gòu)第1頁/共27頁2無序?qū)εc多重集合無序?qū)? 2個(gè)元素構(gòu)成的集合, 記作(a,b)無序積: A B=(x,y) | x A y B例如 A=a,b,c, B=1,2 A B=B A=(a,1), (b,1), (c,1), (a,2), (b,2), (c,2) A A=(a,a), (a,b), (a,c), (b,b), (b,c), (c,c) B B=(1,1), (1,2), (2,2)多

2、重集合: 元素可以重復(fù)出現(xiàn)的集合重復(fù)度: 元素在多重集合中出現(xiàn)的次數(shù)例如 S=a,b,b,c,c,c, a,b,c 的重復(fù)度依次為1,2,3第2頁/共27頁3無向圖定義6.1 無向圖G=, 其中V稱為頂點(diǎn)集, 其元素稱為頂點(diǎn)或結(jié)點(diǎn); E是V V的多重子集, 稱為邊集, 其元素稱為無向邊，簡(jiǎn)稱邊. 有時(shí)用V(G)和E(G)分別表示V和E例如, G=如圖所示, 其中V=v1, v2, ,v5 E=(v1,v1), (v1,v2), (v2,v3), (v2,v3), (v2,v5), (v1,v5), (v4,v5) e1e2e3e4e5e6e7v5v1v2v3v4第3頁/共27頁4有向圖定義6.

3、2 有向圖D=, 其中V稱為頂點(diǎn)集, 其元素稱為頂點(diǎn)或結(jié)點(diǎn); E是V V的多重子集, 稱為邊集, 其元素稱為有向邊，簡(jiǎn)稱邊. 有時(shí)用V(D)和E(D)分別表示V和E 有限圖: V, E都是有窮集合的圖n 階圖: n個(gè)頂點(diǎn)的圖零圖: E=的圖平凡圖: 1 階零圖e1e2e3e4e5e6e7dabc第4頁/共27頁5頂點(diǎn)和邊的關(guān)聯(lián)與相鄰設(shè)無向圖G=, ek=(vi, vj) E, 稱vi, vj為ek的端點(diǎn), ek與vi ( vj)關(guān)聯(lián). 若vi = vj, 則稱ek為環(huán). 無邊關(guān)聯(lián)的頂點(diǎn)稱作孤立點(diǎn). 若vi vj, 則稱ek與vi ( vj)的關(guān)聯(lián)次數(shù)為1; 若vi = vj, 則稱ek與vi

4、的關(guān)聯(lián)次數(shù)為2; 若vi不是邊e的端點(diǎn), 則稱e與vi 的關(guān)聯(lián)次數(shù)為0. 設(shè)vi,vj V, ek,el E, 若(vi,vj) E, 則稱vi,vj相鄰; 若ek,el有一個(gè)公共端點(diǎn), 則稱ek,el相鄰.對(duì)有向圖有類似定義. 設(shè)ek= vi,vj 是有向圖的一條邊, 又稱vi是ek的始點(diǎn), vj是ek的終點(diǎn), vi鄰接到vj, vj鄰接于vi第5頁/共27頁6頂點(diǎn)的度數(shù)設(shè)G=為無向圖, v V,v的度數(shù)(度) d(v): v作為邊的端點(diǎn)次數(shù)之和 懸掛頂點(diǎn): 度數(shù)為1的頂點(diǎn)懸掛邊: 與懸掛頂點(diǎn)關(guān)聯(lián)的邊G的最大度 (G)=maxd(v)| v VG的最小度 (G)=mind(v)| v V例如

5、 d(v5)=3, d(v2)=4, d(v1)=4, (G)=4, (G)=1, v4是懸掛頂點(diǎn), e7是懸掛邊, e1是環(huán)e1e2e3e4e5e6e7v5v1v2v3v4第6頁/共27頁7頂點(diǎn)的度數(shù)(續(xù))設(shè)D=為有向圖, v V,v的出度d+(v): v作為邊的始點(diǎn)次數(shù)之和v的入度d (v): v作為邊的終點(diǎn)次數(shù)之和v的度數(shù)(度) d(v): v作為邊的端點(diǎn)次數(shù)之和 d(v)= d+(v)+ d-(v) +(D), +(D), (D), (D), (D), (D)懸掛頂點(diǎn), 懸掛邊例如 d+(a)=4, d-(a)=1, d(a)=5, d+(b)=0, d-(b)=3, d(b)=3,

6、+=4, +=0, =3, =1, =5, =3e1e2e3e4e5e6e7dabc第7頁/共27頁8握手定理定理6.1 任何圖(無向圖和有向圖)的所有頂點(diǎn)度數(shù)之和都等于邊數(shù)的2倍.證 圖中每條邊(包括環(huán))均有兩個(gè)端點(diǎn), 所以在計(jì)算各頂點(diǎn)度數(shù)之和時(shí), 每條邊均提供2度, m條邊共提供2m度.推論 任何圖(無向圖和有向圖)都有偶數(shù)個(gè)奇度頂點(diǎn)定理6.2 有向圖所有頂點(diǎn)的入度之和等于出度之和等于邊數(shù)證 每條邊恰好提供1個(gè)入度和1個(gè)出度第8頁/共27頁9圖的度數(shù)列設(shè)無向圖G的頂點(diǎn)集V=v1, v2, , vnG的度數(shù)列: d(v1), d(v2), , d(vn)如右圖度數(shù)列:4,4,2,1,3設(shè)有向

7、圖D的頂點(diǎn)集V=v1, v2, , vnD的度數(shù)列: d(v1), d(v2), , d(vn)D的出度列: d+(v1), d+(v2), , d+(vn)D的入度列: d (v1), d (v2), , d (vn)如右圖度數(shù)列:5,3,3,3 出度列:4,0,2,1 入度列:1,3,1,2e1e2e3e4e5e6e7v5v1v2v3v4e1e2e3e4e5e6e7dabc第9頁/共27頁10實(shí)例(2) 能能例1 下述2組數(shù)能成為無向圖的度數(shù)列嗎?(1) 3,3,3,4; (2) 1,2,2,3解解 (1) 不可能不可能. . 有奇數(shù)個(gè)奇數(shù)有奇數(shù)個(gè)奇數(shù). .第10頁/共27頁11實(shí)例例例2

8、 已知圖已知圖G有有10條邊條邊, 4個(gè)個(gè)3度頂點(diǎn)度頂點(diǎn), 其余頂點(diǎn)的度數(shù)均小其余頂點(diǎn)的度數(shù)均小于等于于等于2, 問問G至少有多少個(gè)頂點(diǎn)至少有多少個(gè)頂點(diǎn)? 解解 設(shè)設(shè)G有有n個(gè)頂點(diǎn)個(gè)頂點(diǎn). 由握手定理由握手定理, 4 3+2 (n-4) 2 10解得解得 n 8例例3 已知已知5階有向圖的度數(shù)列和出度列分別為階有向圖的度數(shù)列和出度列分別為3,3,2,3,3和和1,2,1,2,1, 求它的入度列求它的入度列解解 2,1,1,1,2第11頁/共27頁12實(shí)例例4 證明不存在具有奇數(shù)個(gè)面且每個(gè)面都具有奇數(shù)條棱的多面體.證證 用反證法用反證法. 假設(shè)存在這樣的多面體假設(shè)存在這樣的多面體, 作無向圖作無

9、向圖G=,其中其中 V=v | v為多面體的面為多面體的面, E=(u,v) | u,v V u與與v有公共的棱有公共的棱 u v.根據(jù)假設(shè)根據(jù)假設(shè), |V|為奇數(shù)且為奇數(shù)且 v V, d(v)為奇數(shù)為奇數(shù). 這與握手定理的這與握手定理的推論矛盾推論矛盾.第12頁/共27頁13實(shí)例例5 設(shè)9階無向圖的每個(gè)頂點(diǎn)的度數(shù)為5或6, 證明它至少有5個(gè)6度頂點(diǎn)或者至少有6個(gè)5度頂點(diǎn).證證 討論所有可能的情況討論所有可能的情況. 設(shè)有設(shè)有a個(gè)個(gè)5度頂點(diǎn)和度頂點(diǎn)和b個(gè)個(gè)6度頂點(diǎn)度頂點(diǎn)(1)a=0, b=9;(2)a=2, b=7;(3)a=4, b=5;(4)a=6, b=3;(5)a=8, b=1(1)(

10、3) 至少至少5個(gè)個(gè)6度頂點(diǎn)度頂點(diǎn), (4)和和(5) 至少至少6個(gè)個(gè)5度頂點(diǎn)度頂點(diǎn)方法二方法二 假設(shè)假設(shè)b9-5=4. 由握手定理的推論由握手定理的推論, a 6第13頁/共27頁14簡(jiǎn)單圖定義6.4 在無向圖中, 關(guān)聯(lián)同一對(duì)頂點(diǎn)的2條或2條以上的邊, 稱為平行邊, 平行邊的條數(shù)稱為重?cái)?shù)在有向圖中, 具有相同始點(diǎn)和終點(diǎn)的2條或2條以上的邊稱為有向平行邊, 簡(jiǎn)稱平行邊, 平行邊的條數(shù)稱為重?cái)?shù)含平行邊的圖稱為多重圖既無平行邊也無環(huán)的圖稱為簡(jiǎn)單圖第14頁/共27頁15實(shí)例e5和和e6 是平行邊是平行邊重?cái)?shù)為重?cái)?shù)為2不是簡(jiǎn)單圖不是簡(jiǎn)單圖e2和和e3 是平行邊是平行邊,重?cái)?shù)為重?cái)?shù)為2e6和和e7 不是

11、平行邊不是平行邊不是簡(jiǎn)單圖不是簡(jiǎn)單圖e1e2e3e4e5e6e7v5v1v2v3v4e1e2e3e4e5e6e7dabc第15頁/共27頁16完全圖與正則圖無向完全圖: 每對(duì)頂點(diǎn)之間都有一條邊的無向簡(jiǎn)單圖.n階無向完全圖記作Kn, 頂點(diǎn)數(shù)n, 邊數(shù)m=n(n-1)/2, = =n-1有向完全圖: 每對(duì)頂點(diǎn)之間均有兩條方向相反的邊的有向簡(jiǎn)單圖.頂點(diǎn)數(shù)n, 邊數(shù)m=n(n-1), += += -= -=n-1, = =2(n-1)k-正則圖: 每個(gè)頂點(diǎn)的度數(shù)均為k的無向簡(jiǎn)單圖頂點(diǎn)數(shù)n, 邊數(shù)m=kn/2第16頁/共27頁17實(shí)例K3K53階有向完全圖階有向完全圖2正則圖正則圖4正則圖正則圖 3正則

12、圖正則圖彼得松圖彼得松圖第17頁/共27頁18圈圖與輪圖無 向 圈 圖Cn= , 其 中V= v1,v2, ,vn , E=(v1,v2),(v2,v3),(vn-1,vn),(vn,v1), n 3有 向 圈 圖Cn= , 其 中V= v1,v2, ,vn , E=, n 3輪圖Wn:無向圈圖Cn-1內(nèi)放一個(gè)頂點(diǎn), 且與圈圖的每個(gè)頂點(diǎn)之間恰有一條邊, n 4第18頁/共27頁19方體圖n方體圖Qn=是2n階無向簡(jiǎn)單圖, 其中 V=v|v=a1a2an, ai=0,1, i=1,2,n E=(u,v)| u,v V u與v恰好有一位數(shù)字不同. 0100011011000 001010 0111

13、10100111101第19頁/共27頁20子圖定義6.10 設(shè)G=, G =是2個(gè)圖(同為無向圖,或同為有向圖)若VV且EE, 則稱G 為G的子圖, G為G 的母圖, 記作GG若GG 且V =V, 則稱G 為G的生成子圖若VV或EE, 稱G 為G的真子圖設(shè)VV且V, 以V 為頂點(diǎn)集, 以兩端點(diǎn)都在V 中的所有邊為邊集的G的子圖稱作V 的導(dǎo)出子圖, 記作GV 設(shè)EE且E, 以E 為邊集, 以E 中邊關(guān)聯(lián)的所有頂點(diǎn)為頂點(diǎn)集的G的子圖稱作E 的導(dǎo)出子圖, 記作GE 第20頁/共27頁21實(shí)例(1),(2),(3)是(1)的子圖, (2),(3)是真子圖, (1)是母圖.(1),(3)是(1)的生成

14、子圖.(2)是d,e,f 的導(dǎo)出子圖, 也是e5, e6, e7導(dǎo)出子圖.(3)是e1, e3, e5, e7的導(dǎo)出子圖aabbccdddeee f f f e1 e1 e2 e3 e3 e4 e5 e5 e5 e6 e6 e7 e7 e7(1)(2)(3)第21頁/共27頁22補(bǔ)圖定義定義6.11 設(shè)設(shè)G=為為n階無向簡(jiǎn)單圖階無向簡(jiǎn)單圖, 記記 =V V -E, 稱稱 為為G的的補(bǔ)圖補(bǔ)圖EEVG,第22頁/共27頁23圖的同構(gòu)定義6.12 設(shè)G1=, G2=為兩個(gè)無向圖(有向圖), 若存在雙射函數(shù) f: V1V2, 使得對(duì)于任意的vi,vj V1, (vi,vj) E1 ( E1) 當(dāng)且僅當(dāng) (f(vi), f(vj) E2 ( E2)并且 (vi,vj) () 與 (f(vi),f(vj) ()的重?cái)?shù)相同，則稱G1與G2是同構(gòu)的，記作G1