第6章—一些特殊的圖

1、第第6章章 一些特殊的圖一些特殊的圖內(nèi)容導(dǎo)讀內(nèi)容導(dǎo)讀: 二部圖二部圖 歐拉圖歐拉圖哈密頓圖哈密頓圖平面圖平面圖難點(diǎn)難點(diǎn):各種圖的判別定理各種圖的判別定理2022-4-21離散數(shù)學(xué)1 2022-4-21離散數(shù)學(xué)2(1)(2) 設(shè)無向圖設(shè)無向圖 G = 有兩個(gè)有兩個(gè)V的子集的子集V1,V2, 它們具有滿足：它們具有滿足： V1V2= V V1V2= 圖圖G中的每一邊中的每一邊 e 均具有均具有 e = ( vi , vj ) 其中：其中： vi V1 , vj V2 則稱則稱G是一個(gè)是一個(gè)二部圖二部圖，2022-4-21離散數(shù)學(xué)3定義定義6.1 若一個(gè)圖若一個(gè)圖G的結(jié)點(diǎn)集的結(jié)點(diǎn)集V能劃分為兩個(gè)子能

2、劃分為兩個(gè)子集集V1和和V2，使得使得G的每一條邊的每一條邊vi,vj滿足滿足viV1, vjV2 , 則稱則稱G是一個(gè)是一個(gè)二部圖二部圖， V1和和V2稱為稱為G的的互補(bǔ)結(jié)點(diǎn)子集。此時(shí)可將互補(bǔ)結(jié)點(diǎn)子集。此時(shí)可將G記成記成 G = 若若V1中任一結(jié)點(diǎn)與中任一結(jié)點(diǎn)與V2中每一結(jié)點(diǎn)均有邊相連中每一結(jié)點(diǎn)均有邊相連接接, 則稱二部圖為則稱二部圖為完全二部圖完全二部圖。若。若|V1|=n, |V2 |=m則記完全二部圖則記完全二部圖G為為Kn, m。(1)(2)K2,3K3,32022-4-21離散數(shù)學(xué)4(1)(2)例例 6.1 判斷下列圖是否是二部圖？判斷下列圖是否是二部圖？v1v3v5v2v4v6v

3、1v4v8v5v2v3v6v7v1v2v3v4v5(3)在圖在圖 (1) 中中, V1=v1, v3, v5, V2=v2, v4, v6, 是一個(gè)完是一個(gè)完全二部圖。在圖全二部圖。在圖 (2) 中中, V1=v1, v4, v8, v5, V2=v2, v3, v7, v6, 是一個(gè)二部圖。在圖是一個(gè)二部圖。在圖 (3) 中中, 對(duì)于對(duì)于其中的頂點(diǎn)無法將它們分到兩個(gè)不同的子集其中的頂點(diǎn)無法將它們分到兩個(gè)不同的子集V1和和 V2,使其邊能滿足二部圖的定義使其邊能滿足二部圖的定義, 所以它不是二部圖。所以它不是二部圖。二部圖是不是一定是連通圖?2022-4-21離散數(shù)學(xué)5(4)(5)定理定理6.

4、1 一個(gè)無向圖一個(gè)無向圖 G = 是二部圖是二部圖當(dāng)且當(dāng)且僅當(dāng)僅當(dāng)G中無奇數(shù)長(zhǎng)度的回路。中無奇數(shù)長(zhǎng)度的回路。 下圖所示前下圖所示前3個(gè)圖中個(gè)圖中, 均無奇數(shù)長(zhǎng)度的回路均無奇數(shù)長(zhǎng)度的回路, 所以它們都是二部圖所以它們都是二部圖, 其中圖其中圖(2)所示為所示為K2, 3, 圖圖(3)所示為所示為K3, 3, 它們分別與圖它們分別與圖(4)和和(5)同構(gòu)同構(gòu)。(1)(2)(3)2022-4-21離散數(shù)學(xué)6(1)(2)e1e2e3e4e5e6e7e1e2e3e4e5e6e7在圖在圖(1)中，中，e1, e1, e7 , e5, e4 , e6 等都是圖中等都是圖中的匹配。的匹配。在圖在圖(2)中找出

5、匹配。中找出匹配。定義定義6.2 設(shè)設(shè) G = 為無向圖為無向圖, E* E, 若若E*中任意兩中任意兩條邊均不相鄰條邊均不相鄰, 則子集則子集E*稱為稱為G中的中的匹配匹配(或或邊獨(dú)邊獨(dú)立集立集), 并把并把E*中的邊所關(guān)聯(lián)的兩個(gè)結(jié)點(diǎn)稱為在中的邊所關(guān)聯(lián)的兩個(gè)結(jié)點(diǎn)稱為在E*下是匹配的。下是匹配的。2022-4-21離散數(shù)學(xué)7(1)(2)e1e2e3e4e5e6e7e1e2e3e4e5e6e7在圖在圖(1)中中, e5, e1, e7 , e4 , e6 e3, e7 , e2, e6 是是極大匹配極大匹配，后后4個(gè)是最大匹配，匹配數(shù)個(gè)是最大匹配，匹配數(shù) 1 =2。若在若在E*中再加入任何一條邊

6、就都不是匹配了中再加入任何一條邊就都不是匹配了, 則稱則稱E*為為極大匹配極大匹配。邊數(shù)最多的極大匹配稱為。邊數(shù)最多的極大匹配稱為最大匹配最大匹配，最大匹配中的元素，最大匹配中的元素(邊邊)的個(gè)數(shù)稱為的個(gè)數(shù)稱為G的的匹配數(shù)匹配數(shù)，記為，記為 1(G), 簡(jiǎn)記為簡(jiǎn)記為 1 。2022-4-21離散數(shù)學(xué)8(2)e1e2e3e4e5e6e7在圖在圖(2)中中, e2, e5 , e3 , e6 ,e1 , e7 , e4 都是極大匹都是極大匹配配, 其中其中e1, e7, e4 是最大匹配。是最大匹配。2022-4-21離散數(shù)學(xué)9(1)(2)e1e2e3e4e5e6e7e1e2e3e4e5e6e7在

7、圖在圖(1)中中不存在完美匹配。不存在完美匹配。在圖在圖(2)中中,e1, e7, e4 是最大匹配，同時(shí)也是是最大匹配，同時(shí)也是完美匹配。完美匹配。今后常用今后常用M表示匹配，設(shè)表示匹配，設(shè)M為為G中一個(gè)匹配，中一個(gè)匹配，v V(G), 若存在若存在M中的邊與中的邊與v關(guān)聯(lián)，則稱關(guān)聯(lián)，則稱v為為M飽和點(diǎn)飽和點(diǎn)，否則，否則v為為M非飽和點(diǎn)非飽和點(diǎn)，若，若G中每個(gè)頂點(diǎn)中每個(gè)頂點(diǎn)都是飽和點(diǎn)，則稱都是飽和點(diǎn)，則稱M為為G中中完美匹配完美匹配。2022-4-21離散數(shù)學(xué)10v1v2v3v4v5v6v7v8v9v1v2v3v4v5v6v7v8(2)(1)在圖在圖(1)中的一個(gè)最大匹配是中的一個(gè)最大匹配是

