第八章一些特殊的圖

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

2、分為兩個子集集V1和和V2，使得使得G的每一條邊的每一條邊vi,vj滿足滿足viV1, vjV2 , 則稱則稱G是一個是一個二部圖二部圖， V1和和V2稱為稱為G的的互補結(jié)點子集。此時可將互補結(jié)點子集。此時可將G記成記成 G = 若若V1中任一結(jié)點與中任一結(jié)點與V2中每一結(jié)點均有邊相連中每一結(jié)點均有邊相連接接, 則稱二部圖為則稱二部圖為完全二部圖完全二部圖。若。若|V1|=n, |V2 |=m則記完全二部圖則記完全二部圖G為為Kn, m。(1)(2)K2,3K3,32022-2-105(1)(2)例例 8.1 判斷下列圖是否是二部圖？判斷下列圖是否是二部圖？v1v3v5v2v4v6v1v4v8

3、v5v2v3v6v7v1v2v3v4v5(3)在圖在圖 (1) 中中, V1=v1, v3, v5, V2=v2, v4, v6, 是一個完是一個完全二部圖。在圖全二部圖。在圖 (2) 中中, V1=v1, v4, v8, v5, V2=v2, v3, v7, v6, 是一個二部圖。在圖是一個二部圖。在圖 (3) 中中, 對于對于其中的頂點無法將它們分到兩個不同的子集其中的頂點無法將它們分到兩個不同的子集V1和和 V2,使其邊能滿足二部圖的定義使其邊能滿足二部圖的定義, 所以它不是二部圖。所以它不是二部圖。二部圖是不是一定是連通圖?2022-2-106(4)(5)定理定理8.1 一個無向圖一個

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

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

6、都不是匹配了, 則稱則稱E*為為極大匹配極大匹配。邊數(shù)最多的極大匹配稱為。邊數(shù)最多的極大匹配稱為最大匹配最大匹配，最大匹配中的元素，最大匹配中的元素(邊邊)的個數(shù)稱為的個數(shù)稱為G的的匹配數(shù)匹配數(shù)，記為，記為 1(G), 簡記為簡記為 1 。2022-2-109(2)e1e2e3e4e5e6e7在圖在圖(2)中中, e2, e5 , e3 , e6 ,e1 , e7 , e4 都是極大匹都是極大匹配配, 其中其中e1, e7, e4 是最大匹配。是最大匹配。2022-2-1010(1)(2)e1e2e3e4e5e6e7e1e2e3e4e5e6e7在圖在圖(1)中中不存在完美匹配。不存在完美匹配。

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

8、匹配, 此時若此時若|V1| |V2|, 則稱則稱M為為V1到到 V2的的一個完備匹配。如果一個完備匹配。如果|V1|= |V2| ,這時這時M為為G中的完中的完美匹配。美匹配。G1G2G3在上圖中在上圖中, e1, e2 為為G1中的最大匹配中的最大匹配, G1中不存在完備中不存在完備匹配匹配, 更無完美匹配。更無完美匹配。 G2中中e1, e2 , e3為完備匹配為完備匹配, 但但G2中無完美匹配。中無完美匹配。 G3中中e1,e2, e3為完備匹配為完備匹配, 同時也是完同時也是完美匹配。美匹配。e1e2e1e2e3e1e2e32022-2-1012例例8.2 8.2 我們班級成立了我們

9、班級成立了 3 3 個運動隊個運動隊: :籃球隊、排球隊和足球隊。籃球隊、排球隊和足球隊。今有今有張、王、李、趙、陳張、王、李、趙、陳5 5位同學(xué)位同學(xué)，若已知，若已知張、王為籃球隊員張、王為籃球隊員；張、李、趙為排球隊員張、李、趙為排球隊員；李、趙、陳為足球隊員李、趙、陳為足球隊員，問能否從這，問能否從這5 5人中選出人中選出3 3名不兼職的隊長？名不兼職的隊長？解解: :構(gòu)造二部圖構(gòu)造二部圖G=VG=,E其中其中V V1 1= = 籃籃球隊球隊, ,排球隊排球隊, ,足球隊足球隊 , ,V V2 2= = 張張, ,王王, ,李李, ,趙趙, ,陳陳 圖中的邊分別表示這圖中的邊分別表示這5

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

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

