圖論基本概念課件

1、第五部分 圖論本部分主要內(nèi)容 圖的基本概念 歐拉圖、哈密頓圖 樹(shù)1圖論基本概念緒論圖論的歷史： 圖論的第一篇論文是瑞士數(shù)學(xué)家歐拉（Euler）發(fā)表于1736年出版的圣彼得堡科學(xué)院刊物中。討論一個(gè)所謂Konigsberg Seven Bridges Problem。2圖論基本概念緒論圖論的作用：圖與計(jì)算機(jī)：計(jì)算機(jī)中數(shù)據(jù)結(jié)構(gòu)，離不開(kāi)數(shù)組、串、各種鏈接表、樹(shù)和圖，因此圖是計(jì)算機(jī)中數(shù)據(jù)表示、存儲(chǔ)和運(yùn)算的基礎(chǔ) 圖與網(wǎng)絡(luò)： 最大流問(wèn)題：假設(shè)從城市P到城市Q的一個(gè)公路網(wǎng)， 公路網(wǎng)中每段公路上每天可以通過(guò)的汽車(chē)的數(shù)量有上限，那么經(jīng)過(guò)該公路網(wǎng)，每天最多可以有多少輛汽車(chē)從城市P開(kāi)到城市Q？ 最優(yōu)支撐樹(shù)問(wèn)題：某一地

2、區(qū)有若干個(gè)主要城市，擬修建高速公路把這些城市連接起來(lái)，使得從其中任何一個(gè)城市都可以經(jīng)高速公路直接或間接到達(dá)另一個(gè)城市。假設(shè)已經(jīng)知道了任意兩個(gè)城市之間修建高速公路的成本，那么應(yīng)如何決定在哪些城市間修建高速公路，使得總成本最??？3圖論基本概念第十四章 圖的基本概念主要內(nèi)容圖通路與回路圖的連通性圖的矩陣表示圖的運(yùn)算預(yù)備知識(shí)多重集合元素可以重復(fù)出現(xiàn)的集合無(wú)序集AB=(x,y) | xAyB4圖論基本概念14.1 圖 無(wú)向圖G = , 其中(1) V 為頂點(diǎn)集，元素稱(chēng)為頂點(diǎn) Vertex(2) E為VV 的多重集，其元素稱(chēng)為無(wú)向邊，簡(jiǎn)稱(chēng)邊 Edge實(shí)例 設(shè) V = v1, v2, ,v5, E = (v

3、1,v1), (v1,v2), (v2,v3), (v2,v3), (v2,v5), (v1,v5), (v4,v5) 則 G = 為一無(wú)向圖5圖論基本概念有向圖 有向圖D=, 只需注意E是VV 的多重子集圖2表示的是一個(gè)有向圖，試寫(xiě)出它的V 和 E 注意：圖的數(shù)學(xué)定義與圖形表示，在同構(gòu)（待敘）的意義下是一一對(duì)應(yīng)的6圖論基本概念相關(guān)概念1. 圖 可用G泛指圖（無(wú)向的或有向的） V(G), E(G), |V(G)|, |E(G)| n階圖：n 個(gè)頂點(diǎn)的圖2. 有限圖3. n 階零圖（0條邊）與平凡圖（1個(gè)頂點(diǎn)）4. 空?qǐng)D（運(yùn)算中出現(xiàn)）5. 用 ek 表示無(wú)向邊或有向邊7圖論基本概念相關(guān)概念6.

4、頂點(diǎn)與邊的關(guān)聯(lián)關(guān)系 關(guān)聯(lián)、關(guān)聯(lián)次數(shù) 環(huán) 孤立點(diǎn)7. 頂點(diǎn)之間的相鄰與鄰接關(guān)系8圖論基本概念8. 鄰域與關(guān)聯(lián)集 vV(G) (G為無(wú)向圖) v 的關(guān)聯(lián)集 vV(D) (D為有向圖)9. 標(biāo)定圖與非標(biāo)定圖(頂點(diǎn)和邊指定編號(hào)的）10. 基圖（有向圖的有向邊改為無(wú)向邊）相關(guān)概念9圖論基本概念多重圖與簡(jiǎn)單圖定義14.3 (1) 無(wú)向圖中的平行邊及重?cái)?shù) 關(guān)聯(lián)一對(duì)頂點(diǎn)的邊多于一條，條數(shù)稱(chēng)為重?cái)?shù) (2) 有向圖中的平行邊及重?cái)?shù)（注意方向性） (3) 多重圖 (4) 簡(jiǎn)單圖（無(wú)平行邊和環(huán)）簡(jiǎn)單圖是極其重要的概念 10圖論基本概念頂點(diǎn)的度數(shù) (1) 設(shè)G=為無(wú)向圖, vV, d(v)v的度數(shù), 簡(jiǎn)稱(chēng)度 (2) 設(shè)