8、 M=(v1, v2), (v3, v9), (v5, v6), (v7, v8)在圖在圖(2)中的一個(gè)完美匹配是中的一個(gè)完美匹配是 M=(v1, v2), (v3, v4), (v5, v6), (v7, v8)2022-4-21離散數(shù)學(xué)11定義定義6.3 設(shè)設(shè) G = 為二部圖為二部圖, M為為G中一個(gè)最大中一個(gè)最大匹配匹配, 若若 |M| = min |V1|, |V2| , 則稱則稱M為為G中的一中的一個(gè)個(gè)完備匹配完備匹配, 此時(shí)若此時(shí)若|V1| |V2|, 則稱則稱M為為V1到到 V2的的一個(gè)完備匹配。如果一個(gè)完備匹配。如果|V1|= |V2| ,這時(shí)這時(shí)M為為G中的完中的完美匹配。

9、美匹配。G1G2G3在上圖中在上圖中, e1, e2 為為G1中的最大匹配中的最大匹配, G1中不存在完備中不存在完備匹配匹配, 更無完美匹配。更無完美匹配。 G2中中e1, e2 , e3為完備匹配為完備匹配, 但但G2中無完美匹配。中無完美匹配。 G3中中e1,e2, e3為完備匹配為完備匹配, 同時(shí)也是完同時(shí)也是完美匹配。美匹配。e1e2e1e2e3e1e2e32022-4-21離散數(shù)學(xué)12例例6.2 6.2 我們班級(jí)成立了我們班級(jí)成立了 3 3 個(gè)運(yùn)動(dòng)隊(duì)個(gè)運(yùn)動(dòng)隊(duì): :籃球隊(duì)、排球隊(duì)和足球隊(duì)。籃球隊(duì)、排球隊(duì)和足球隊(duì)。今有今有張、王、李、趙、陳張、王、李、趙、陳5 5位同學(xué)位同學(xué)，若已知，

10、若已知張、王為籃球隊(duì)員張、王為籃球隊(duì)員；張、李、趙為排球隊(duì)員張、李、趙為排球隊(duì)員；李、趙、陳為足球隊(duì)員李、趙、陳為足球隊(duì)員，問能否從這，問能否從這5 5人中選出人中選出3 3名不兼職的隊(duì)長(zhǎng)？名不兼職的隊(duì)長(zhǎng)？解解: :構(gòu)造二部圖構(gòu)造二部圖G=VG=,E其中其中V V1 1= = 籃籃球隊(duì)球隊(duì), ,排球隊(duì)排球隊(duì), ,足球隊(duì)足球隊(duì) , ,V V2 2= = 張張, ,王王, ,李李, ,趙趙, ,陳陳 圖中的邊分別表示這圖中的邊分別表示這5 5位同學(xué)是相應(yīng)球位同學(xué)是相應(yīng)球隊(duì)的隊(duì)員隊(duì)的隊(duì)員, ,圖中存在圖中存在V V1 1到到V V2 2的匹配的匹配, ,因因此題目要求可以滿足。此題目要求可以滿足。如

11、可選如可選張為籃球隊(duì)長(zhǎng)張為籃球隊(duì)長(zhǎng), ,李為排球隊(duì)長(zhǎng)李為排球隊(duì)長(zhǎng), ,陳為陳為足球足球隊(duì)長(zhǎng)。隊(duì)長(zhǎng)?；@籃排排足足張張王王李李 趙趙 陳陳V V1 1V V2 22022-4-21離散數(shù)學(xué)13例例6.3 6.3 今有今有3 3人甲、乙、丙和人甲、乙、丙和3 3項(xiàng)工作項(xiàng)工作a,b,c,a,b,c,已知甲能勝任已知甲能勝任3 3項(xiàng)工項(xiàng)工作作a,b,c,a,b,c,乙能勝任乙能勝任2 2項(xiàng)工作項(xiàng)工作a,b,a,b,丙能勝任丙能勝任2 2項(xiàng)工作項(xiàng)工作b,cb,c。能否給出能否給出2 2種不同的方案，使每個(gè)人各去完成一項(xiàng)他能勝任的工作？種不同的方案，使每個(gè)人各去完成一項(xiàng)他能勝任的工作？解解: :構(gòu)造二部圖構(gòu)

12、造二部圖G=VG=,E其中其中V V1 1= = 甲甲, ,乙乙, ,丙丙 , , V V2 2= = a,b,ca,b,c 若若V V1 1中某人能勝任中某人能勝任V V2 2中某項(xiàng)工作，則用邊中某項(xiàng)工作，則用邊連接這兩個(gè)結(jié)點(diǎn)，連接這兩個(gè)結(jié)點(diǎn)，得到右圖。顯然得到右圖。顯然 ( (甲甲, ,a),a),( (乙乙, ,b),(b),(丙丙, ,c)c) 和和 ( (甲甲, ,c),c),( (乙乙, ,a),(a),(丙丙, ,b)b) 是符是符合題目要求的合題目要求的 2 2 種不同的方案種不同的方案請(qǐng)同學(xué)們考慮請(qǐng)同學(xué)們考慮: :還有第還有第3 3種方案嗎？種方案嗎？甲甲 乙乙 丙丙a b

13、ca b cV V1 1V V2 22022-4-21離散數(shù)學(xué)14幾個(gè)問題幾個(gè)問題1 “1 “一筆畫一筆畫”問題問題2 “2 “街道清掃車街道清掃車”設(shè)某封閉式小區(qū)的路網(wǎng)結(jié)構(gòu)如圖設(shè)某封閉式小區(qū)的路網(wǎng)結(jié)構(gòu)如圖所示，請(qǐng)證明能否設(shè)計(jì)出一條路所示，請(qǐng)證明能否設(shè)計(jì)出一條路線使得清潔車從小區(qū)大門出發(fā)清線使得清潔車從小區(qū)大門出發(fā)清掃每條道路恰好一次，且在清掃掃每條道路恰好一次，且在清掃完最后一條道路后正好返回小區(qū)完最后一條道路后正好返回小區(qū)大門處。大門處。 3 3 七橋問題七橋問題小區(qū)大門ABCD6.2 6.2 歐拉圖歐拉圖2022-4-21離散數(shù)學(xué)15ABCD在以下在以下4個(gè)圖中個(gè)圖中, 不能一筆畫出圖不