12、筆而能一筆畫出圖畫出圖, 且在中筆又能回到出發(fā)點。且在中筆又能回到出發(fā)點。在中存在關(guān)聯(lián)所有頂點的在中存在關(guān)聯(lián)所有頂點的簡單通路簡單通路, 在中存在關(guān)聯(lián)所有頂點的在中存在關(guān)聯(lián)所有頂點的簡單回路簡單回路2022-2-1016定義定義8.48.4 通過圖通過圖( (無向圖或有向圖無向圖或有向圖) )中所有邊一次且中所有邊一次且僅一次行遍所有頂點的通路稱為僅一次行遍所有頂點的通路稱為歐拉通路歐拉通路。 通過圖中所有邊一次且僅一次行遍所有頂通過圖中所有邊一次且僅一次行遍所有頂點的回路稱為點的回路稱為歐拉回路歐拉回路。 具有歐拉回路的圖稱為具有歐拉回路的圖稱為歐拉圖歐拉圖。 具有歐拉通路而無歐拉回路的圖稱

13、為具有歐拉通路而無歐拉回路的圖稱為半歐半歐拉圖。拉圖。規(guī)定：平凡圖是歐拉圖。規(guī)定：平凡圖是歐拉圖。2022-2-1017ABCDEe1e2e3e4例例8.48.4 左下圖既是左下圖既是歐拉回路歐拉回路，也是，也是歐拉圖歐拉圖 而右下圖則是而右下圖則是歐拉通路歐拉通路2022-2-1018推論推論 無向圖無向圖G G是是歐拉圖歐拉圖 G G是連通圖，且是連通圖，且G G中中沒有奇度頂點沒有奇度頂點。 無向圖無向圖G G是是半歐拉圖半歐拉圖 G G是連通圖，且是連通圖，且G G中中恰有兩個奇度頂點恰有兩個奇度頂點。定理定理8.48.4無向圖無向圖G G具有歐拉通路具有歐拉通路 G G是連通圖，且是

14、連通圖，且G G中中有有零個或兩個奇度頂點零個或兩個奇度頂點。 若無奇度頂點，則通路為歐拉回路；若無奇度頂點，則通路為歐拉回路；若有若有兩個奇度頂點，則它們是每條歐拉通路的端點。兩個奇度頂點，則它們是每條歐拉通路的端點。 2022-2-1019例例 8.5 考察下圖是否為歐拉圖考察下圖是否為歐拉圖 或存在歐拉通路或存在歐拉通路？ 存在兩個奇度頂點存在兩個奇度頂點 根據(jù)定理根據(jù)定理8.4推論知推論知 不是歐拉圖不是歐拉圖. 存在一條歐拉通路存在一條歐拉通路2022-2-1020定理定理 8.5 8.5有向圖有向圖D D具有歐拉通路具有歐拉通路 D D 是連通的是連通的, ,且除了且除了兩個頂點外

15、兩個頂點外, ,其余頂點的入度均等于出度。在其余頂點的入度均等于出度。在這兩個特殊的頂點中這兩個特殊的頂點中, ,一個頂點的入度比出度一個頂點的入度比出度大大1,1,另一個頂點的入度比出度小另一個頂點的入度比出度小1 1。推論推論一個一個有向圖有向圖D D是歐拉圖是歐拉圖 D D是連通的，是連通的，且所有且所有頂點的入度等于出度頂點的入度等于出度。特別提醒：特別提醒：歐拉回路要求邊不能重復(fù)，結(jié)點可歐拉回路要求邊不能重復(fù)，結(jié)點可以重復(fù)以重復(fù). . 筆不離開紙，不重復(fù)地走完所有的邊，筆不離開紙，不重復(fù)地走完所有的邊，回到原處回到原處. . 就是所謂的一筆畫就是所謂的一筆畫. . 2022-2-10