5、D=為有向圖, vV, d+(v)v的出度 d(v)v的入度 d(v)v的度或度數(shù) (3) (G)（最大度）, (G)（最小度） 無(wú)向圖中 (4) +(D), +(D), (D), (D), (D), (D) (5) 度數(shù)為1的點(diǎn)稱(chēng)為懸掛點(diǎn)，關(guān)聯(lián)的邊為懸掛邊； 奇頂點(diǎn)度與偶度頂點(diǎn)11圖論基本概念定理 設(shè)G=為任意無(wú)向圖，V=v1,v2,vn, |E|=m, 則證 G中每條邊 (包括環(huán)) 均有兩個(gè)端點(diǎn)，所以在計(jì)算G中各頂點(diǎn)度數(shù)之和時(shí)，每條邊均提供2度，m 條邊共提供 2m 度.此二定理是歐拉1736年給出，是圖論的基本定理握手定理 設(shè)D=為任意有向圖，V=v1,v2,vn, |E|=m, 則12

6、圖論基本概念握手定理推論推論 任何圖 (無(wú)向或有向) 中，奇度頂點(diǎn)的個(gè)數(shù)是偶數(shù).證 設(shè)G=為任意圖，令 V1=v | vV d(v)為奇數(shù) V2=v | vV d(v)為偶數(shù) 則V1V2=V, V1V2=，由握手定理可知由于2m, 均為偶數(shù)，所以 為偶數(shù)，但因?yàn)閂1中頂點(diǎn)度數(shù)為奇數(shù)，所以|V1|必為偶數(shù). 13圖論基本概念圖的度數(shù)列1 . V=v1, v2, , vn為無(wú)向圖G的頂點(diǎn)集，稱(chēng)d(v1), d(v2), , d(vn)為G的度數(shù)列 2. V=v1, v2, , vn為有向圖D的頂點(diǎn)集， D的度數(shù)列：d(v1), d(v2), , d(vn) D的出度列：d+(v1), d+(v2)

7、, , d+(vn) D的入度列：d(v1), d(v2), , d(vn) 3. 非負(fù)整數(shù)列d=(d1, d2, , dn)是可圖化的，是可簡(jiǎn)單圖化的.易知：(2, 4, 6, 8, 10)，(1, 3, 3, 3, 4) 是可圖化的，后者又是可簡(jiǎn)單圖化的，而(2, 2, 3, 4, 5)，(3, 3, 3, 4) 都不是可簡(jiǎn)單圖化的，特別是后者也不是可圖化的14圖論基本概念圖的同構(gòu) 設(shè)G1=, G2=為兩個(gè)無(wú)向圖(兩個(gè)有向圖)，若存在雙射函數(shù)f:V1V2, 對(duì)于vi,vjV1, (vi,vj)E1 當(dāng)且僅當(dāng) (f(vi),f(vj)E2 （E1 當(dāng)且僅當(dāng) E2 )并且, (vi,vj)（）

8、與 (f(vi),f(vj)（）的重?cái)?shù)相同，則稱(chēng)G1與G2是同構(gòu)的，記作G1G2. 圖之間的同構(gòu)關(guān)系具有自反性、對(duì)稱(chēng)性和傳遞性.能找到多條同構(gòu)的必要條件，但它們?nèi)皇浅浞謼l件： 邊數(shù)相同，頂點(diǎn)數(shù)相同; 度數(shù)列相同; 對(duì)應(yīng)頂點(diǎn)的關(guān)聯(lián)集及鄰域的元素個(gè)數(shù)相同，等等 若破壞必要條件，則兩圖不同構(gòu)判斷兩個(gè)圖同構(gòu)是個(gè)難題15圖論基本概念圖同構(gòu)的實(shí)例圖中(1)與(2)的度數(shù)列相同，它們同構(gòu)嗎？為什么？ (1) (2) (3) (4) 圖中，(1)與(2)不同構(gòu)（度數(shù)列不同），(3)與(4)也不同構(gòu). (1) (2) 16圖論基本概念n 階完全圖與競(jìng)賽圖定義14.6 (1) n (n1) 階無(wú)向完全圖每個(gè)頂點(diǎn)