14、能一筆畫出圖, , 而能一筆而能一筆畫出圖畫出圖, 且在中筆又能回到出發(fā)點(diǎn)。且在中筆又能回到出發(fā)點(diǎn)。在中存在關(guān)聯(lián)所有頂點(diǎn)的在中存在關(guān)聯(lián)所有頂點(diǎn)的簡(jiǎn)單通路簡(jiǎn)單通路, 在中存在關(guān)聯(lián)所有頂點(diǎn)的在中存在關(guān)聯(lián)所有頂點(diǎn)的簡(jiǎn)單回路簡(jiǎn)單回路2022-4-21離散數(shù)學(xué)16定義定義6.46.4 通過圖通過圖( (無向圖或有向圖無向圖或有向圖) )中所有邊一次且中所有邊一次且僅一次行遍所有頂點(diǎn)的通路稱為僅一次行遍所有頂點(diǎn)的通路稱為歐拉通路歐拉通路。 通過圖中所有邊一次且僅一次行遍所有頂通過圖中所有邊一次且僅一次行遍所有頂點(diǎn)的回路稱為點(diǎn)的回路稱為歐拉回路歐拉回路。 具有歐拉回路的圖稱為具有歐拉回路的圖稱為歐拉圖歐拉圖

15、。 具有歐拉通路而無歐拉回路的圖稱為具有歐拉通路而無歐拉回路的圖稱為半歐半歐拉圖。拉圖。規(guī)定：平凡圖是歐拉圖。規(guī)定：平凡圖是歐拉圖。2022-4-21離散數(shù)學(xué)17ABCDEe1e2e3e4例例6.46.4 左下圖既是左下圖既是歐拉回路歐拉回路，也是，也是歐拉圖歐拉圖 而右下圖則是而右下圖則是歐拉通路歐拉通路2022-4-21離散數(shù)學(xué)18推論推論 無向圖無向圖G G是是歐拉圖歐拉圖 G G是連通圖，且是連通圖，且G G中中沒有奇度頂點(diǎn)沒有奇度頂點(diǎn)。 無向圖無向圖G G是是半歐拉圖半歐拉圖 G G是連通圖，且是連通圖，且G G中中恰有兩個(gè)奇度頂點(diǎn)恰有兩個(gè)奇度頂點(diǎn)。定理定理6.46.4無向圖無向圖G

16、 G具有歐拉通路具有歐拉通路 G G是連通圖，且是連通圖，且G G中中有有零個(gè)或兩個(gè)奇度頂點(diǎn)零個(gè)或兩個(gè)奇度頂點(diǎn)。 若無奇度頂點(diǎn)，則通路為歐拉回路；若無奇度頂點(diǎn)，則通路為歐拉回路；若有若有兩個(gè)奇度頂點(diǎn)，則它們是每條歐拉通路的端點(diǎn)。兩個(gè)奇度頂點(diǎn)，則它們是每條歐拉通路的端點(diǎn)。 2022-4-21離散數(shù)學(xué)19例例 6.5 考察下圖是否為歐拉圖考察下圖是否為歐拉圖 或存在歐拉通路或存在歐拉通路？ 存在兩個(gè)奇度頂點(diǎn)存在兩個(gè)奇度頂點(diǎn) 根據(jù)定理根據(jù)定理6.4推論知推論知 不是歐拉圖不是歐拉圖. 存在一條歐拉通路存在一條歐拉通路2022-4-21離散數(shù)學(xué)20v4 v5 E G 4Av2 v3 B C v1 D（

17、a） (b) 圖61例例 6.6 求下列圖是否為歐拉圖或存在歐拉通路？求下列圖是否為歐拉圖或存在歐拉通路？v1v2v3v4v5EBFADC(1)(2)解解: 在圖在圖(1)中中, d(v1)= d(v2) =d(v3)3有兩個(gè)以上的結(jié)有兩個(gè)以上的結(jié)點(diǎn)的度為點(diǎn)的度為3. 根據(jù)定理根據(jù)定理6.4知知: 圖圖(1)中不存在歐拉通路，中不存在歐拉通路，當(dāng)然不存在歐拉回路當(dāng)然不存在歐拉回路, 所以不是歐拉圖所以不是歐拉圖. 不能一筆畫出不能一筆畫出. 在圖在圖(2)中中, d(A)=2, d(B) =d(C)= d(D)=4 d(E) =d(G)=3只有兩個(gè)奇數(shù)度的結(jié)點(diǎn)只有兩個(gè)奇數(shù)度的結(jié)點(diǎn), 有歐拉通路

18、有歐拉通路,根據(jù)定理根據(jù)定理6.4推論推論知知不是歐拉圖不是歐拉圖. 存在一條歐拉通路存在一條歐拉通路, 如如EDBEFCABCDF2022-4-21離散數(shù)學(xué)21定理定理 6.5 6.5有向圖有向圖D D具有歐拉通路具有歐拉通路 D D 是連通的是連通的, ,且除了且除了兩個(gè)頂點(diǎn)外兩個(gè)頂點(diǎn)外, ,其余頂點(diǎn)的入度均等于出度。在其余頂點(diǎn)的入度均等于出度。在這兩個(gè)特殊的頂點(diǎn)中這兩個(gè)特殊的頂點(diǎn)中, ,一個(gè)頂點(diǎn)的入度比出度一個(gè)頂點(diǎn)的入度比出度大大1,1,另一個(gè)頂點(diǎn)的入度比出度小另一個(gè)頂點(diǎn)的入度比出度小1 1。推論推論一個(gè)一個(gè)有向圖有向圖D D是歐拉圖是歐拉圖 D D是連通的，是連通的，且所有且所有頂點(diǎn)的

19、入度等于出度頂點(diǎn)的入度等于出度。特別提醒：特別提醒：歐拉回路要求邊不能重復(fù)，結(jié)點(diǎn)可歐拉回路要求邊不能重復(fù)，結(jié)點(diǎn)可以重復(fù)以重復(fù). . 筆不離開紙，不重復(fù)地走完所有的邊，筆不離開紙，不重復(fù)地走完所有的邊，回到原處回到原處. . 就是所謂的一筆畫就是所謂的一筆畫. . 2022-4-21離散數(shù)學(xué)22v0v1v2e10e12e21e00e01e20e22e12e01例例6.76.7 考察考察下圖是下圖是歐拉通路或歐拉回路嗎？歐拉通路或歐拉回路嗎？三個(gè)頂點(diǎn)的度出度與入度相同三個(gè)頂點(diǎn)的度出度與入度相同 是是歐拉回路歐拉回路！ 沿著邊沿著邊 e00, e01, e12, e22, e21, e10, e01