16、21v0v1v2e10e12e21e00e01e20e22e12e01例例8.78.7 考察考察下圖是下圖是歐拉通路或歐拉回路嗎？歐拉通路或歐拉回路嗎？三個頂點的度出度與入度相同三個頂點的度出度與入度相同 是是歐拉回路歐拉回路！ 沿著邊沿著邊 e00, e01, e12, e22, e21, e10, e01, e12, e20 回到出發(fā)點回到出發(fā)點2022-2-1022幾個問題幾個問題 在一個大城市，有很多取款機，那么，如何制定出一個在一個大城市，有很多取款機，那么，如何制定出一個最優(yōu)的路線，使運鈔車過每個提款機一次就能運送完錢最優(yōu)的路線，使運鈔車過每個提款機一次就能運送完錢鈔？鈔？ 貨郎擔(dān)

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

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

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

20、十二面體的邊尋找一條路通過體的邊尋找一條路通過20個城市，而每個城市只個城市，而每個城市只通過一次，最后返回原地。哈密爾頓將此問題稱通過一次，最后返回原地。哈密爾頓將此問題稱為周游世界問題。為周游世界問題。游戲) l求解求解 抽象為圖論問題抽象為圖論問題 哈密爾頓給出了肯定回答，該問題的解是存在哈密爾頓給出了肯定回答，該問題的解是存在的的哈密爾頓回路哈密爾頓回路( (圈圈) )哈密爾頓圖哈密爾頓圖運籌學(xué)、計算機科學(xué)和編碼理論中的很多問題都可以化為哈密爾頓圖問題運籌學(xué)、計算機科學(xué)和編碼理論中的很多問題都可以化為哈密爾頓圖問題 William Rowan Hamilton(1805-1865)20

21、22-2-1025定義定義 8.5 8.5 經(jīng)過圖（有向圖或無向圖）中所有頂經(jīng)過圖（有向圖或無向圖）中所有頂點一次且僅一次的通路稱為點一次且僅一次的通路稱為哈密頓通路哈密頓通路。 經(jīng)過圖中所有頂點一次且僅一次的回經(jīng)過圖中所有頂點一次且僅一次的回路稱為路稱為哈密頓回路。哈密頓回路。 具有哈密頓回路的圖稱為具有哈密頓回路的圖稱為哈密頓圖哈密頓圖. . 具有具有哈密頓通路哈密頓通路但不具有哈密頓回路但不具有哈密頓回路的圖稱為的圖稱為半哈密頓圖半哈密頓圖. .注注: :平凡圖是哈密頓圖平凡圖是哈密頓圖。8.3 8.3 哈密頓圖哈密頓圖2022-2-1026例例8.10 指出下列各圖是否哈密頓圖指出下列

22、各圖是否哈密頓圖,有無哈密頓有無哈密頓 通路通路, 回路？回路？解解 (1) 容易判斷容易判斷, 存在哈密頓回路存在哈密頓回路, 故是哈密頓圖故是哈密頓圖. (2) 只有哈密頓通路只有哈密頓通路, 無哈密頓回路無哈密頓回路, 故不是哈故不是哈 密頓圖密頓圖. (3) 無哈密頓通路，顯然不是哈密頓圖無哈密頓通路，顯然不是哈密頓圖. (1)(2)(3)2022-2-1027定理定理 8.6 8.6 必要條件必要條件 設(shè)無向圖設(shè)無向圖G=G=是哈密頓圖是哈密頓圖, ,對于任意對于任意V V1 1 V V且且V V1 1 , , 均有均有 p(G-Vp(G-V1 1) )| V V1 1 |,其中其中

23、p(G-Vp(G-V1 1) )為為G G中刪除中刪除V V1 1( (刪除刪除V V1 1中各頂點及關(guān)聯(lián)的邊中各頂點及關(guān)聯(lián)的邊) )后所得圖后所得圖的連通分支數(shù)。的連通分支數(shù)。證證: : 設(shè)設(shè)C C為為G G中任意一條哈密頓回路。中任意一條哈密頓回路。 若若V V1 1中的頂點在中的頂點在C C上彼此相鄰，則上彼此相鄰，則 p(C- V p(C- V1 1)=1 )=1 | V V1 1 | 設(shè)設(shè)V V1 1中的頂點在中的頂點在C C上存在上存在 r( 2r( 2 r | V V1 1 | ) )個個 互不相鄰，則互不相鄰，則 p(C- V p(C- V1 1)=r )=r | V V1 1