9、與其余頂點(diǎn)均相鄰的無(wú)向簡(jiǎn)單圖，記作 Kn.簡(jiǎn)單性質(zhì)：邊數(shù)(2) n (n1)階有向完全圖每對(duì)頂點(diǎn)之間均有兩條方向相反的有向邊的有向簡(jiǎn)單圖.簡(jiǎn)單性質(zhì)： (3) n (n1) 階競(jìng)賽圖基圖為Kn的有向簡(jiǎn)單圖.簡(jiǎn)單性質(zhì)：邊數(shù) 17圖論基本概念n 階 k 正則圖(1)為K5，(2)為3階有向完全圖，(3)為4階競(jìng)賽圖. (1) (2) (3) n 階k正則圖=k 的無(wú)向簡(jiǎn)單圖簡(jiǎn)單性質(zhì)：邊數(shù)（由握手定理得）Kn是 n1正則圖，彼得松圖（見(jiàn)書(shū)上圖14.3(1) 所示，記住它）18圖論基本概念子圖 G=, G=(1) GG G為G的子圖，G為G的母圖(2) 若GG且V=V，則稱(chēng)G為G的生成子圖(3) 若VV

10、或EE，稱(chēng)G為G的真子圖(4) V（VV且V）的導(dǎo)出子圖，記作GV(5) E（EE且E）的導(dǎo)出子圖，記作GE19圖論基本概念例2 畫(huà)出K4的所有非同構(gòu)的生成子圖實(shí)例20圖論基本概念補(bǔ)圖 設(shè)G=為n階無(wú)向簡(jiǎn)單圖，以V為頂點(diǎn)集，以所有使G成為完全圖Kn的添加邊組成的集合為邊集的圖，稱(chēng)為G的補(bǔ)圖，記作 .若G , 則稱(chēng)G是自補(bǔ)圖. 相對(duì)于K4, 求上面圖中所有圖的補(bǔ)圖，并指出哪些是自補(bǔ)圖. 問(wèn)：互為自補(bǔ)圖的兩個(gè)圖的邊數(shù)有何關(guān)系？21圖論基本概念14.2 通路與回路 給定圖G=（無(wú)向或有向的），G中頂點(diǎn)與邊的交替序列 = v0e1v1e2elvl，vi1, vi 是 ei 的端點(diǎn).(1) 通路與回路：

11、 為通路；若 v0=vl， 為回路，l 為回路長(zhǎng) 度.(2) 簡(jiǎn)單通路與回路：所有邊各異， 為簡(jiǎn)單通路，又若v0=vl， 為簡(jiǎn)單回路(3) 初級(jí)通路(路徑)與初級(jí)回路(圈)： 中所有頂點(diǎn)各異，則稱(chēng) 為初級(jí)通路(路徑)，又若除v0=vl，所有的頂點(diǎn)各不相同且所有的邊各異，則稱(chēng) 為初級(jí)回路(圈)(4) 復(fù)雜通路與回路：有邊重復(fù)出現(xiàn)22圖論基本概念幾點(diǎn)說(shuō)明表示法 定義表示法 只用邊表示法 只用頂點(diǎn)表示法（在簡(jiǎn)單圖中） 混合表示法環(huán)（長(zhǎng)為1的圈）的長(zhǎng)度為1，兩條平行邊構(gòu)成的圈長(zhǎng)度為 2，無(wú)向簡(jiǎn)單圖中，圈長(zhǎng)3，有向簡(jiǎn)單圖中圈的長(zhǎng)度2. 不同的圈（以長(zhǎng)度3的為例） 定義意義下 無(wú)向圖：圖中長(zhǎng)度為l（l3）

12、的圈，定義意義下為2l個(gè) 有向圖：圖中長(zhǎng)度為l（l3）的圈，定義意義下為l個(gè) 同構(gòu)意義下：長(zhǎng)度相同的圈均為1個(gè)試討論l=3和l=4的情況23圖論基本概念通路與回路的長(zhǎng)度 在n 階圖G中，若從頂點(diǎn)vi 到vj（vivj）存在通路，則從vi 到 vj 存在長(zhǎng)度小于或等于n1 的通路.推論 在 n 階圖G中，若從頂點(diǎn)vi 到 vj（vivj）存在通路，則從vi 到vj 存在長(zhǎng)度小于或等于n1的初級(jí)通路（路徑）. 在一個(gè)n 階圖G中，若存在 vi 到自身的回路，則一定存在vi 到自身長(zhǎng)度小于或等于 n 的回路.推論 在一個(gè)n 階圖G中，若存在 vi 到自身的簡(jiǎn)單回路，則一定存在長(zhǎng)度小于或等于n 的初級(jí)