20、, e12, e20 回到出發(fā)點(diǎn)回到出發(fā)點(diǎn)2022-4-21離散數(shù)學(xué)231 12 23 34 4e1e2e3e4e5e1e2e3e4e5e1e2e3e4e5e6e3e1e2e4e2e1e3e4e5e2e1e3e45 56 6例例 6.6 6.6：判斷各圖是否存在：判斷各圖是否存在歐拉通路歐拉通路或或歐拉回路歐拉回路2022-4-21離散數(shù)學(xué)24v1v2v3v4e1e2e3e4e4e5e6e7例例 6 6.9 判定下圖中，是否有歐拉回路？若判定下圖中，是否有歐拉回路？若有請(qǐng)把歐拉回路寫出來有請(qǐng)把歐拉回路寫出來. 在圖中，在圖中，D是連通的，是連通的，且所有頂點(diǎn)的出度等于且所有頂點(diǎn)的出度等于入度。

21、入度。根據(jù)定理根據(jù)定理6.5推論推論知：知：D是是歐拉圖，歐拉圖，所以所以存在歐拉回路，存在歐拉回路，一個(gè)歐拉回路為一個(gè)歐拉回路為v1 e1 v2 e2 v3 e5 v1 e4 v3 e3 v4 e6 v2 e7 v4 e4v12022-4-21離散數(shù)學(xué)25幾個(gè)問題幾個(gè)問題 在一個(gè)大城市，有很多取款機(jī)，那么，如何制定出一個(gè)在一個(gè)大城市，有很多取款機(jī)，那么，如何制定出一個(gè)最優(yōu)的路線，使運(yùn)鈔車過每個(gè)提款機(jī)一次就能運(yùn)送完錢最優(yōu)的路線，使運(yùn)鈔車過每個(gè)提款機(jī)一次就能運(yùn)送完錢鈔？鈔？ 貨郎擔(dān)問題貨郎擔(dān)問題旅行商人問題旅行商人問題 (Traveling Salesman Problem ,TSP) 優(yōu)化算法

22、優(yōu)化算法近似解近似解演化算法演化算法6.3 6.3 哈密頓圖哈密頓圖2022-4-21離散數(shù)學(xué)26幾個(gè)問題幾個(gè)問題1. 在一個(gè)大城市，有很多取款機(jī)，那么，如何制定出一個(gè)在一個(gè)大城市，有很多取款機(jī)，那么，如何制定出一個(gè)最優(yōu)的路線，使運(yùn)鈔車過每個(gè)提款機(jī)一次就能運(yùn)送完錢最優(yōu)的路線，使運(yùn)鈔車過每個(gè)提款機(jī)一次就能運(yùn)送完錢鈔？鈔？ 貨郎擔(dān)問題貨郎擔(dān)問題旅行商人問題旅行商人問題(TSP)2. 考慮在七天內(nèi)安排七門課程的考試，要求同一位教師所考慮在七天內(nèi)安排七門課程的考試，要求同一位教師所任教的兩門課程考試不安排在接連的兩天里，如果教師任教的兩門課程考試不安排在接連的兩天里，如果教師所擔(dān)任的課程都不多于四門，

23、則是否存在滿足上述要求所擔(dān)任的課程都不多于四門，則是否存在滿足上述要求的考試安排方案？的考試安排方案？ 時(shí)間表問題時(shí)間表問題3. 國(guó)際象棋的跳馬是否可以遍歷其棋盤，即從任一格出發(fā)國(guó)際象棋的跳馬是否可以遍歷其棋盤，即從任一格出發(fā)跳到每一格僅一次并最后回到出發(fā)的棋盤格子？跳到每一格僅一次并最后回到出發(fā)的棋盤格子？4. 在一個(gè)至少有在一個(gè)至少有5人出席的圓桌會(huì)議上（會(huì)議需要舉行多人出席的圓桌會(huì)議上（會(huì)議需要舉行多次），為達(dá)到充分交流的目的，會(huì)議主持者希望每次會(huì)次），為達(dá)到充分交流的目的，會(huì)議主持者希望每次會(huì)議每人兩側(cè)的人均與前次不同，這是否可行？請(qǐng)應(yīng)用圖議每人兩側(cè)的人均與前次不同，這是否可行？請(qǐng)應(yīng)用

24、圖論知識(shí)進(jìn)行論證。論知識(shí)進(jìn)行論證。 2022-4-21離散數(shù)學(xué)27哈密爾頓圖哈密爾頓圖l問題問題 1859年愛爾蘭數(shù)學(xué)家威廉年愛爾蘭數(shù)學(xué)家威廉哈密爾頓（哈密爾頓（Sir William Hamilton）發(fā)明了一個(gè)小游戲玩具：一）發(fā)明了一個(gè)小游戲玩具：一個(gè)木刻的正十二面體，每面系正五角形，三面交個(gè)木刻的正十二面體，每面系正五角形，三面交于一角，共有于一角，共有20個(gè)角，每角標(biāo)有世界上一個(gè)重要個(gè)角，每角標(biāo)有世界上一個(gè)重要城市。哈密爾頓提出一個(gè)問題：要求沿正十二面城市。哈密爾頓提出一個(gè)問題：要求沿正十二面體的邊尋找一條路通過體的邊尋找一條路通過20個(gè)城市，而每個(gè)城市只個(gè)城市，而每個(gè)城市只通過一次，

25、最后返回原地。哈密爾頓將此問題稱通過一次，最后返回原地。哈密爾頓將此問題稱為周游世界問題。為周游世界問題。游戲) l求解求解 抽象為圖論問題抽象為圖論問題 哈密爾頓給出了肯定回答，該問題的解是存哈密爾頓給出了肯定回答，該問題的解是存在的在的哈密爾頓回路哈密爾頓回路( (圈圈) )哈密爾頓圖哈密爾頓圖運(yùn)籌學(xué)、計(jì)算機(jī)科學(xué)和編碼理論中的很多問題都可以化為哈密爾頓圖問題運(yùn)籌學(xué)、計(jì)算機(jī)科學(xué)和編碼理論中的很多問題都可以化為哈密爾頓圖問題 William Rowan Hamilton(1805-1865)2022-4-21離散數(shù)學(xué)28定義定義 6.5 6.5 經(jīng)過圖（有向圖或無向圖）中所有頂經(jīng)過圖（有向圖或

