第八章一些特殊的圖

1、2022-7-31第八章第八章 一些特殊的圖一些特殊的圖內(nèi)容導(dǎo)讀內(nèi)容導(dǎo)讀: 二部圖二部圖 歐拉圖歐拉圖哈密頓圖哈密頓圖平面圖平面圖難點(diǎn)難點(diǎn):各種圖的判別定理各種圖的判別定理2022-7-32 2022-7-33(1)(2) 設(shè)無(wú)向圖設(shè)無(wú)向圖 G = 有兩個(gè)有兩個(gè)V的子集的子集V1,V2, 它們具有滿足：它們具有滿足： V1V2= V V1V2= 圖圖G中的每一邊中的每一邊 e 均具有均具有 e = ( vi , vj ) 其中：其中： vi V1 , vj V2 則稱(chēng)則稱(chēng)G是一個(gè)是一個(gè)二部圖二部圖，2022-7-34定義定義8.1 若一個(gè)圖若一個(gè)圖G的結(jié)點(diǎn)集的結(jié)點(diǎn)集V能劃分為兩個(gè)子能劃分為兩個(gè)

2、子集集V1和和V2，使得使得G的每一條邊的每一條邊vi,vj滿足滿足viV1, vjV2 , 則稱(chēng)則稱(chēng)G是一個(gè)是一個(gè)二部圖二部圖， V1和和V2稱(chēng)為稱(chēng)為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)均有邊相連接接, 則稱(chēng)二部圖為則稱(chēng)二部圖為完全二部圖完全二部圖。若。若|V1|=n, |V2 |=m則記完全二部圖則記完全二部圖G為為Kn, m。(1)(2)K2,3K3,32022-7-35(1)(2)例例 8.1 判斷下列圖是否是二部圖？判斷下列圖是否是二部圖？v1v3v5v2v4v6v1v4v8v5v2v

3、3v6v7v1v2v3v4v5(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)無(wú)法將它們分到兩個(gè)不同的子集其中的頂點(diǎn)無(wú)法將它們分到兩個(gè)不同的子集V1和和 V2,使其邊能滿足二部圖的定義使其邊能滿足二部圖的定義, 所以它不是二部圖。所以它不是二部圖。二部圖是不是一定是連通圖?2022-7-36(4)(5)定理定理8.1 一個(gè)無(wú)向圖一個(gè)無(wú)向圖 G

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

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

6、則稱(chēng)則稱(chēng)E*為為極大匹配極大匹配。邊數(shù)最多的極大匹配稱(chēng)為。邊數(shù)最多的極大匹配稱(chēng)為最大匹配最大匹配，最大匹配中的元素，最大匹配中的元素(邊邊)的個(gè)數(shù)稱(chēng)為的個(gè)數(shù)稱(chēng)為G的的匹配數(shù)匹配數(shù)，記為，記為 1(G), 簡(jiǎn)記為簡(jiǎn)記為 1 。2022-7-39(2)e1e2e3e4e5e6e7在圖在圖(2)中中, e2, e5 , e3 , e6 ,e1 , e7 , e4 都是極大匹都是極大匹配配, 其中其中e1, e7, e4 是最大匹配。是最大匹配。2022-7-310(1)(2)e1e2e3e4e5e6e7e1e2e3e4e5e6e7在圖在圖(1)中中不存在完美匹配。不存在完美匹配。在圖在圖(2)中中,

7、e1, e7, e4 是最大匹配，同時(shí)也是是最大匹配，同時(shí)也是完美匹配。完美匹配。今后常用今后常用M表示匹配，設(shè)表示匹配，設(shè)M為為G中一個(gè)匹配，中一個(gè)匹配，v V(G), 若存在若存在M中的邊與中的邊與v關(guān)聯(lián)，則稱(chēng)關(guān)聯(lián)，則稱(chēng)v為為M飽和點(diǎn)飽和點(diǎn)，否則，否則v為為M非飽和點(diǎn)非飽和點(diǎn)，若，若G中每個(gè)頂點(diǎn)中每個(gè)頂點(diǎn)都是飽和點(diǎn)，則稱(chēng)都是飽和點(diǎn)，則稱(chēng)M為為G中中完美匹配完美匹配。2022-7-311定義定義8.3 設(shè)設(shè) G = 為二部圖為二部圖, M為為G中一個(gè)最大中一個(gè)最大匹配匹配, 若若 |M| = min |V1|, |V2| , 則稱(chēng)則稱(chēng)M為為G中的一中的一個(gè)個(gè)完備匹配完備匹配, 此時(shí)若此時(shí)若|