13、回路.24圖論基本概念 圖的連通性無(wú)向圖的連通性(1) 頂點(diǎn)之間的連通關(guān)系：G=為無(wú)向圖 若 vi 與 vj 之間有通路，則 vivj 是V上的等價(jià)關(guān)系 R=| u,v V且uv (2) G的連通性與連通分支 若u,vV，uv，則稱(chēng)G連通 V/R=V1,V2,Vk，稱(chēng)GV1, GV2, ,GVk為連通分 支，其個(gè)數(shù) p(G)=k (k1)； k=1，G連通25圖論基本概念短程線與距離(3) 短程線與距離 u與v之間的短程線：uv，u與v之間長(zhǎng)度最短的通路 u與v之間的距離：d(u,v)短程線的長(zhǎng)度 d(u,v)的性質(zhì)： d(u,v)0, uv時(shí)d(u,v)= d(u,v)=d(v,u) d(u

14、,v)+d(v,w)d(u,w)26圖論基本概念無(wú)向圖的連通度1. 刪除頂點(diǎn)及刪除邊 Gv 從G中將v及關(guān)聯(lián)的邊去掉 GV從G中刪除V中所有的頂點(diǎn) Ge 將e從G中去掉 GE刪除E中所有邊 2. 點(diǎn)割集與邊割集 點(diǎn)割集與割點(diǎn) G=, VV V為點(diǎn)割集p(GV)p(G)且有極小性 v為割點(diǎn)v為點(diǎn)割集 G=, EE E是邊割集p(GE)p(G)且有極小性 e是割邊（橋）e為邊割集27圖論基本概念點(diǎn)割集與割點(diǎn)例3 v1,v4，v6是點(diǎn)割集，v6是割點(diǎn). v2,v5是點(diǎn)割集嗎？e1,e2，e1,e3,e5,e6，e8等是邊割集，e8是橋，e7,e9,e5,e6 是邊割集嗎？幾點(diǎn)說(shuō)明：Kn中無(wú)點(diǎn)割集，N

15、n中既無(wú)點(diǎn)割集，也無(wú)邊割集，其中Nn為 n 階零圖. 若G 連通，E為邊割集，則 p(GE)=2，V為點(diǎn)割集，則 p(GV)2 28圖論基本概念點(diǎn)連通度與邊連通度 G為連通非完全圖 點(diǎn)連通度 (G) = min |V |V 為點(diǎn)割集 規(guī)定 (Kn) = n1 若G非連通，(G) = 0 若 (G)k，則稱(chēng)G為 k-連通圖 設(shè)G為連通圖 邊連通度(G) = min|E|E為邊割集 若G非連通，則(G) = 0 若(G)r，則稱(chēng)G是 r 邊-連通圖圖中， =1，它是 1-連通圖 和 1邊-連通圖29圖論基本概念幾點(diǎn)說(shuō)明(Kn)=(Kn)=n1G非連通，則 =0若G中有割點(diǎn)，則=1，若有橋，則=1若

16、(G)=k, 則G是1-連通圖，2-連通圖，k-連通圖，但不是(k+s)-連通圖，s1若(G)=r, 則G是1-邊連通圖，2-邊連通圖，r-邊連通圖，但不是(r+s)-邊連通圖，s1, , 之間的關(guān)系.定理 (G)(G)(G)請(qǐng)畫(huà)出一個(gè)的無(wú)向簡(jiǎn)單圖30圖論基本概念有向圖的連通性 D=為有向圖 vi vj（vi 可達(dá) vj）vi 到vj 有通路 vi vj（vi 與vj 相互可達(dá)）性質(zhì) 具有自反性(vi vi)、傳遞性 具有自反性、對(duì)稱(chēng)性、傳遞性 vi 到vj 的短程線與距離類(lèi)似于無(wú)向圖中，只需注意距離表示法的不同(無(wú)向圖中d(vi,vj)，有向圖中d) 及 d無(wú)對(duì)稱(chēng)性31圖論基本概念有向圖的連