26、無向圖）中所有頂點(diǎn)一次且僅一次的通路稱為點(diǎn)一次且僅一次的通路稱為哈密頓通路哈密頓通路。 經(jīng)過圖中所有頂點(diǎn)一次且僅一次的回經(jīng)過圖中所有頂點(diǎn)一次且僅一次的回路稱為路稱為哈密頓回路。哈密頓回路。 具有哈密頓回路的圖稱為具有哈密頓回路的圖稱為哈密頓圖哈密頓圖. . 具有具有哈密頓通路哈密頓通路但不具有哈密頓回路但不具有哈密頓回路的圖稱為的圖稱為半哈密頓圖半哈密頓圖. .注注: :平凡圖是哈密頓圖平凡圖是哈密頓圖。6.3 6.3 哈密頓圖哈密頓圖2022-4-21離散數(shù)學(xué)29例例6.10 指出下列各圖是否哈密頓圖指出下列各圖是否哈密頓圖,有無哈密頓有無哈密頓 通路通路, 回路？回路？解解 (1) 容易判

27、斷容易判斷, 存在哈密頓回路存在哈密頓回路, 故是哈密頓圖故是哈密頓圖. (2) 只有哈密頓通路只有哈密頓通路, 無哈密頓回路無哈密頓回路, 故不是哈故不是哈 密頓圖密頓圖. (3) 無哈密頓通路，顯然不是哈密頓圖無哈密頓通路，顯然不是哈密頓圖. (1)(2)(3)2022-4-21離散數(shù)學(xué)30例例 6.11 6.11：判斷各圖是否是哈密頓圖。判斷各圖是否是哈密頓圖。1 12 23 34 4e1e2e3e4e5e1e2e3e4e5e1e2e3e4e5e6e3e1e2e4e2e1e3e4e5e2e1e3e45 56 62022-4-21離散數(shù)學(xué)31例例 6.12畫出具有下列條件的有畫出具有下列條

28、件的有5個(gè)結(jié)點(diǎn)的無向圖個(gè)結(jié)點(diǎn)的無向圖 (1) 不是哈密頓圖，也不是歐拉圖；不是哈密頓圖，也不是歐拉圖； (2) 有哈密頓回路，沒有歐拉回路；有哈密頓回路，沒有歐拉回路； (3) 沒有哈密頓回路，有歐拉回路；沒有哈密頓回路，有歐拉回路； (4) 是哈密頓圖，也是歐拉圖是哈密頓圖，也是歐拉圖. 解解 作圖如圖作圖如圖(4)(不唯一不唯一).(1)(2)(3)(4)2022-4-21離散數(shù)學(xué)32例例 6.12畫出具有下列條件的有畫出具有下列條件的有5個(gè)結(jié)點(diǎn)的無向圖個(gè)結(jié)點(diǎn)的無向圖 (1) 不是哈密頓圖，也不是歐拉圖；不是哈密頓圖，也不是歐拉圖； (2) 有哈密頓回路，沒有歐拉回路；有哈密頓回路，沒有歐

29、拉回路； (3) 沒有哈密頓回路，有歐拉回路；沒有哈密頓回路，有歐拉回路； (4) 是哈密頓圖，也是歐拉圖是哈密頓圖，也是歐拉圖. 解解 作圖如圖作圖如圖(4)(不唯一不唯一).(1)(2)(3)(4)2022-4-21離散數(shù)學(xué)33定理定理 6.6 6.6 必要條件必要條件 設(shè)無向圖設(shè)無向圖G=G=是哈密頓圖是哈密頓圖, ,對(duì)于任意對(duì)于任意V V1 1 V V且且V V1 1 , , 均有均有 p(G-Vp(G-V1 1) )| V V1 1 |,其中其中p(G-Vp(G-V1 1) )為為G G中刪除中刪除V V1 1( (刪除刪除V V1 1中各頂點(diǎn)及關(guān)聯(lián)的邊中各頂點(diǎn)及關(guān)聯(lián)的邊) )后所得

30、圖后所得圖的連通分支數(shù)。的連通分支數(shù)。證證: : 設(shè)設(shè)C C為為G G中任意一條哈密頓回路。中任意一條哈密頓回路。 若若V V1 1中的頂點(diǎn)在中的頂點(diǎn)在C C上彼此相鄰，則上彼此相鄰，則 p(C- V p(C- V1 1)=1 )=1 | V V1 1 | 設(shè)設(shè)V V1 1中的頂點(diǎn)在中的頂點(diǎn)在C C上存在上存在 r( 2r( 2 r | V V1 1 | ) )個(gè)個(gè) 互不相鄰，則互不相鄰，則 p(C- V p(C- V1 1)=r )=r | V V1 1 | 一般說來一般說來, V V1 1中的中的頂點(diǎn)在頂點(diǎn)在C C上既有相鄰的上既有相鄰的, ,又有不相又有不相鄰的鄰的, ,因而總有因而總有

31、 p(C- V p(C- V1 1) ) | V V1 1 | ，而而C C是是G G的生成子圖的生成子圖, , p(G-Vp(G-V1 1) ) p(C-Vp(C-V1 1) )| V V1 1|2022-4-21離散數(shù)學(xué)34e1e2e3e4e5e6v1v2v3v4V1=v1, v4 或或V1=v2, v3 v5若若V1中的頂點(diǎn)在中的頂點(diǎn)在C上彼此相鄰，則上彼此相鄰，則 P(C- V1)=1 | V1 |2022-4-21離散數(shù)學(xué)35e1e2e3e4e5e6e7V1=v1, v2, v3 或或 V1=v1, v4, v3 v1v2v3v4v5設(shè)設(shè)V1中的頂點(diǎn)在中的頂點(diǎn)在C上存在上存在 r(

32、2 r | V1 | )個(gè)個(gè) 互不相鄰，則互不相鄰，則 P(C- V1)=r | V1 | 2022-4-21離散數(shù)學(xué)36例例 6.13 利用定理利用定理6.6可判斷某些圖不是可判斷某些圖不是哈密頓哈密頓圖圖設(shè)下圖為設(shè)下圖為G G1 1, ,取取 V V1 1=v,則則P(GP(G1 1-V-V1 1)=2 )=2 | V V1 1 |=1 G G1 1-V-V1 1為圖所示為圖所示, ,由由定理定理6.6可知可知G G1 1不是不是哈密頓哈密頓圖圖v2022-4-21離散數(shù)學(xué)37例例 6.13 利用定理利用定理6.6可判斷某些圖不是可判斷某些圖不是哈密頓哈密頓圖圖 設(shè)下圖為設(shè)下圖為G G2

