離散數(shù)學第14章課件_高等教育出版社_屈婉玲_耿素云_張立昂主編

1、1第五部分第五部分 圖論圖論本部分主要內(nèi)容本部分主要內(nèi)容l 圖的基本概念圖的基本概念l 歐拉圖、哈密頓圖歐拉圖、哈密頓圖l 樹樹l 2 第十四章第十四章 圖的基本概念圖的基本概念主要內(nèi)容主要內(nèi)容l 圖圖l 通路與回路通路與回路l 圖的連通性圖的連通性l 圖的矩陣表示圖的矩陣表示l 圖的運算圖的運算預備知識預備知識l 多重集合多重集合元素可以重復出現(xiàn)的集合元素可以重復出現(xiàn)的集合l 無序積無序積A B=x,y | x A y B314.1 圖圖定義定義14.1 無向圖無向圖G = , 其中其中(1) V 為頂點集，元素稱為為頂點集，元素稱為頂點頂點(2) E為為V V 的多重集，其元素稱為無向邊，

2、簡稱的多重集，其元素稱為無向邊，簡稱邊邊實例實例 設設 V = v1, v2, ,v5, E = (v1,v1), (v1,v2), (v2,v3), (v2,v3), (v2,v5), (v1,v5), (v4,v5) 則則 G = 為一無向圖為一無向圖4有向圖有向圖定義定義14.2 有向圖有向圖D=, 只需注意只需注意E是是V V 的多重子集的多重子集圖圖2表示的是一個有向圖，試寫出它的表示的是一個有向圖，試寫出它的V 和和 E 注意：圖的數(shù)學定義與圖形表示。注意：圖的數(shù)學定義與圖形表示。5相關概念相關概念1. 圖圖 可用可用G泛指圖（無向的或有向的）泛指圖（無向的或有向的） V(G),

