1、1第第6 6章章 圖圖 6.1 圖的基本概念 6.2 圖的連通性 6.3 圖的矩陣表示 6.4 幾種特殊的圖第1頁/共28頁26.1 圖的基本概念圖的基本概念 6.1.1 無向圖與有向圖 6.1.2 頂點的度數與握手定理 6.1.3 簡單圖、完全圖、正則圖、圈圖、 輪圖、方體圖 6.1.4 子圖、補圖 6.1.5 圖的同構第2頁/共28頁3無序對與多重集合無序對: 2個元素構成的集合, 記作(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,

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

3、v5), (v1,v5), (v4,v5) e1e2e3e4e5e6e7v5v1v2v3v4第4頁/共28頁5有向圖定義6.2 有向圖D=, 其中V稱為頂點集, 其元素稱為頂點或結點; E是V V的多重子集, 稱為邊集, 其元素稱為有向邊，簡稱邊. 有時用V(D)和E(D)分別表示V和E 有限圖: V, E都是有窮集合的圖n 階圖: n個頂點的圖零圖: E=的圖平凡圖: 1 階零圖e1e2e3e4e5e6e7dabc第5頁/共28頁6頂點和邊的關聯與相鄰設無向圖G=, ek=(vi, vj) E, 稱vi, vj為ek的端點, ek與vi ( vj)關聯. 若vi = vj, 則稱ek為環.

4、無邊關聯的頂點稱作孤立點. 若vi vj, 則稱ek與vi ( vj)的關聯次數為1; 若vi = vj, 則稱ek與vi 的關聯次數為2; 若vi不是邊e的端點, 則稱e與vi 的關聯次數為0. 設vi,vj V, ek,el E, 若(vi,vj) E, 則稱vi,vj相鄰; 若ek,el有一個公共端點, 則稱ek,el相鄰.對有向圖有類似定義. 設ek= vi,vj 是有向圖的一條邊, 又稱vi是ek的始點, vj是ek的終點, vi鄰接到vj, vj鄰接于vi第6頁/共28頁7頂點的度數設G=為無向圖, v V,v的度數(度) d(v): v作為邊的端點次數之和 懸掛頂點: 度數為1的

5、頂點懸掛邊: 與懸掛頂點關聯的邊G的最大度 (G)=maxd(v)| v VG的最小度 (G)=mind(v)| v V例如 d(v5)=3, d(v2)=4, d(v1)=4, (G)=4, (G)=1, v4是懸掛頂點, e7是懸掛邊, e1是環e1e2e3e4e5e6e7v5v1v2v3v4第7頁/共28頁8頂點的度數(續)設D=為有向圖, v V,v的出度d+(v): v作為邊的始點次數之和v的入度d (v): v作為邊的終點次數之和v的度數(度) d(v): v作為邊的端點次數之和 d(v)= d+(v)+ d-(v) +(D), +(D), (D), (D), (D), (D)懸掛

6、頂點, 懸掛邊例如 d+(a)=4, d-(a)=1, d(a)=5, d+(b)=0, d-(b)=3, d(b)=3, +=4, +=0, =3, =1, =5, =3e1e2e3e4e5e6e7dabc第8頁/共28頁9握手定理定理6.1 任何圖(無向圖和有向圖)的所有頂點度數之和都等于邊數的2倍.證 圖中每條邊(包括環)均有兩個端點, 所以在計算各頂點度數之和時, 每條邊均提供2度, m條邊共提供2m度.推論 任何圖(無向圖和有向圖)都有偶數個奇度頂點定理6.2 有向圖所有頂點的入度之和等于出度之和等于邊數證 每條邊恰好提供1個入度和1個出度第9頁/共28頁10圖的度數列設無向圖G的頂

7、點集V=v1, v2, , vnG的度數列: d(v1), d(v2), , d(vn)如右圖度數列:4,4,2,1,3設有向圖D的頂點集V=v1, v2, , vnD的度數列: d(v1), d(v2), , d(vn)D的出度列: d+(v1), d+(v2), , d+(vn)D的入度列: d (v1), d (v2), , d (vn)如右圖度數列:5,3,3,3 出度列:4,0,2,1 入度列:1,3,1,2e1e2e3e4e5e6e7v5v1v2v3v4e1e2e3e4e5e6e7dabc第10頁/共28頁11實例(2) 能能例1 下述2組數能成為無向圖的度數列嗎?(1) 3,3,

8、3,4; (2) 1,2,2,3解解 (1) 不可能不可能. . 有奇數個奇數有奇數個奇數. .第11頁/共28頁12實例例例2 已知圖已知圖G有有10條邊條邊, 4個個3度頂點度頂點, 其余頂點的度數均小其余頂點的度數均小于等于于等于2, 問問G至少有多少個頂點至少有多少個頂點? 解解 設設G有有n個頂點個頂點. 由握手定理由握手定理, 4 3+2 (n-4) 2 10解得解得 n 8例例3 已知已知5階有向圖的度數列和出度列分別為階有向圖的度數列和出度列分別為3,3,2,3,3和和1,2,1,2,1, 求它的入度列求它的入度列解解 2,1,1,1,2第12頁/共28頁13實例例4 證明不存