33、2, ,在在G G2 2中取中取 V V2 2 = a, b, c, d, e, f,g , 則則 G G2 2- V- V2 2為圖為圖 所示所示, ,P( GP( G2 2 - V- V2 2)= 9)= 9| V V2 2 |=7 由由定理定理6.6可知可知 G G2 2 不是不是哈密頓哈密頓圖圖abcdefg2022-4-21離散數(shù)學(xué)38定理定理 6.7 6.7 充分條件充分條件 設(shè)設(shè) G G 是是 n (n3)n (n3)階無向簡(jiǎn)單圖，若對(duì)階無向簡(jiǎn)單圖，若對(duì) G G中任意不相鄰的頂點(diǎn)中任意不相鄰的頂點(diǎn) v vi i,v,vj j的度數(shù)之和大于等于的度數(shù)之和大于等于n-n-1 1，即，

34、即 d(vd(vi i)+d(v)+d(vj j)n-1 )n-1 則則G G中存在哈密頓通路中存在哈密頓通路. .推論推論 設(shè)設(shè)G G為為n(n 3)n(n 3)階無向簡(jiǎn)單圖，若對(duì)于階無向簡(jiǎn)單圖，若對(duì)于G G中任中任意兩個(gè)不相鄰的頂點(diǎn)意兩個(gè)不相鄰的頂點(diǎn)v vi i,v,vj j，均有均有 d(vd(vi i)+d(v)+d(vj j)n )n 則則G G中存在哈密頓回路，從而中存在哈密頓回路，從而G G為哈密頓圖。為哈密頓圖。2022-4-21離散數(shù)學(xué)39e1e2e3e4e5e6d(vi)+d(vj)n-1 存在哈密頓通路存在哈密頓通路d(vi)+d(vj)n 存在哈密頓回路存在哈密頓回路2

35、022-4-21離散數(shù)學(xué)40(2)(3)再如下圖再如下圖G任意兩個(gè)不相鄰的頂點(diǎn)任意兩個(gè)不相鄰的頂點(diǎn)vi,vj vi,vj d(vi)+d(vj)n-1 d(vi)+d(vj)n-1 則則G G中存在哈密頓通路中存在哈密頓通路. .d(vi)+d(vj)n d(vi)+d(vj)n 則則G G中存在哈密頓回路，中存在哈密頓回路，從而從而G G為哈密頓圖。為哈密頓圖。abdc(1)(1)和和(2)2022-4-21離散數(shù)學(xué)41例例 6.14 判斷下圖是否是判斷下圖是否是哈密頓哈密頓圖圖afedcb2022-4-21離散數(shù)學(xué)42定理定理 6.6 6.6 在在 n (n2)n (n2)階有向圖階有向圖

36、 D=D=中，如果所有中，如果所有有向邊均用無向邊代替，所得無向圖中含生成子有向邊均用無向邊代替，所得無向圖中含生成子圖圖K Kn n, ,則有向圖則有向圖 D D 中存在哈密頓通路中存在哈密頓通路. .推論推論 n(n 3)n(n 3)階有向完全圖階有向完全圖G G為哈密頓圖為哈密頓圖。2022-4-21離散數(shù)學(xué)43例例 6.15 已知有關(guān)人員已知有關(guān)人員a, b, c, d, e, f, g 的有關(guān)信息的有關(guān)信息 a：說英語(yǔ)；說英語(yǔ)； b：說英語(yǔ)或西班牙語(yǔ)；說英語(yǔ)或西班牙語(yǔ)； c；說英語(yǔ)，意大利語(yǔ)和俄語(yǔ)；說英語(yǔ)，意大利語(yǔ)和俄語(yǔ)； d：說日語(yǔ)和西班牙語(yǔ)說日語(yǔ)和西班牙語(yǔ) e：說德語(yǔ)和意大利語(yǔ)；

37、說德語(yǔ)和意大利語(yǔ)； f：說法語(yǔ)、日語(yǔ)和俄語(yǔ)；說法語(yǔ)、日語(yǔ)和俄語(yǔ)； g：說法語(yǔ)和德語(yǔ)說法語(yǔ)和德語(yǔ). 試問：上述試問：上述7人中是否任意兩人都能交談？人中是否任意兩人都能交談？ (可借助其余可借助其余5人中組成的譯員鏈幫助人中組成的譯員鏈幫助)2022-4-21離散數(shù)學(xué)44abcdefg解解 設(shè)設(shè)7個(gè)人為個(gè)人為7個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn), 將兩個(gè)懂同一語(yǔ)言的人之將兩個(gè)懂同一語(yǔ)言的人之間連一條邊間連一條邊(即他們能直接交談即他們能直接交談), 這樣就得到一個(gè)這樣就得到一個(gè)簡(jiǎn)單圖簡(jiǎn)單圖G, 問題就轉(zhuǎn)化為問題就轉(zhuǎn)化為G是否連通是否連通. 如圖所示如圖所示, 因因?yàn)闉镚的任意兩個(gè)結(jié)點(diǎn)是連通的的任意兩個(gè)結(jié)點(diǎn)是連通的,

38、所以所以G是連通圖是連通圖. 因因此此, 上述上述7個(gè)人中任意兩個(gè)人能交談個(gè)人中任意兩個(gè)人能交談. a：說說英語(yǔ)英語(yǔ)；b：說說英語(yǔ)英語(yǔ)或或西班牙西班牙語(yǔ)；語(yǔ)；C: 說英語(yǔ)說英語(yǔ),意大利語(yǔ)意大利語(yǔ)和和俄語(yǔ)俄語(yǔ)；d：說說日語(yǔ)日語(yǔ)和和西班牙西班牙語(yǔ)語(yǔ)e：說德語(yǔ)和說德語(yǔ)和意大利語(yǔ)意大利語(yǔ)；f：說說法語(yǔ)法語(yǔ)、日語(yǔ)日語(yǔ)和和俄語(yǔ)俄語(yǔ)；g：說說法語(yǔ)法語(yǔ)和德語(yǔ)和德語(yǔ). 2022-4-21離散數(shù)學(xué)45abcdefg如果題目改為：試問這如果題目改為：試問這7個(gè)人應(yīng)如何安排座位個(gè)人應(yīng)如何安排座位, 才才能使每個(gè)人都能與他身邊的人交談？能使每個(gè)人都能與他身邊的人交談？解：用結(jié)點(diǎn)表示人，用邊表示連接的兩個(gè)人能將解：用結(jié)點(diǎn)