8、V1| |V2|, 則稱(chēng)則稱(chēng)M為為V1到到 V2的的一個(gè)完備匹配。如果一個(gè)完備匹配。如果|V1|= |V2| ,這時(shí)這時(shí)M為為G中的完中的完美匹配。美匹配。G1G2G3在上圖中在上圖中, e1, e2 為為G1中的最大匹配中的最大匹配, G1中不存在完備中不存在完備匹配匹配, 更無(wú)完美匹配。更無(wú)完美匹配。 G2中中e1, e2 , e3為完備匹配為完備匹配, 但但G2中無(wú)完美匹配。中無(wú)完美匹配。 G3中中e1,e2, e3為完備匹配為完備匹配, 同時(shí)也是完同時(shí)也是完美匹配。美匹配。e1e2e1e2e3e1e2e32022-7-312例例8.2 8.2 我們班級(jí)成立了我們班級(jí)成立了 3 3 個(gè)運(yùn)

9、動(dòng)隊(duì)個(gè)運(yùn)動(dòng)隊(duì): :籃球隊(duì)、排球隊(duì)和足球隊(duì)?；@球隊(duì)、排球隊(duì)和足球隊(duì)。今有今有張、王、李、趙、陳張、王、李、趙、陳5 5位同學(xué)位同學(xué)，若已知，若已知張、王為籃球隊(duì)員張、王為籃球隊(duì)員；張、李、趙為排球隊(duì)員張、李、趙為排球隊(duì)員；李、趙、陳為足球隊(duì)員李、趙、陳為足球隊(duì)員，問(wèn)能否從這，問(wèn)能否從這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é)

10、是相應(yīng)球隊(duì)的隊(duì)員隊(duì)的隊(duì)員, ,圖中存在圖中存在V V1 1到到V V2 2的匹配的匹配, ,因因此題目要求可以滿足。此題目要求可以滿足。如可選如可選張為籃球隊(duì)長(zhǎng)張為籃球隊(duì)長(zhǎng), ,李為排球隊(duì)長(zhǎng)李為排球隊(duì)長(zhǎng), ,陳為陳為足球足球隊(duì)長(zhǎng)。隊(duì)長(zhǎng)?；@籃排排足足張張王王李李 趙趙 陳陳V V1 1V V2 22022-7-313籃籃排排足足張張王王李李 趙趙 陳陳V V1 1V V2 2籃籃排排足足張張王王李李 趙趙 陳陳V V1 1V V2 2籃籃排排足足張張王王李李 趙趙 陳陳V V1 1V V2 2籃籃排排足足張張王王李李 趙趙 陳陳V V1 1V V2 2剩下的匹配同學(xué)們自己找剩下的匹配同學(xué)們自己找

11、2022-7-314幾個(gè)問(wèn)題幾個(gè)問(wèn)題1 “1 “一筆畫(huà)一筆畫(huà)”問(wèn)題問(wèn)題2 “2 “街道清掃車(chē)街道清掃車(chē)”設(shè)某封閉式小區(qū)的路網(wǎng)結(jié)構(gòu)如圖設(shè)某封閉式小區(qū)的路網(wǎng)結(jié)構(gòu)如圖所示，請(qǐng)證明能否設(shè)計(jì)出一條路所示，請(qǐng)證明能否設(shè)計(jì)出一條路線使得清潔車(chē)從小區(qū)大門(mén)出發(fā)清線使得清潔車(chē)從小區(qū)大門(mén)出發(fā)清掃每條道路恰好一次，且在清掃掃每條道路恰好一次，且在清掃完最后一條道路后正好返回小區(qū)完最后一條道路后正好返回小區(qū)大門(mén)處。大門(mén)處。 3 3 七橋問(wèn)題七橋問(wèn)題小區(qū)大門(mén)ABCD8.2 8.2 歐拉圖歐拉圖2022-7-315ABCD在以下在以下4個(gè)圖中個(gè)圖中, 不能一筆畫(huà)出圖不能一筆畫(huà)出圖, , 而能一筆而能一筆畫(huà)出圖畫(huà)出圖, 且在