9、在具有奇數個面且每個面都具有奇數條棱的多面體.證證 用反證法用反證法. 假設存在這樣的多面體假設存在這樣的多面體, 作無向圖作無向圖G=,其中其中 V=v | v為多面體的面為多面體的面, E=(u,v) | u,v V u與與v有公共的棱有公共的棱 u v.根據假設根據假設, |V|為奇數且為奇數且 v V, d(v)為奇數為奇數. 這與握手定理的這與握手定理的推論矛盾推論矛盾.第13頁/共28頁14實例例5 設9階無向圖的每個頂點的度數為5或6, 證明它至少有5個6度頂點或者至少有6個5度頂點.證證 討論所有可能的情況討論所有可能的情況. 設有設有a個個5度頂點和度頂點和b個個6度頂點度頂

10、點(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)(3) 至少至少5個個6度頂點度頂點, (4)和和(5) 至少至少6個個5度頂點度頂點方法二方法二 假設假設b9-5=4. 由握手定理的推論由握手定理的推論, a 6第14頁/共28頁15簡單圖定義6.4 在無向圖中, 關聯同一對頂點的2條或2條以上的邊, 稱為平行邊, 平行邊的條數稱為重數在有向圖中, 具有相同始點和終點的2條或2條以上的邊稱為有向平行邊, 簡稱平行邊, 平行邊的條數稱為重數含平行邊的圖稱為多重圖既無平行邊也無環的圖稱為簡單圖第15頁/共28頁16實例

11、e5和和e6 是平行邊是平行邊重數為重數為2不是簡單圖不是簡單圖e2和和e3 是平行邊是平行邊,重數為重數為2e6和和e7 不是平行邊不是平行邊不是簡單圖不是簡單圖e1e2e3e4e5e6e7v5v1v2v3v4e1e2e3e4e5e6e7dabc第16頁/共28頁17完全圖與正則圖無向完全圖: 每對頂點之間都有一條邊的無向簡單圖.n階無向完全圖記作Kn, 頂點數n, 邊數m=n(n-1)/2, = =n-1有向完全圖: 每對頂點之間均有兩條方向相反的邊的有向簡單圖.頂點數n, 邊數m=n(n-1), += += -= -=n-1, = =2(n-1)k-正則圖: 每個頂點的度數均為k的無向簡

12、單圖頂點數n, 邊數m=kn/2第17頁/共28頁18實例K3K53階有向完全圖階有向完全圖2正則圖正則圖4正則圖正則圖 3正則圖正則圖彼得松圖彼得松圖第18頁/共28頁19圈圖與輪圖無 向 圈 圖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 4第19頁/共28頁20方體圖n方體圖Qn=是2n階無向簡單圖, 其中 V=v|v=a1a2an, ai=0,1

13、, i=1,2,n E=(u,v)| u,v V u與v恰好有一位數字不同. 0100011011000 001010 011110100111101第20頁/共28頁21子圖定義6.10 設G=, G =是2個圖(同為無向圖,或同為有向圖)若VV且EE, 則稱G 為G的子圖, G為G 的母圖, 記作GG若GG 且V =V, 則稱G 為G的生成子圖若VV或EE, 稱G 為G的真子圖設VV且V, 以V 為頂點集, 以兩端點都在V 中的所有邊為邊集的G的子圖稱作V 的導出子圖, 記作GV 設EE且E, 以E 為邊集, 以E 中邊關聯的所有頂點為頂點集的G的子圖稱作E 的導出子圖, 記作GE 第21

14、頁/共28頁22實例(1),(2),(3)是(1)的子圖, (2),(3)是真子圖, (1)是母圖.(1),(3)是(1)的生成子圖.(2)是d,e,f 的導出子圖, 也是e5, e6, e7導出子圖.(3)是e1, e3, e5, e7的導出子圖aabbccdddeee f f f e1 e1 e2 e3 e3 e4 e5 e5 e5 e6 e6 e7 e7 e7(1)(2)(3)第22頁/共28頁23補圖定義定義6.11 設設G=為為n階無向簡單圖階無向簡單圖, 記記 =V V -E, 稱稱 為為G的的補圖補圖EEVG,第23頁/共28頁24圖的同構定義6.12 設G1=, G2=為兩個無向圖(有向圖), 若存在雙射函數 f: V1V2, 使得對于任意的vi,vj V1, (vi,vj) E1 ( E1) 當且僅當 (f(vi), f(vj) E2 ( E2)并且 (vi,vj) () 與 (f(vi),f(vj) ()的重數相同，則稱G1與G2是同構的，記作G1