39、表示人，用邊表示連接的兩個(gè)人能將同一種語(yǔ)言，夠造出同一種語(yǔ)言，夠造出哈密頓圖如右上哈密頓圖如右上圖所示。圖所示。a：說英語(yǔ)；說英語(yǔ)；b：說英語(yǔ)或西班牙語(yǔ)；說英語(yǔ)或西班牙語(yǔ)；c；說英語(yǔ)，意大利說英語(yǔ)，意大利 語(yǔ)和俄語(yǔ)；語(yǔ)和俄語(yǔ)；d：說日語(yǔ)和西班牙語(yǔ)說日語(yǔ)和西班牙語(yǔ)e：說德語(yǔ)和意大利語(yǔ)；說德語(yǔ)和意大利語(yǔ)；f：說法語(yǔ)、日語(yǔ)和俄語(yǔ)；說法語(yǔ)、日語(yǔ)和俄語(yǔ)；g：說法語(yǔ)和德語(yǔ)說法語(yǔ)和德語(yǔ). 英英英英西西日日法法德德意意2022-4-21離散數(shù)學(xué)46 對(duì)于對(duì)于平面圖平面圖, 先舉一例先舉一例, 設(shè)有一個(gè)電路它有六設(shè)有一個(gè)電路它有六個(gè)元件，三個(gè)分成一組，一個(gè)元件組的每個(gè)元個(gè)元件，三個(gè)分成一組，一個(gè)元件組的每個(gè)元件

40、都用導(dǎo)線與另一組的每個(gè)元件相接，是否有件都用導(dǎo)線與另一組的每個(gè)元件相接，是否有這樣的接法使得導(dǎo)線互不交叉？這個(gè)問題可用這樣的接法使得導(dǎo)線互不交叉？這個(gè)問題可用左下圖表示左下圖表示, 它的最少交叉點(diǎn)是一個(gè)，用右下圖它的最少交叉點(diǎn)是一個(gè)，用右下圖表示表示6.4.平面圖平面圖2022-4-21離散數(shù)學(xué)47定義定義 6. 6 一個(gè)圖一個(gè)圖G能畫在平面上，除頂點(diǎn)之外，再?zèng)]能畫在平面上，除頂點(diǎn)之外，再?zèng)]有邊與邊相交有邊與邊相交. 則稱則稱G為為平面圖平面圖。 畫出的沒有邊交叉的圖稱為畫出的沒有邊交叉的圖稱為G的一個(gè)的一個(gè)平面嵌平面嵌入入或或G的的一個(gè)平面一個(gè)平面.在下圖中在下圖中(2)是是(1) (K4)

41、的平面嵌入的平面嵌入, 所以所以(1)是平面是平面圖圖, 單獨(dú)看單獨(dú)看(2)也是平面圖也是平面圖, 對(duì)于對(duì)于(3) (K5)無論怎樣無論怎樣畫法畫法,也去不掉交叉邊也去不掉交叉邊, 所以不是平面圖。所以不是平面圖。(1)(2)(3)(4)2022-4-21離散數(shù)學(xué)48 例例 6.16 右下圖是左下圖的平面嵌入右下圖是左下圖的平面嵌入, 所以左下圖所以左下圖是平面圖是平面圖, 單獨(dú)看右下圖也是平面圖。單獨(dú)看右下圖也是平面圖。2022-4-21離散數(shù)學(xué)49定義定義 6. 7 設(shè)設(shè)G是一個(gè)連通的平面圖是一個(gè)連通的平面圖, G的邊將的邊將G所在的所在的平面劃分成若干個(gè)區(qū)域平面劃分成若干個(gè)區(qū)域, 每個(gè)區(qū)

42、域稱為每個(gè)區(qū)域稱為G的一個(gè)的一個(gè)面面。其中面積無限的區(qū)域稱為。其中面積無限的區(qū)域稱為無限面或外部面無限面或外部面, 常記為常記為R0, 面積有限的區(qū)域稱為面積有限的區(qū)域稱為有限面或內(nèi)部面有限面或內(nèi)部面。包圍每個(gè)面的所有邊所構(gòu)成的回路稱為該面的包圍每個(gè)面的所有邊所構(gòu)成的回路稱為該面的邊邊界界, 邊界的長(zhǎng)度稱為該面的邊界的長(zhǎng)度稱為該面的次數(shù)次數(shù), R次數(shù)記為次數(shù)記為deg(R) 對(duì)于非連通的平面圖對(duì)于非連通的平面圖G可以類似地定義它的面、可以類似地定義它的面、邊界及次數(shù)。邊界及次數(shù)。2022-4-21離散數(shù)學(xué)50v1v2v3v4v5v6v1v2v3v4v5v6v7R0R1R2R1R0R2( 1 )

43、( 2 )在下圖中在下圖中, 圖圖(1)所示為連通的平面圖所示為連通的平面圖, 共有共有3個(gè)面?zhèn)€面R0, R1, R2。 R1的邊界為初級(jí)回路的邊界為初級(jí)回路v1 v3 v4 v1 , deg(R1)=3。R2的邊界為初級(jí)回路的邊界為初級(jí)回路v1 v2 v3 v1 , deg(R2)=3。R0無限面無限面, 它的邊界為復(fù)雜回路它的邊界為復(fù)雜回路v1 v4 v5v6 v5 v4 v3 v2 v1 , deg(R0)=6。圖圖(2)所示為非所示為非連通的平面圖，有兩個(gè)連通分支，連通的平面圖，有兩個(gè)連通分支， deg(R1)=3， deg(R2)=4， R0的邊界由兩個(gè)初級(jí)回路的邊界由兩個(gè)初級(jí)回路v

44、1 v2 v3v1 和和v4 v5 v6 v7 v4圍成，圍成， deg(R0)=7 。2022-4-21離散數(shù)學(xué)51v1v2v3v4v5v6v1v2v3v4v5v6v7R0R1R2R1R0R2( 1 )( 2 )定理定理 6.9 在一個(gè)在一個(gè)平面圖平面圖G中中, 所有面的次數(shù)之和邊數(shù)所有面的次數(shù)之和邊數(shù)m的的2倍，即倍，即 deg ( Ri ) = 2m 在如下圖所示：無論是連通的還是非連通的在如下圖所示：無論是連通的還是非連通的平面圖，各面次數(shù)之和均等于邊數(shù)的兩倍。平面圖，各面次數(shù)之和均等于邊數(shù)的兩倍。i=1r其中其中r為面數(shù)為面數(shù)2022-4-21離散數(shù)學(xué)52定義定義 6.6 設(shè)設(shè)G為一

45、個(gè)為一個(gè)平面圖平面圖, 如果在如果在G中任意不相鄰的中任意不相鄰的兩個(gè)頂點(diǎn)之間再加一條邊兩個(gè)頂點(diǎn)之間再加一條邊, 所得圖為非平面圖所得圖為非平面圖, 則則稱稱G為為極大平面圖極大平面圖。例：例： GG2022-4-21離散數(shù)學(xué)53定義定義 6.8 在非平面圖在非平面圖G中任意刪除一條邊，所得圖為中任意刪除一條邊，所得圖為平面圖平面圖, 則稱則稱G為為極小非平面圖極小非平面圖。例：例： GG2022-4-21離散數(shù)學(xué)54歐拉公式：歐拉公式：定理定理 6.10 設(shè)設(shè)G為任意的為任意的連通連通的平面圖的平面圖, 則有則有 n m + r = 2 成立。其中成立。其中, n為為G中的頂點(diǎn)數(shù)中的頂點(diǎn)數(shù),