12、中筆又能回到出發(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-7-316定義定義8.48.4 通過(guò)圖通過(guò)圖( (無(wú)向圖或有向圖無(wú)向圖或有向圖) )中所有邊一次且中所有邊一次且僅一次行遍所有頂點(diǎn)的通路稱(chēng)為僅一次行遍所有頂點(diǎn)的通路稱(chēng)為歐拉通路歐拉通路。 通過(guò)圖中所有邊一次且僅一次行遍所有頂通過(guò)圖中所有邊一次且僅一次行遍所有頂點(diǎn)的回路稱(chēng)為點(diǎn)的回路稱(chēng)為歐拉回路歐拉回路。 具有歐拉回路的圖稱(chēng)為具有歐拉回路的圖稱(chēng)為歐拉圖歐拉圖。 具有歐拉通路而無(wú)歐拉回路的圖稱(chēng)為具有歐拉通路而無(wú)歐拉回路的圖稱(chēng)

13、為半歐半歐拉圖。拉圖。規(guī)定：平凡圖是歐拉圖。規(guī)定：平凡圖是歐拉圖。2022-7-317ABCDEe1e2e3e4例例8.48.4 左下圖既是左下圖既是歐拉回路歐拉回路，也是，也是歐拉圖歐拉圖 而右下圖則是而右下圖則是歐拉通路歐拉通路2022-7-318推論推論 無(wú)向圖無(wú)向圖G G是是歐拉圖歐拉圖 G G是連通圖，且是連通圖，且G G中中沒(méi)有奇度頂點(diǎn)沒(méi)有奇度頂點(diǎn)。 無(wú)向圖無(wú)向圖G G是是半歐拉圖半歐拉圖 G G是連通圖，且是連通圖，且G G中中恰有兩個(gè)奇度頂點(diǎn)恰有兩個(gè)奇度頂點(diǎn)。定理定理8.48.4無(wú)向圖無(wú)向圖G G具有歐拉通路具有歐拉通路 G G是連通圖，且是連通圖，且G G中中有有零個(gè)或兩個(gè)奇

14、度頂點(diǎn)零個(gè)或兩個(gè)奇度頂點(diǎn)。 若無(wú)奇度頂點(diǎn)，則通路為歐拉回路；若無(wú)奇度頂點(diǎn)，則通路為歐拉回路；若有若有兩個(gè)奇度頂點(diǎn)，則它們是每條歐拉通路的端點(diǎn)。兩個(gè)奇度頂點(diǎn)，則它們是每條歐拉通路的端點(diǎn)。 2022-7-319例例 8.5 考察下圖是否為歐拉圖考察下圖是否為歐拉圖 或存在歐拉通路或存在歐拉通路？ 存在兩個(gè)奇度頂點(diǎn)存在兩個(gè)奇度頂點(diǎn) 根據(jù)定理根據(jù)定理8.4推論知推論知 不是歐拉圖不是歐拉圖. 存在一條歐拉通路存在一條歐拉通路2022-7-320定理定理 8.5 8.5有向圖有向圖D D具有歐拉通路具有歐拉通路 D D 是連通的是連通的, ,且除了且除了兩個(gè)頂點(diǎn)外兩個(gè)頂點(diǎn)外, ,其余頂點(diǎn)的入度均等于出度

15、。在其余頂點(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)的入度等于出度頂點(diǎn)的入度等于出度。特別提醒：特別提醒：歐拉回路要求邊不能重復(fù)，結(jié)點(diǎn)可歐拉回路要求邊不能重復(fù)，結(jié)點(diǎn)可以重復(fù)以重復(fù). . 筆不離開(kāi)紙，不重復(fù)地走完所有的邊，筆不離開(kāi)紙，不重復(fù)地走完所有的邊，回到原處回到原處. . 就是所謂的一筆畫(huà)就是所謂的一筆畫(huà). . 2022-7-321v0v1v2e10e12e21e00e

16、01e20e22e12e01例例8.78.7 考察考察下圖是下圖是歐拉通路或歐拉回路嗎？歐拉通路或歐拉回路嗎？三個(gè)頂點(diǎn)的度出度與入度相同三個(gè)頂點(diǎn)的度出度與入度相同 是是歐拉回路歐拉回路！ 沿著邊沿著邊 e00, e01, e12, e22, e21, e10, e01, e12, e20 回到出發(fā)點(diǎn)回到出發(fā)點(diǎn)2022-7-322幾個(gè)問(wèn)題幾個(gè)問(wèn)題 在一個(gè)大城市，有很多取款機(jī)，那么，如何制定出一個(gè)在一個(gè)大城市，有很多取款機(jī)，那么，如何制定出一個(gè)最優(yōu)的路線，使運(yùn)鈔車(chē)過(guò)每個(gè)提款機(jī)一次就能運(yùn)送完錢(qián)最優(yōu)的路線，使運(yùn)鈔車(chē)過(guò)每個(gè)提款機(jī)一次就能運(yùn)送完錢(qián)鈔？鈔？ 貨郎擔(dān)問(wèn)題貨郎擔(dān)問(wèn)題旅行商人問(wèn)題旅行商人問(wèn)題 (T

17、raveling Salesman Problem ,TSP) 優(yōu)化算法優(yōu)化算法近似解近似解演化算法演化算法8.3 8.3 哈密頓圖哈密頓圖2022-7-323幾個(gè)問(wèn)題幾個(gè)問(wèn)題1. 在一個(gè)大城市，有很多取款機(jī)，那么，如何制定出一個(gè)在一個(gè)大城市，有很多取款機(jī)，那么，如何制定出一個(gè)最優(yōu)的路線，使運(yùn)鈔車(chē)過(guò)每個(gè)提款機(jī)一次就能運(yùn)送完錢(qián)最優(yōu)的路線，使運(yùn)鈔車(chē)過(guò)每個(gè)提款機(jī)一次就能運(yùn)送完錢(qián)鈔？鈔？ 貨郎擔(dān)問(wèn)題貨郎擔(dān)問(wèn)題旅行商人問(wèn)題旅行商人問(wèn)題(TSP)2. 考慮在七天內(nèi)安排七門(mén)課程的考試，要求同一位教師所考慮在七天內(nèi)安排七門(mén)課程的考試，要求同一位教師所任教的兩門(mén)課程考試不安排在接連的兩天里，如果教師任教的兩門(mén)課

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

19、否可行？請(qǐng)應(yīng)用圖議每人兩側(cè)的人均與前次不同，這是否可行？請(qǐng)應(yīng)用圖論知識(shí)進(jìn)行論證。論知識(shí)進(jìn)行論證。 2022-7-324哈密爾頓圖哈密爾頓圖l問(wèn)題問(wèn)題 1859年愛(ài)爾蘭數(shù)學(xué)家威廉年愛(ài)爾蘭數(shù)學(xué)家威廉哈密爾頓（哈密爾頓（Sir William Hamilton）發(fā)明了一個(gè)小游戲玩具：一）發(fā)明了一個(gè)小游戲玩具：一個(gè)木刻的正十二面體，每面系正五角形，三面交個(gè)木刻的正十二面體，每面系正五角形，三面交于一角，共有于一角，共有20個(gè)角，每角標(biāo)有世界上一個(gè)重要個(gè)角，每角標(biāo)有世界上一個(gè)重要城市。哈密爾頓提出一個(gè)問(wèn)題：要求沿正十二面城市。哈密爾頓提出一個(gè)問(wèn)題：要求沿正十二面體的邊尋找一條路通過(guò)體的邊尋找一條路通過(guò)2

20、0個(gè)城市，而每個(gè)城市只個(gè)城市，而每個(gè)城市只通過(guò)一次，最后返回原地。哈密爾頓將此問(wèn)題稱(chēng)通過(guò)一次，最后返回原地。哈密爾頓將此問(wèn)題稱(chēng)為周游世界問(wèn)題。為周游世界問(wèn)題。游戲) l求解求解 抽象為圖論問(wèn)題抽象為圖論問(wèn)題 哈密爾頓給出了肯定回答，該問(wèn)題的解是存在哈密爾頓給出了肯定回答，該問(wèn)題的解是存在的的哈密爾頓回路哈密爾頓回路( (圈圈) )哈密爾頓圖哈密爾頓圖運(yùn)籌學(xué)、計(jì)算機(jī)科學(xué)和編碼理論中的很多問(wèn)題都可以化為哈密爾頓圖問(wèn)題運(yùn)籌學(xué)、計(jì)算機(jī)科學(xué)和編碼理論中的很多問(wèn)題都可以化為哈密爾頓圖問(wèn)題 William Rowan Hamilton(1805-1865)2022-7-325定義定義 8.5 8.5 經(jīng)過(guò)圖