17、通性及分類(lèi) D=為有向圖 D弱連通(連通)基圖為無(wú)向連通圖 D單向連通vi,vjV，vivj 或 vjvi D強(qiáng)連通vi,vjV，vivj易知，強(qiáng)連通單向連通弱連通判別法 D強(qiáng)連通當(dāng)且僅當(dāng)D中存在經(jīng)過(guò)每個(gè)頂點(diǎn)至少一次的回路 D單向連通當(dāng)且僅當(dāng)D中存在經(jīng)過(guò)每個(gè)頂點(diǎn)至少一次的通路32圖論基本概念擴(kuò)大路徑法無(wú)向圖中設(shè)G=為 n 階無(wú)向圖，E. 設(shè) l 為G中一條路徑，若此路徑的始點(diǎn)或終點(diǎn)與通路外的頂點(diǎn)相鄰，就將它們擴(kuò)到通路中來(lái)，繼續(xù)這一過(guò)程，直到最后得到的通路的兩個(gè)端點(diǎn)不與通路外的頂點(diǎn)相鄰為止. 設(shè)最后得到的路徑為l+k（長(zhǎng)度為 l 的路徑擴(kuò)大成了長(zhǎng)度為 l+k 的路徑），稱(chēng)l+k為“極大路徑”，稱(chēng)

18、使用此種方法證明問(wèn)題的方法為“擴(kuò)大路徑法”.有向圖中類(lèi)似討論，只需注意，在每步擴(kuò)大中保證有向邊方向的一致性.33圖論基本概念實(shí)例由某條路徑擴(kuò)大出的極大路徑不惟一，極大路徑不一定是圖中最長(zhǎng)的路徑上圖中，(1)中實(shí)線邊所示的長(zhǎng)為2的初始路徑，(2),(3),(4)中實(shí)線邊所示的都是它擴(kuò)展成的極大路徑. 還能找到另外的極大路徑嗎？ (1) (2) (4) (3)34圖論基本概念擴(kuò)大路徑法的應(yīng)用例4 設(shè) G 為 n（n3）階無(wú)向簡(jiǎn)單圖， 2，證明G 中存在長(zhǎng)度 +1 的圈.證 設(shè) = v0v1vl 是由初始路徑 0 用擴(kuò)大路徑法的得到的極大路徑，則 l （為什么？）. 因?yàn)関0 不與 外頂點(diǎn)相鄰，又

19、d(v0) ，因而在 上除 v1外，至少還存在 1個(gè)頂點(diǎn)與 v0 相鄰. 設(shè) vx 是離 v0 最遠(yuǎn)的頂點(diǎn)，于是 v0v1vxv0 為 G 中長(zhǎng)度 +1 的圈. 35圖論基本概念二部圖 設(shè) G=為一個(gè)無(wú)向圖，若能將 V分成 V1和V2(V1V2=V，V1V2=)，使得 G 中的每條邊的兩個(gè)端點(diǎn)都是一個(gè)屬于V1，另一個(gè)屬于V2，則稱(chēng) G 為二部圖 ( 或稱(chēng)二分圖、偶圖等 )，稱(chēng)V1和V2為互補(bǔ)頂點(diǎn)子集，常將二部圖G記為. 又若G是簡(jiǎn)單二部圖，V1中每個(gè)頂點(diǎn)均與V2中所有的頂點(diǎn)相鄰，則稱(chēng)G為完全二部圖，記為 Kr,s，其中r=|V1|，s=|V2|. 注意，n 階零圖為二部圖. 36圖論基本概念二

20、部圖的判別法 無(wú)向圖G=是二部圖當(dāng)且僅當(dāng)G中無(wú)奇圈 由定理14.10可知圖9中各圖都是二部圖，哪些是完全二部圖？哪些圖是同構(gòu)的？37圖論基本概念14.4 圖的矩陣表示無(wú)向圖的關(guān)聯(lián)矩陣（對(duì)圖無(wú)限制） 無(wú)向圖G=，|V|=n，|E|=m，令 mij為 vi 與 ej的關(guān)聯(lián)次數(shù)，稱(chēng)(mij)nm為G 的關(guān)聯(lián)矩陣，記為M(G). 性質(zhì)38圖論基本概念有向圖的關(guān)聯(lián)矩陣（無(wú)環(huán)有向圖） 定義 有向圖D=，令則稱(chēng) (mij)nm為D的關(guān)聯(lián)矩陣，記為M(D). (4) 平行邊對(duì)應(yīng)的列相同性質(zhì)有向圖的關(guān)聯(lián)矩陣39圖論基本概念有向圖的鄰接矩陣（無(wú)限制） 設(shè)有向圖D=, V=v1, v2, , vn, E=e1, e