46、 m為邊數(shù)為邊數(shù), r為面為面數(shù)。數(shù)。 (或或 結(jié)點(diǎn)數(shù)與面數(shù)之和邊數(shù)結(jié)點(diǎn)數(shù)與面數(shù)之和邊數(shù)2)定理中平面圖的連通性條件是重要的。如下所示定理中平面圖的連通性條件是重要的。如下所示的平面圖，的平面圖，n=7, m=7, r=3，歐拉公式不成立歐拉公式不成立則歐拉公式則歐拉公式成立成立2022-4-21離散數(shù)學(xué)55歐拉公式證明:對(duì)邊數(shù)m作數(shù)學(xué)歸納:1. m=0,G為孤立點(diǎn),n=1,r=1,結(jié)論成立2. 設(shè)m=k-1(k=1)時(shí)結(jié)論成立,要證明m=k時(shí)結(jié)論成立.若G為樹,任取一樹葉v并刪除它,則G=G-v,則G連通,G中有n=n-1,m=m-1,r=r因此由歸納假設(shè)可得:n-m+r=2即:(n-1)-

47、(m-1)+r=2也就是:n-m+r=2.連通而不含回路的連通而不含回路的無向圖稱為無向樹無向圖稱為無向樹2022-4-21離散數(shù)學(xué)56其次,若G不是樹,則G中必有初級(jí)回路,設(shè)C為一初級(jí)回路,邊e在C上,令G=G-e因?yàn)閑在C上,所以G仍連通,在G中,n=n,m=m-1,r=r-1,利用歸納假設(shè)可得n-m+r=22022-4-21離散數(shù)學(xué)57我們遇到過的圖并不都是平面圖我們遇到過的圖并不都是平面圖,下圖就是非平下圖就是非平面圖面圖, 這個(gè)圖對(duì)應(yīng)于一個(gè)有名的公用事業(yè)問題。這個(gè)圖對(duì)應(yīng)于一個(gè)有名的公用事業(yè)問題。 設(shè)三座房子設(shè)三座房子 a, b, c以及三個(gè)公用事業(yè)設(shè)備以及三個(gè)公用事業(yè)設(shè)備d, e,

48、f,是否可能使每座房子到三個(gè)公用事業(yè)設(shè)備是否可能使每座房子到三個(gè)公用事業(yè)設(shè)備都有管道連接而互不相交。都有管道連接而互不相交。abcdefcbadef實(shí)踐說明這是做不到的實(shí)踐說明這是做不到的, 如左下圖所示如左下圖所示,該圖是二部圖該圖是二部圖K3,3,它是非平面圖。它是非平面圖。2022-4-21離散數(shù)學(xué)58定理定理 6.11 設(shè)設(shè)G是連通的平面圖，且每個(gè)面的次是連通的平面圖，且每個(gè)面的次 數(shù)至少為數(shù)至少為L(zhǎng) ( L 3），），則則 m ( n 2 ) 其中其中, n為為G中的頂點(diǎn)數(shù)中的頂點(diǎn)數(shù), m為邊數(shù)。為邊數(shù)。 LL-2例：如右所示的平面圖例：如右所示的平面圖 m=8 n=6 L 3R3R

49、1R2R0m ( n 2 )L-2L 8 12 （?。ㄈ=3或或4 )2022-4-21離散數(shù)學(xué)59定理定理 6.12 設(shè)設(shè)G是連通的簡(jiǎn)單的平面圖是連通的簡(jiǎn)單的平面圖, 則則 G中至少存在一個(gè)頂點(diǎn)中至少存在一個(gè)頂點(diǎn)v, 有有d(v) 5 該定理在圖的著色理論中占據(jù)重要地位該定理在圖的著色理論中占據(jù)重要地位 2022-4-21離散數(shù)學(xué)60定義定義 6.9 如果如果兩個(gè)圖兩個(gè)圖G1和和G2同構(gòu)同構(gòu), 或經(jīng)過反復(fù)或經(jīng)過反復(fù)插入或消去插入或消去2度頂點(diǎn)后同構(gòu)度頂點(diǎn)后同構(gòu), 則稱則稱G1與與G2同胚同胚 例例 6.16 圖圖G2是經(jīng)過是經(jīng)過G1消去消去2度頂點(diǎn)度頂點(diǎn)a, e, 插入插入2度度頂點(diǎn)頂點(diǎn)h

50、, i 而得到而得到, 易制知易制知G1與與G2同胚同胚 。abcdefgbgcdfihG1G22022-4-21離散數(shù)學(xué)61例例 6.17 考察下列兩圖是否同胚考察下列兩圖是否同胚 。2022-4-21離散數(shù)學(xué)62定義定義 6.10 圖圖G中相鄰頂點(diǎn)中相鄰頂點(diǎn)u, v 之間的之間的初等收縮初等收縮由下面方法給出：刪除邊由下面方法給出：刪除邊(u, v), 用新的頂點(diǎn)用新的頂點(diǎn) 取取代代u, v, 使使 關(guān)聯(lián)關(guān)聯(lián) u, v關(guān)聯(lián)的一切邊關(guān)聯(lián)的一切邊 ( 除除 (u, v) 外外) 例例 6.16 圖圖G1中頂點(diǎn)中頂點(diǎn)v2 ,v3之間的之間的初等收縮初等收縮結(jié)果由結(jié)果由 圖圖G2給出。給出。G1G

51、2v2v1v3v4v1v4 = v2 2022-4-21離散數(shù)學(xué)63定理定理 6.13 平面圖判定條件平面圖判定條件 圖圖G是平面圖的充分必要條件是是平面圖的充分必要條件是G不含與不含與K3, 3或或K5同胚子圖同胚子圖. 以上定理稱為庫(kù)拉圖斯基定理。以上定理稱為庫(kù)拉圖斯基定理。它還有另一種敘述形式它還有另一種敘述形式定理定理 6.14 平面圖判定條件平面圖判定條件 圖圖G是平面圖當(dāng)且僅當(dāng)它沒有可以收縮到是平面圖當(dāng)且僅當(dāng)它沒有可以收縮到K5的子圖，也沒有收縮到的子圖，也沒有收縮到K3, 3的子圖。的子圖。2022-4-21離散數(shù)學(xué)64例例 6.19 下圖下圖G1與與G2（ K5）同胚同胚 。又可收縮到與。