3、E(G), V(D), E(D) n階圖階圖2. 有限圖有限圖3. n 階零圖與平凡圖階零圖與平凡圖4. 空圖空圖5. 用用 ek 表示無向邊或有向邊表示無向邊或有向邊6. 頂點與邊的關聯(lián)關系頂點與邊的關聯(lián)關系 關聯(lián)、關聯(lián)次數(shù)關聯(lián)、關聯(lián)次數(shù) 環(huán)環(huán) 孤立點孤立點7. 頂點之間的相鄰關系頂點之間的相鄰關系6)()()(),()(|)(vvNvNvvuGEvuGVuuvNv 的的閉閉鄰鄰域域的的鄰鄰域域)(|)(關關聯(lián)聯(lián)與與veGEeevI )()()()()()(,)(|)()(,)(|)(vvNvNvvvvNvvuDEvuDVuuvvvuDEuvDVuuvvDDDDDDD 的閉鄰域的閉鄰域的鄰域

4、的鄰域的先驅(qū)元集的先驅(qū)元集的后繼元集的后繼元集8. 鄰域與關聯(lián)集鄰域與關聯(lián)集 v V(G) (G為無向圖為無向圖) v 的關聯(lián)集的關聯(lián)集 v V(D) (D為有向圖為有向圖)9. 標定圖與非標定圖標定圖與非標定圖10. 基圖基圖相關概念相關概念7多重圖與簡單圖多重圖與簡單圖定義定義14.3 (1) 無向圖中的平行邊及重數(shù)無向圖中的平行邊及重數(shù) (2) 有向圖中的平行邊及重數(shù)（注意方向性）有向圖中的平行邊及重數(shù)（注意方向性） (3) 多重圖多重圖 (4) 簡單圖簡單圖在定義在定義14.3中定義的簡單圖是極其重要的概念中定義的簡單圖是極其重要的概念 8頂點的度數(shù)頂點的度數(shù)定義定義14.4 (1)

5、設設G=為無向圖為無向圖, v V, d(v)v的度數(shù)的度數(shù), 簡稱度簡稱度 (2) 設設D=為有向圖為有向圖, v V, d+(v)v的入度的入度 d (v)v的出度的出度 d(v)v的度或度數(shù)的度或度數(shù) (3) (G), (G) (4) +(D), +(D), (D), (D), (D), (D) (5) 奇頂點度與偶度頂點奇頂點度與偶度頂點9mvdnii2)(1 mvdvdmvdniiniinii 111)()(,2)(且且定理定理14.1 設設G=為任意無向圖，為任意無向圖，V=v1,v2,vn, |E|=m, 則則證證 G中每條邊中每條邊 (包括環(huán)包括環(huán)) 均有兩個端點，所以在計算均

6、有兩個端點，所以在計算G中各頂點中各頂點度數(shù)之和時，每條邊均提供度數(shù)之和時，每條邊均提供2度，度，m 條邊共提供條邊共提供 2m 度度.本定理的證明類似于定理本定理的證明類似于定理14.1握手定理握手定理定理定理14.2 設設D=為任意有向圖，為任意有向圖，V=v1,v2,vn, |E|=m, 則則10握手定理推論握手定理推論推論推論 任何圖任何圖 (無向或有向無向或有向) 中，奇度頂點的個數(shù)是偶數(shù)中，奇度頂點的個數(shù)是偶數(shù).證證 設設G=為任意圖，令為任意圖，令 V1=v | v V d(v)為奇數(shù)為奇數(shù) V2=v | v V d(v)為偶數(shù)為偶數(shù) 則則V1 V2=V, V1 V2=，由握手定

7、理可知，由握手定理可知由于由于2m, 均為偶數(shù)，所以均為偶數(shù)，所以 為偶數(shù)，但因為為偶數(shù)，但因為V1中中頂點度數(shù)為奇數(shù)，所以頂點度數(shù)為奇數(shù)，所以|V1|必為偶數(shù)必為偶數(shù). 21)()()(2VvVvVvvdvdvdm 2)(Vvvd 1)(Vvvd11例例1 無向圖無向圖G有有16條邊，條邊，3個個4度頂點，度頂點，4個個3度頂點，其余度頂點，其余頂點度數(shù)均小于頂點度數(shù)均小于3，問，問G的階數(shù)的階數(shù)n為幾？為幾？解解 本題的關鍵是應用握手定理本題的關鍵是應用握手定理. 設除設除3度與度與4度頂點外，還有度頂點外，還有x個頂點個頂點v1, v2, , vx， 則則 d(vi) 2，i =1, 2

8、, , x，于是得不等式于是得不等式 32 24+2x得得 x 4, 階數(shù)階數(shù) n 4+4+3=11. 握手定理應用握手定理應用12圖的度數(shù)列圖的度數(shù)列1 . V=v1, v2, , vn為無向圖為無向圖G的頂點集，稱的頂點集，稱d(v1), d(v2), , d(vn)為為G的的度度數(shù)列數(shù)列 2. V=v1, v2, , vn為有向圖為有向圖D的頂點集，的頂點集， D的的度數(shù)列度數(shù)列：d(v1), d(v2), , d(vn) D的的入度列入度列：d+(v1), d+(v2), , d+(vn) D的的出度列出度列：d (v1), d (v2), , d (vn) 3. 非負整數(shù)列非負整數(shù)列

9、d=(d1, d2, , dn)在什么條件下是在什么條件下是可圖化的可圖化的，是，是可簡單圖化可簡單圖化的？的？定理定理14.4 p277易知：易知：(2, 4, 6, 8, 10)，(1, 3, 3, 3, 4) 是可圖化的，后者又是可是可圖化的，后者又是可簡單圖化的，而簡單圖化的，而(2, 2, 3, 4, 5)，(3, 3, 3, 4) 都不是可簡單圖化都不是可簡單圖化的，特別是后者也不是可圖化的的，特別是后者也不是可圖化的13n 階完全圖與競賽圖階完全圖與競賽圖定義定義14.6 (1) n (n 1) 階無向完全圖階無向完全圖每個頂點與其余頂點均相鄰的每個頂點與其余頂點均相鄰的無向簡單

10、圖無向簡單圖，記作，記作 Kn.簡單性質(zhì)：邊數(shù)簡單性質(zhì)：邊數(shù)(2) n (n 1)階階有向完全圖有向完全圖每對頂點之間均有兩條方向相每對頂點之間均有兩條方向相反的有向邊的反的有向邊的有向簡單圖有向簡單圖.簡單性質(zhì)：簡單性質(zhì)： (3) n (n 1) 階階競賽圖競賽圖基圖為基圖為Kn的的有向簡單圖有向簡單圖.簡單性質(zhì)：邊數(shù)簡單性質(zhì)：邊數(shù)1,2)1( nnnm 1),1(2),1( nnnnm 1,2)1( nnnm 14n 階階 k 正則圖正則圖(1)為為K5，(2)為為3階有向完全圖，階有向完全圖，(3)為為4階競賽圖階競賽圖. (1) (2) (3)定義定義14.7 n 階階k正則圖正則圖

11、= =k 的的無向簡單圖無向簡單圖簡單性質(zhì)：邊數(shù)（由握手定理得）簡單性質(zhì)：邊數(shù)（由握手定理得）n階完全圖階完全圖Kn是是 n 1正則圖，正則圖，2nkm 15子圖子圖定義定義14.8 G=, G =(1) GG G 為為G的的子圖子圖，G為為G 的的母圖母圖(2) 若若GG且且V =V，則稱，則稱G 為為G的的生成子圖生成子圖(3) 若若VV或或EE，稱，稱G 為為G的的真子圖真子圖(4) V （VV且且V）的）的導出子圖導出子圖，記作，記作GV (5) E （EE且且E）的）的導出子圖導出子圖，記作，記作GE 16例例2 畫出畫出K4的所有非同構(gòu)的生成子圖的所有非同構(gòu)的生成子圖實例實例17補

12、圖補圖定義定義14.9 設設G=為為n階無向簡單圖，以階無向簡單圖，以V為頂點集，以為頂點集，以所有使所有使G成為完全圖成為完全圖Kn的的添加邊添加邊組成的集合為邊集的圖，組成的集合為邊集的圖，稱為稱為G的的補圖補圖，記作，記作 .若若G , 則稱則稱G是是自補圖自補圖. 例：見書例：見書P280 圖圖14.6GG1814.2 通路與回路通路與回路定義定義14.11 給定圖給定圖G=（無向或有向的），（無向或有向的），G中中頂點與頂點與邊的交替序列邊的交替序列 = v0e1v1e2elvl，vi 1, vi 是是 ei 的端點的端點.(1) 通路與回路：通路與回路： 為為通路通路；若；若 v0

13、=vl， 為為回路回路，l 為為回路長回路長 度度.(2) 簡單通路與回路：所有邊各異，簡單通路與回路：所有邊各異， 為為簡單通路簡單通路，又若，又若v0=vl， 為為簡單回路簡單回路(3) 初級通路初級通路(路徑路徑)與初級回路與初級回路(圈圈)： 中所有頂點各異，則中所有頂點各異，則稱稱 為為初級通路初級通路(路徑路徑)，又若除，又若除v0=vl，所有的頂點各不相，所有的頂點各不相同且所有的邊各異，則稱同且所有的邊各異，則稱 為為初級回路初級回路(圈圈)(4) 復雜通路與回路：有邊重復出現(xiàn)復雜通路與回路：有邊重復出現(xiàn)19幾點說明幾點說明表示法表示法 定義表示法定義表示法 只用邊表示法只用邊

14、表示法 只用頂點表示法（在簡單圖中）只用頂點表示法（在簡單圖中） 混合表示法混合表示法環(huán)環(huán)（長為（長為1的圈）的長度為的圈）的長度為1，兩條平行邊構(gòu)成的圈長度為，兩條平行邊構(gòu)成的圈長度為 2，無向簡單圖中，圈長，無向簡單圖中，圈長 3，有向簡單圖中圈的長度，有向簡單圖中圈的長度 2. 不同的圈（以長度不同的圈（以長度 3的為例）的為例） 20通路與回路的長度通路與回路的長度定理定理14.5 在在n 階圖階圖G中，若從頂點中，若從頂點vi 到到vj（vi vj）存在通路，）存在通路，則從則從vi 到到 vj 存在長度小于或等于存在長度小于或等于n 1 的通路的通路.推論推論 在在 n 階圖階圖G

15、中，若從頂點中，若從頂點vi 到到 vj（vi vj）存在通路，則）存在通路，則從從vi 到到vj 存在長度小于或等于存在長度小于或等于n 1的初級通路（路徑）的初級通路（路徑）.定理定理14.6 在一個在一個n 階圖階圖G中，若存在中，若存在 vi 到自身的回路，則一到自身的回路，則一定存在定存在vi 到自身長度小于或等于到自身長度小于或等于 n 的回路的回路.推論推論 在一個在一個n 階圖階圖G中，若存在中，若存在 vi 到自身的簡單回路，則一到自身的簡單回路，則一定存在長度小于或等于定存在長度小于或等于n 的初級回路的初級回路.2114.3 圖的連通性圖的連通性無向圖的連通性無向圖的連通

16、性(1) 頂點之間的連通關系：頂點之間的連通關系：G=為無向圖為無向圖 若若 vi 與與 vj 之間有通路，則之間有通路，則 vi vj 是是V上的等價關系上的等價關系 R=| u,v V且且u v (2) G的連通性與連通分支的連通性與連通分支 若若 u,v V，u v，則稱，則稱G連通連通 V1,V2,Vk，稱，稱GV1, GV2, ,GVk為為連通分連通分 支支，其個數(shù)，其個數(shù) p(G)=k (k 1)； k=1，G連通連通22短程線與距離短程線與距離(3) 短程線與距離短程線與距離 u與與v之間的之間的短程線短程線：u v，u與與v之間長度最短的通路之間長度最短的通路 u與與v之間的之

17、間的距離距離：d(u,v)短程線的長度短程線的長度 d(u,v)的性質(zhì)：的性質(zhì)： d(u,v) 0, u v時時d(u,v)= d(u,v)=d(v,u) d(u,v)+d(v,w) d(u,w)23無向圖的連通度無向圖的連通度1. 刪除頂點及刪除邊刪除頂點及刪除邊 G v 從從G中將中將v及關聯(lián)的邊去掉及關聯(lián)的邊去掉 G V 從從G中刪除中刪除V 中所有的頂點中所有的頂點 G e 將將e從從G中去掉中去掉 G E 刪除刪除E 中所有邊中所有邊 2. 點割集與邊割集點割集與邊割集 點割集與割點點割集與割點 書書p283定義定義14.15 G=, VV V 為為點割集點割集p(G V )p(G)

18、且有極小性且有極小性 v為為割點割點v為點割集為點割集定義定義14.16 G=, EE E 是是邊割集邊割集p(G E )p(G)且有極小性且有極小性 e是是割邊割邊（橋）（橋）e為邊割集為邊割集24點割集與割點點割集與割點例例3 v1,v4，v6是點是點割集，割集，v6是割點是割點. v2,v5是點割集嗎？是點割集嗎？e1,e2，e1,e3,e5,e6，e8等是邊割集，等是邊割集，e8是是橋，橋，e7,e9,e5,e6 是邊割是邊割集嗎？集嗎？幾點說明：幾點說明：l Kn中無點割集，中無點割集，Nn中既無點割集，也無邊割集，其中中既無點割集，也無邊割集，其中Nn為為 n 階零圖階零圖. l

19、若若G 連通，連通，E 為邊割集，則為邊割集，則 p(G E )=2，V 為點割集，則為點割集，則 p(G V ) 2 25點連通度與邊連通度點連通度與邊連通度定義定義14.18 G為連通非完全圖為連通非完全圖 點連通度點連通度 (G) = min |V | V 為點割集為點割集 規(guī)定規(guī)定 (Kn) = n 1 若若G非連通，非連通， (G) = 0 若若 (G) k，則稱，則稱G為為 k-連通圖連通圖 定義定義14.19 設設G為連通圖為連通圖 邊連通度邊連通度 (G) = min|E | E 為邊割集為邊割集 若若G非連通，則非連通，則 (G) = 0 若若 (G) r，則稱，則稱G是是

20、r 邊邊-連通圖連通圖圖中，圖中， = =1，它是，它是 1-連通圖連通圖 和和 1邊邊-連通圖連通圖26有向圖的連通性有向圖的連通性定義定義14.20 D=為有向圖為有向圖 vi vj（vi 可達可達 vj）vi 到到vj 有通路有通路 vi vj（vi 與與vj 相互可達）相互可達）性質(zhì)性質(zhì) 具有自反性具有自反性(vi vi)、傳遞性、傳遞性 具有自反性、對稱性、傳遞性具有自反性、對稱性、傳遞性 vi 到到vj 的短程線與距離的短程線與距離類似于無向圖中，只需注意距離表示法的不同類似于無向圖中，只需注意距離表示法的不同(無向圖中無向圖中d(vi,vj)，有向圖中，有向圖中d) 及及 d無對

21、稱性無對稱性27有向圖的連通性及分類有向圖的連通性及分類定義定義14.22 D=為有向圖為有向圖 D弱連通弱連通(連通連通)基圖為無向連通圖基圖為無向連通圖 D單向連通單向連通 vi,vj V，vivj 或或 vjvi D強連通強連通 vi,vj V，vivj易知，強連通易知，強連通單向連通單向連通弱連通弱連通判別法判別法定理定理14.8 D強連通當且僅當強連通當且僅當D中存在經(jīng)過每個頂點至少一次中存在經(jīng)過每個頂點至少一次的回路的回路定理定理14.9 D單向連通當且僅當單向連通當且僅當D中存在經(jīng)過每個頂點至少一中存在經(jīng)過每個頂點至少一次的通路次的通路28二部圖二部圖定義定義14.23 設設 G

22、=為一個無向圖，若能將為一個無向圖，若能將 V分成分成 V1和和V2(V1 V2=V，V1 V2=)，使得，使得 G 中的每條邊的兩個端點都是中的每條邊的兩個端點都是一個屬于一個屬于V1，另一個屬于，另一個屬于V2，則稱，則稱 G 為為二部圖二部圖 ( 或稱或稱二分二分圖圖、偶圖偶圖等等 )，稱，稱V1和和V2為為互補頂點子集互補頂點子集，常將二部圖，常將二部圖G記為記為. 又若又若G是簡單二部圖，是簡單二部圖，V1中每個頂點均與中每個頂點均與V2中所有的頂點相中所有的頂點相鄰，則稱鄰，則稱G為為完全二部圖完全二部圖，記為，記為 Kr,s，其中，其中r=|V1|，s=|V2|. 注意，注意，n

23、 階零圖為二部圖階零圖為二部圖. 2914.4 圖的矩陣表示圖的矩陣表示無向圖的關聯(lián)矩陣（對圖無限制）無向圖的關聯(lián)矩陣（對圖無限制） P288定義定義14.24 無向圖無向圖G=，|V|=n，|E|=m，令，令 mij為為 vi 與與 ej的關聯(lián)次數(shù)，稱的關聯(lián)次數(shù)，稱(mij)n m為為G 的的關聯(lián)矩陣關聯(lián)矩陣，記為，記為M(G). 性質(zhì)性質(zhì)平行邊的列相同平行邊的列相同)4(2)3(),.,2 , 1()()2(),.,2 , 1(2)1(,11mmnivdmmjmjiijimjijniij 30jiijmjmjiijiijniijmnivdmvdmmjm,1110)3(,.,2 , 1),(

24、) 1(),() 1()2(),.,2 , 1(0) 1 ( 的的終終點點為為，不不關關聯(lián)聯(lián)與與，的的始始點點為為jijijiijevevevm10,1有向圖的關聯(lián)矩陣（無環(huán)有向圖）P288 定義定義14.25 有向圖有向圖D=，令，令則稱則稱 (mij)n m為為D的的關聯(lián)矩陣關聯(lián)矩陣，記為，記為M(D). (4) 平行邊對應的列相同平行邊對應的列相同性質(zhì)性質(zhì)有向圖的關聯(lián)矩陣31有向圖的鄰接矩陣（無限制）有向圖的鄰接矩陣（無限制）定義定義14.26 設有向圖設有向圖D=, V=v1, v2, , vn, E=e1, e2, , em, 令為頂點令為頂點 vi 鄰接到頂點鄰接到頂點 vj 邊的

25、條數(shù)，稱為邊的條數(shù)，稱為D的的鄰接矩鄰接矩陣陣，記作，記作A(D)，或簡記為，或簡記為A. 性質(zhì)性質(zhì) 的回路數(shù)的回路數(shù)中長度為中長度為的通路數(shù)的通路數(shù)中長度為中長度為1)4(1)3(,.,2 , 1),()2(,.,2 , 1),()1(1)1(,)1(1)1(1)1(DaDmanjvdanivdaniiijiijjniijinjij 32推論推論 設設Bl=A+A2+Al（l 1），則），則 Bl中元素中元素為D中長度為 l 的通路總數(shù)，)(lija)(liia ninjlija11)( niliia1)( ninjlijb11)( niliib1)(定理定理14.11 設設 A為有向圖為有

26、向圖 D 的鄰接矩陣，的鄰接矩陣，V=v1, v2, , vn為為頂點集，則頂點集，則 A 的的 l 次冪次冪 Al（l 1）中元素）中元素為D中vi 到vj長度為 l 的通路數(shù)，其中為vi到自身長度為 l 的回路數(shù)，而為為D中長度小于或等于中長度小于或等于 l 的回路數(shù)的回路數(shù)為為D中長度小于或等于中長度小于或等于 l 的通路數(shù)的通路數(shù). 鄰接矩陣的應用鄰接矩陣的應用為為D 中長度為中長度為 l 的回路總數(shù)的回路總數(shù). 33例例5 有向圖有向圖D如圖所示，求如圖所示，求 A, A2, A3, A4，并回答諸問題：，并回答諸問題：(1) D 中長度為中長度為1, 2, 3, 4的通路各有多少條

27、？其中回路分別為多的通路各有多少條？其中回路分別為多少條？少條？(2) D 中長度小于或等于中長度小于或等于4的通路為多少條？其中有多少條回路？的通路為多少條？其中有多少條回路？實例實例34 1004010410050001010310030104000110020102100300010101100101020001432AAAA(1) D中長度為中長度為1的通路為的通路為8條，其中有條，其中有1條是回路條是回路. D中長度為中長度為2的通路為的通路為11條，其中有條，其中有3條是回路條是回路. D中長度為中長度為3和和4的通路分別為的通路分別為14和和17條，回路分別條，回路分別 為為1與

28、與3條條.(2) D中長度小于等于中長度小于等于4的通路為的通路為50條，其中有條，其中有8條是回路條是回路.實例求解實例求解35 否否則則可可達達, 1, 0jiijvvp 1101110111110001P定義定義14.27 設設D=為有向圖為有向圖. V=v1, v2, , vn, 令令 有向圖的可達矩陣（無限制）有向圖的可達矩陣（無限制）稱稱 (pij)n n 為為D的可達矩陣，記作的可達矩陣，記作P(D)，簡記為，簡記為P. 由于由于 vi V，vivi，所以，所以P(D)主對角線上的元素全為主對角線上的元素全為1. 由定義不難看出由定義不難看出, D 強連通當且僅當強連通當且僅當

29、P(D)為全為全1矩陣矩陣. 下圖所示有向圖下圖所示有向圖 D 的可達矩陣為的可達矩陣為36第十四章第十四章 習題課習題課主要內(nèi)容主要內(nèi)容l 無向圖、有向圖、關聯(lián)與相鄰、簡單圖、完全圖、正則圖、無向圖、有向圖、關聯(lián)與相鄰、簡單圖、完全圖、正則圖、子圖、補圖；握手定理與推論；圖的同構(gòu)子圖、補圖；握手定理與推論；圖的同構(gòu)l 通路與回路及其分類通路與回路及其分類l 無向圖的連通性與連通度無向圖的連通性與連通度l 有向圖的連通性及其分類有向圖的連通性及其分類l 圖的矩陣表示圖的矩陣表示37基本要求基本要求l 深刻理解握手定理及推論的內(nèi)容并能靈活地應用它們深刻理解握手定理及推論的內(nèi)容并能靈活地應用它們l

30、 深刻理解圖同構(gòu)、簡單圖、完全圖、正則圖、子圖、補圖、深刻理解圖同構(gòu)、簡單圖、完全圖、正則圖、子圖、補圖、二部圖的概念以及它們的性質(zhì)及相互之間的關系二部圖的概念以及它們的性質(zhì)及相互之間的關系l 記住通路與回路的定義、分類及表示法記住通路與回路的定義、分類及表示法l 深刻理解與無向圖連通性、連通度有關的諸多概念深刻理解與無向圖連通性、連通度有關的諸多概念l 會判別有向圖連通性的類型會判別有向圖連通性的類型l 熟練掌握用鄰接矩陣及其冪求有向圖中通路與回路數(shù)的方熟練掌握用鄰接矩陣及其冪求有向圖中通路與回路數(shù)的方法，會求可達矩陣法，會求可達矩陣 3819階無向圖階無向圖G中，每個頂點的度數(shù)不是中，每個

31、頂點的度數(shù)不是5就是就是6. 證明證明G中至少有中至少有5個個6度頂點或至少有度頂點或至少有6個個5度頂點度頂點. 練習練習1證證 關鍵是利用握手定理的推論關鍵是利用握手定理的推論. 方法一：窮舉法方法一：窮舉法設設G中有中有x個個5度頂點，則必有度頂點，則必有(9 x)個個6度頂點，由握手定度頂點，由握手定理推論可知，理推論可知，(x,9 x)只有只有5種可能：種可能：(0,9), (2,7), (4,5), (6,3), (8,1）它們都滿足要求）它們都滿足要求. 方法二：反證法方法二：反證法否則，由握手定理推論可知，否則，由握手定理推論可知，“G至多有至多有4個個5度頂點并且度頂點并且至多有至多有4個個6度頂點度頂點”，這與，這與G是是 9 階圖矛盾階圖矛盾. 392數(shù)組數(shù)組2, 2, 2, 2, 3, 3能簡單圖化嗎？若能，畫出盡可能多圖能簡單圖化嗎？若能，畫出盡可能多圖來來. 練習練習2只要能畫出只要能畫出6 階無向簡單圖，就說明它可簡單圖化階無向簡單圖，就說明它可簡單圖化. 下圖的下圖的4個圖都以此數(shù)列為度數(shù)