21、（有向圖或無(wú)向圖）中所有頂經(jīng)過(guò)圖（有向圖或無(wú)向圖）中所有頂點(diǎn)一次且僅一次的通路稱(chēng)為點(diǎn)一次且僅一次的通路稱(chēng)為哈密頓通路哈密頓通路。 經(jīng)過(guò)圖中所有頂點(diǎn)一次且僅一次的回經(jīng)過(guò)圖中所有頂點(diǎn)一次且僅一次的回路稱(chēng)為路稱(chēng)為哈密頓回路。哈密頓回路。 具有哈密頓回路的圖稱(chēng)為具有哈密頓回路的圖稱(chēng)為哈密頓圖哈密頓圖. . 具有具有哈密頓通路哈密頓通路但不具有哈密頓回路但不具有哈密頓回路的圖稱(chēng)為的圖稱(chēng)為半哈密頓圖半哈密頓圖. .注注: :平凡圖是哈密頓圖平凡圖是哈密頓圖。8.3 8.3 哈密頓圖哈密頓圖2022-7-326例例8.10 指出下列各圖是否哈密頓圖指出下列各圖是否哈密頓圖,有無(wú)哈密頓有無(wú)哈密頓 通路通路,

22、回路？回路？解解 (1) 容易判斷容易判斷, 存在哈密頓回路存在哈密頓回路, 故是哈密頓圖故是哈密頓圖. (2) 只有哈密頓通路只有哈密頓通路, 無(wú)哈密頓回路無(wú)哈密頓回路, 故不是哈故不是哈 密頓圖密頓圖. (3) 無(wú)哈密頓通路，顯然不是哈密頓圖無(wú)哈密頓通路，顯然不是哈密頓圖. (1)(2)(3)2022-7-327定理定理 8.6 8.6 必要條件必要條件 設(shè)無(wú)向圖設(shè)無(wú)向圖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中刪除中刪除