24、 | 一般說來一般說來, V V1 1中的中的頂點在頂點在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-2-1028e1e2e3e4e5e6v1v2v3v4V1=v1, v4 或或V1=v2, v3 v5若若V1中的頂點在中的頂點在C上彼此相鄰，則上彼此相鄰，則 P(C- V1)=1 | V1 |2022-2-1029e1e2e3e4e5e6e7V1=v

25、1, v2, v3 或或 V1=v1, v4, v3 v1v2v3v4v5設(shè)設(shè)V1中的頂點在中的頂點在C上存在上存在 r( 2 r | V1 | )個個 互不相鄰，則互不相鄰，則 P(C- V1)=r | V1 | 2022-2-1030例例 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-2-1031定理定

26、理 8.7 8.7 充分條件充分條件 設(shè)設(shè) G G 是是 n (n3)n (n3)階無向簡單圖，若對階無向簡單圖，若對 G G中任意不相鄰的頂點中任意不相鄰的頂點 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)階無向簡單圖，若對于階無向簡單圖，若對于G G中任中任意兩個不相鄰的頂點意兩個不相鄰的頂點v vi i,v,vj j，均有均有 d(vd(vi i)+d(v)+d(vj j)n )n 則則G

27、 G中存在哈密頓回路，從而中存在哈密頓回路，從而G G為哈密頓圖。為哈密頓圖。2022-2-1032e1e2e3e4e5e6d(vi)+d(vj)n-1 存在哈密頓通路存在哈密頓通路d(vi)+d(vj)n 存在哈密頓回路存在哈密頓回路2022-2-1033(2)(3)再如下圖再如下圖G任意兩個不相鄰的頂點任意兩個不相鄰的頂點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為哈密頓圖。為哈密頓圖。ab

28、dc(1)(1)和和(2)2022-2-1034定理定理 8.8 8.8 在在 n (n2)n (n2)階有向圖階有向圖 D=D=中，如果所有中，如果所有有向邊均用無向邊代替，所得無向圖中含生成子有向邊均用無向邊代替，所得無向圖中含生成子圖圖K Kn n, ,則有向圖則有向圖 D D 中存在哈密頓通路中存在哈密頓通路. .推論推論 n(n 3)n(n 3)階有向完全圖階有向完全圖G G為哈密頓圖為哈密頓圖。2022-2-1035例例 8.15 已知有關(guān)人員已知有關(guān)人員a, b, c, d, e, f, g 的有關(guān)信息的有關(guān)信息 a：說英語；說英語； b：說英語或西班牙語；說英語或西班牙語； c

29、；說英語，意大利語和俄語；說英語，意大利語和俄語； d：說日語和西班牙語說日語和西班牙語 e：說德語和意大利語；說德語和意大利語； f：說法語、日語和俄語；說法語、日語和俄語； g：說法語和德語說法語和德語. 試問：上述試問：上述7人中是否任意兩人都能交談？人中是否任意兩人都能交談？ (可借助其余可借助其余5人中組成的譯員鏈幫助人中組成的譯員鏈幫助)2022-2-1036abcdefg解解 設(shè)設(shè)7個人為個人為7個結(jié)點個結(jié)點, 將兩個懂同一語言的人之將兩個懂同一語言的人之間連一條邊間連一條邊(即他們能直接交談即他們能直接交談), 這樣就得到一個這樣就得到一個簡單圖簡單圖G, 問題就轉(zhuǎn)化為問題就轉(zhuǎn)

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