21、2, , em, 令為頂點(diǎn) vi 鄰接到頂點(diǎn) vj 邊的條數(shù)，稱(chēng)為D的鄰接矩陣，記作A(D)，或簡(jiǎn)記為A. 性質(zhì) 40圖論基本概念推論 設(shè)Bl=A+A2+Al（l1），則 Bl中元素為D中長(zhǎng)度為 l 的通路總數(shù)， 設(shè) A為有向圖 D 的鄰接矩陣，V=v1, v2, , vn為頂點(diǎn)集，則 A 的 l 次冪 Al（l1）中元素為D中vi 到vj長(zhǎng)度為 l 的通路數(shù)，其中為vi到自身長(zhǎng)度為 l 的回路數(shù)，而為D中長(zhǎng)度小于或等于 l 的回路數(shù)為D中長(zhǎng)度小于或等于 l 的通路數(shù). 鄰接矩陣的應(yīng)用為D 中長(zhǎng)度為 l 的回路總數(shù). 41圖論基本概念例5 有向圖D如圖所示，求 A, A2, A3, A4，并回

22、答諸問(wèn)題：(1) D 中長(zhǎng)度為1, 2, 3, 4的通路各有多少條？其中回路分別為多少條？(2) D 中長(zhǎng)度小于或等于4的通路為多少條？其中有多少條回路？實(shí)例42圖論基本概念(1) D中長(zhǎng)度為1的通路為8條，其中有1條是回路. D中長(zhǎng)度為2的通路為11條，其中有3條是回路. D中長(zhǎng)度為3和4的通路分別為14和17條，回路分別 為1與3條.(2) D中長(zhǎng)度小于等于4的通路為50條，其中有8條是回路.實(shí)例求解43圖論基本概念 設(shè)D=為有向圖. V=v1, v2, , vn, 令 有向圖的可達(dá)矩陣（無(wú)限制）稱(chēng) (pij)nn 為D的可達(dá)矩陣，記作P(D)，簡(jiǎn)記為P. 由于viV，vivi，所以P(D

23、)主對(duì)角線上的元素全為1. 由定義不難看出, D 強(qiáng)連通當(dāng)且僅當(dāng) P(D)為全1矩陣. 下圖所示有向圖 D 的可達(dá)矩陣為44圖論基本概念第十四章 習(xí)題課主要內(nèi)容無(wú)向圖、有向圖、關(guān)聯(lián)與相鄰、簡(jiǎn)單圖、完全圖、正則圖、子圖、補(bǔ)圖；握手定理與推論；圖的同構(gòu)通路與回路及其分類(lèi)無(wú)向圖的連通性與連通度有向圖的連通性及其分類(lèi)圖的矩陣表示45圖論基本概念基本要求深刻理解握手定理及推論的內(nèi)容并能靈活地應(yīng)用它們深刻理解圖同構(gòu)、簡(jiǎn)單圖、完全圖、正則圖、子圖、補(bǔ)圖、二部圖的概念以及它們的性質(zhì)及相互之間的關(guān)系記住通路與回路的定義、分類(lèi)及表示法深刻理解與無(wú)向圖連通性、連通度有關(guān)的諸多概念會(huì)判別有向圖連通性的類(lèi)型熟練掌握用鄰接矩陣及其冪求有向圖中通路與回路數(shù)的方法，會(huì)求可達(dá)矩陣 46圖論基本概念19階無(wú)向圖G中，每個(gè)頂點(diǎn)的度數(shù)不是5就是6. 證明G中至少有5個(gè)6度頂點(diǎn)或至少有6個(gè)5度頂點(diǎn). 練習(xí)1證 關(guān)鍵是利用握手定理的推論. 方法一：窮舉法設(shè)G中有x個(gè)5度頂點(diǎn)，則必有(9x)個(gè)6度頂點(diǎn)，由握手定理推論可知，(x,9x)只有5種可能：(0,9), (2,7), (4,5), (6,3), (8,1）它們都滿(mǎn)足要求. 方法二：反證法否則，由握手定理推論可知，“G