23、V V1 1( (刪除刪除V V1 1中各頂點(diǎn)及關(guān)聯(lián)的邊中各頂點(diǎn)及關(guān)聯(lián)的邊) )后所得圖后所得圖的連通分支數(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 | 一般說(shuō)來(lái)一般說(shuō)來(lái), V V1 1中的中的頂點(diǎn)在頂

24、點(diǎn)在C C上既有相鄰的上既有相鄰的, ,又有不相又有不相鄰的鄰的, ,因而總有因而總有 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-7-328e1e2e3e4e5e6v1v2v3v4V1=v1, v4 或或V1=v2, v3 v5若若V1中的頂點(diǎn)在中的頂點(diǎn)在C上彼此相鄰，則上彼此相鄰，則 P(C- V1)=1 | V1 |2022-7-329e1e2e3e4e5e6e7V1=v1, v2, v3 或或 V1=v1, v4, v3 v1

25、v2v3v4v5設(shè)設(shè)V1中的頂點(diǎn)在中的頂點(diǎn)在C上存在上存在 r( 2 r | V1 | )個(gè)個(gè) 互不相鄰，則互不相鄰，則 P(C- V1)=r | V1 | 2022-7-330例例 8.13 利用定理利用定理8.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為圖所示為圖所示, ,由由定理定理8.6可知可知G G1 1不是不是哈密頓哈密頓圖圖v2022-7-331定理定理 8.7 8.7 充分條件充分條件 設(shè)設(shè) G G 是是 n

26、(n3)n (n3)階無(wú)向簡(jiǎn)單圖，若對(duì)階無(wú)向簡(jiǎn)單圖，若對(duì) G G中任意不相鄰的頂點(diǎn)中任意不相鄰的頂點(diǎn) v vi i,v,vj j的度數(shù)之和大于等于的度數(shù)之和大于等于n-n-1 1，即，即 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)階無(wú)向簡(jiǎn)單圖，若對(duì)于階無(wú)向簡(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為哈密頓

27、圖。為哈密頓圖。2022-7-332e1e2e3e4e5e6d(vi)+d(vj)n-1 存在哈密頓通路存在哈密頓通路d(vi)+d(vj)n 存在哈密頓回路存在哈密頓回路2022-7-333(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-7-334定理定理 8.8 8

28、.8 在在 n (n2)n (n2)階有向圖階有向圖 D=D=中，如果所有中，如果所有有向邊均用無(wú)向邊代替，所得無(wú)向圖中含生成子有向邊均用無(wú)向邊代替，所得無(wú)向圖中含生成子圖圖K Kn n, ,則有向圖則有向圖 D D 中存在哈密頓通路中存在哈密頓通路. .推論推論 n(n 3)n(n 3)階有向完全圖階有向完全圖G G為哈密頓圖為哈密頓圖。2022-7-335例例 8.15 已知有關(guān)人員已知有關(guān)人員a, b, c, d, e, f, g 的有關(guān)信息的有關(guān)信息 a：說(shuō)英語(yǔ)；說(shuō)英語(yǔ)； b：說(shuō)英語(yǔ)或西班牙語(yǔ)；說(shuō)英語(yǔ)或西班牙語(yǔ)； c；說(shuō)英語(yǔ)，意大利語(yǔ)和俄語(yǔ)；說(shuō)英語(yǔ)，意大利語(yǔ)和俄語(yǔ)； d：說(shuō)日語(yǔ)和西班牙

29、語(yǔ)說(shuō)日語(yǔ)和西班牙語(yǔ) e：說(shuō)德語(yǔ)和意大利語(yǔ)；說(shuō)德語(yǔ)和意大利語(yǔ)； f：說(shuō)法語(yǔ)、日語(yǔ)和俄語(yǔ)；說(shuō)法語(yǔ)、日語(yǔ)和俄語(yǔ)； g：說(shuō)法語(yǔ)和德語(yǔ)說(shuō)法語(yǔ)和德語(yǔ). 試問(wèn)：上述試問(wèn)：上述7人中是否任意兩人都能交談？人中是否任意兩人都能交談？ (可借助其余可借助其余5人中組成的譯員鏈幫助人中組成的譯員鏈幫助)2022-7-336abcdefg解解 設(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, 問(wèn)題就轉(zhuǎn)化為問(wèn)題就轉(zhuǎn)化為G是否連通是否連通. 如圖所示如圖所示, 因因?yàn)闉镚的任意兩個(gè)結(jié)點(diǎn)是

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

31、的兩個(gè)人能將解：用結(jié)點(diǎn)表示人，用邊表示連接的兩個(gè)人能將同一種語(yǔ)言，夠造出同一種語(yǔ)言，夠造出哈密頓圖如右上哈密頓圖如右上圖所示。圖所示。a：說(shuō)英語(yǔ)；說(shuō)英語(yǔ)；b：說(shuō)英語(yǔ)或西班牙語(yǔ)；說(shuō)英語(yǔ)或西班牙語(yǔ)；c；說(shuō)英語(yǔ)，意大利說(shuō)英語(yǔ)，意大利 語(yǔ)和俄語(yǔ)；語(yǔ)和俄語(yǔ)；d：說(shuō)日語(yǔ)和西班牙語(yǔ)說(shuō)日語(yǔ)和西班牙語(yǔ)e：說(shuō)德語(yǔ)和意大利語(yǔ)；說(shuō)德語(yǔ)和意大利語(yǔ)；f：說(shuō)法語(yǔ)、日語(yǔ)和俄語(yǔ)；說(shuō)法語(yǔ)、日語(yǔ)和俄語(yǔ)；g：說(shuō)法語(yǔ)和德語(yǔ)說(shuō)法語(yǔ)和德語(yǔ). 英英英英西西日日法法德德意意2022-7-338 對(duì)于對(duì)于平面圖平面圖, 先舉一例先舉一例, 設(shè)有一個(gè)電路它有六設(shè)有一個(gè)電路它有六個(gè)元件，三個(gè)分成一組，一個(gè)元件組的每個(gè)元個(gè)元件，三個(gè)分成一組，一個(gè)元件

32、組的每個(gè)元件都用導(dǎo)線與另一組的每個(gè)元件相接，是否有件都用導(dǎo)線與另一組的每個(gè)元件相接，是否有這樣的接法使得導(dǎo)線互不交叉？這個(gè)問(wèn)題可用這樣的接法使得導(dǎo)線互不交叉？這個(gè)問(wèn)題可用左下圖表示左下圖表示, 它的最少交叉點(diǎn)是一個(gè)，用右下圖它的最少交叉點(diǎn)是一個(gè)，用右下圖表示表示8.4.平面圖平面圖2022-7-339定義定義 8. 6 一個(gè)圖一個(gè)圖G能畫(huà)在平面上，除頂點(diǎn)之外，再?zèng)]能畫(huà)在平面上，除頂點(diǎn)之外，再?zèng)]有邊與邊相交有邊與邊相交. 則稱(chēng)則稱(chēng)G為為平面圖平面圖。 畫(huà)出的沒(méi)有邊交叉的圖稱(chēng)為畫(huà)出的沒(méi)有邊交叉的圖稱(chēng)為G的一個(gè)的一個(gè)平面嵌平面嵌入入或或G的的一個(gè)平面一個(gè)平面.在下圖中在下圖中(2)是是(1) (K4

33、)的平面嵌入的平面嵌入, 所以所以(1)是平面是平面圖圖, 單獨(dú)看單獨(dú)看(2)也是平面圖也是平面圖, 對(duì)于對(duì)于(3) (K5)無(wú)論怎樣無(wú)論怎樣畫(huà)法畫(huà)法,也去不掉交叉邊也去不掉交叉邊, 所以不是平面圖。所以不是平面圖。(1)(2)(3)(4)2022-7-340 例例 8.16 右下圖是左下圖的平面嵌入右下圖是左下圖的平面嵌入, 所以左下圖所以左下圖是平面圖是平面圖, 單獨(dú)看右下圖也是平面圖。單獨(dú)看右下圖也是平面圖。2022-7-341定義定義 8. 7 設(shè)設(shè)G是一個(gè)連通的平面圖是一個(gè)連通的平面圖, G的邊將的邊將G所在的所在的平面劃分成若干個(gè)區(qū)域平面劃分成若干個(gè)區(qū)域, 每個(gè)區(qū)域稱(chēng)為每個(gè)區(qū)域稱(chēng)為