31、邊的人交談？能使每個人都能與他身邊的人交談？解：用結(jié)點表示人，用邊表示連接的兩個人能將解：用結(jié)點表示人，用邊表示連接的兩個人能將同一種語言，夠造出同一種語言，夠造出哈密頓圖如右上哈密頓圖如右上圖所示。圖所示。a：說英語；說英語；b：說英語或西班牙語；說英語或西班牙語；c；說英語，意大利說英語，意大利 語和俄語；語和俄語；d：說日語和西班牙語說日語和西班牙語e：說德語和意大利語；說德語和意大利語；f：說法語、日語和俄語；說法語、日語和俄語；g：說法語和德語說法語和德語. 英英英英西西日日法法德德意意2022-2-1038 對于對于平面圖平面圖, 先舉一例先舉一例, 設(shè)有一個電路它有六設(shè)有一個電路

32、它有六個元件，三個分成一組，一個元件組的每個元個元件，三個分成一組，一個元件組的每個元件都用導(dǎo)線與另一組的每個元件相接，是否有件都用導(dǎo)線與另一組的每個元件相接，是否有這樣的接法使得導(dǎo)線互不交叉？這個問題可用這樣的接法使得導(dǎo)線互不交叉？這個問題可用左下圖表示左下圖表示, 它的最少交叉點是一個，用右下圖它的最少交叉點是一個，用右下圖表示表示8.4.平面圖平面圖2022-2-1039定義定義 8. 6 一個圖一個圖G能畫在平面上，除頂點之外，再沒能畫在平面上，除頂點之外，再沒有邊與邊相交有邊與邊相交. 則稱則稱G為為平面圖平面圖。 畫出的沒有邊交叉的圖稱為畫出的沒有邊交叉的圖稱為G的一個的一個平面嵌

33、平面嵌入入或或G的的一個平面一個平面.在下圖中在下圖中(2)是是(1) (K4)的平面嵌入的平面嵌入, 所以所以(1)是平面是平面圖圖, 單獨看單獨看(2)也是平面圖也是平面圖, 對于對于(3) (K5)無論怎樣無論怎樣畫法畫法,也去不掉交叉邊也去不掉交叉邊, 所以不是平面圖。所以不是平面圖。(1)(2)(3)(4)2022-2-1040 例例 8.16 右下圖是左下圖的平面嵌入右下圖是左下圖的平面嵌入, 所以左下圖所以左下圖是平面圖是平面圖, 單獨看右下圖也是平面圖。單獨看右下圖也是平面圖。2022-2-1041定義定義 8. 7 設(shè)設(shè)G是一個連通的平面圖是一個連通的平面圖, G的邊將的邊將

34、G所在的所在的平面劃分成若干個區(qū)域平面劃分成若干個區(qū)域, 每個區(qū)域稱為每個區(qū)域稱為G的一個的一個面面。其中面積無限的區(qū)域稱為。其中面積無限的區(qū)域稱為無限面或外部面無限面或外部面, 常記為常記為R0, 面積有限的區(qū)域稱為面積有限的區(qū)域稱為有限面或內(nèi)部面有限面或內(nèi)部面。包圍每個面的所有邊所構(gòu)成的回路稱為該面的包圍每個面的所有邊所構(gòu)成的回路稱為該面的邊邊界界, 邊界的長度稱為該面的邊界的長度稱為該面的次數(shù)次數(shù), R次數(shù)記為次數(shù)記為deg(R) 對于非連通的平面圖對于非連通的平面圖G可以類似地定義它的面、可以類似地定義它的面、邊界及次數(shù)。邊界及次數(shù)。2022-2-1042v1v2v3v4v5v6v1v2v3v4v5v6v7R0R1R2R1R0R2( 1 )( 2 )在下圖中在下圖中, 圖圖(1)所示為連通的平面圖所示為連通的平面圖, 共有共有3個面?zhèn)€面R0, R1, R2。 R1的邊界為初級回路的邊界為初級回路v1 v3 v4 v1 , deg(R1)=3。R2的邊界為初級回路的邊界為初級回路v1 v2 v3 v1 , deg(R2)=3。R0無限面無限面, 它的邊界為復(fù)雜回路它的邊界為復(fù)雜回路v1 v4 v5v6 v5 v4 v3 v2 v1 , deg(R0)=8。圖圖(2)所示為非所示為