34、G的一個(gè)的一個(gè)面面。其中面積無(wú)限的區(qū)域稱(chēng)為。其中面積無(wú)限的區(qū)域稱(chēng)為無(wú)限面或外部面無(wú)限面或外部面, 常記為常記為R0, 面積有限的區(qū)域稱(chēng)為面積有限的區(qū)域稱(chēng)為有限面或內(nèi)部面有限面或內(nèi)部面。包圍每個(gè)面的所有邊所構(gòu)成的回路稱(chēng)為該面的包圍每個(gè)面的所有邊所構(gòu)成的回路稱(chēng)為該面的邊邊界界, 邊界的長(zhǎng)度稱(chēng)為該面的邊界的長(zhǎng)度稱(chēng)為該面的次數(shù)次數(shù), R次數(shù)記為次數(shù)記為deg(R) 對(duì)于非連通的平面圖對(duì)于非連通的平面圖G可以類(lèi)似地定義它的面、可以類(lèi)似地定義它的面、邊界及次數(shù)。邊界及次數(shù)。2022-7-342v1v2v3v4v5v6v1v2v3v4v5v6v7R0R1R2R1R0R2( 1 )( 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無(wú)限面無(wú)限面, 它的邊界為復(fù)雜回路它的邊界為復(fù)雜回路v1 v4 v5v6 v5 v4 v3 v2 v1 , deg(R0)=8。圖圖(2)所示為非所