1、離 散 數(shù) 學(xué),電子科技大學(xué),計(jì)算機(jī)科學(xué)與工程學(xué)院 示 范 性 軟 件 學(xué) 院,2020年8月6日星期四,2020/8/6,第11章 特殊圖,2020/8/6,11.0 內(nèi)容提要,幾個(gè)特殊圖的概念：歐拉圖、哈密頓圖、偶圖、平面圖； 歐拉圖、哈密頓圖、偶圖、平面圖的判定； 偶圖的匹配、圖的著色； 歐拉圖、哈密頓圖、偶圖、平面圖的應(yīng)用,2020/8/6,10.1 本章學(xué)習(xí)要求,2020/8/6,11.2 歐拉圖,11.2.1 歐拉圖的引入與定義,2020/8/6,定義11.2.1,設(shè)G是無(wú)孤立結(jié)點(diǎn)的圖，若存在一條通路(回路)，經(jīng)過(guò)圖中每邊一次且僅一次，則稱(chēng)此通路(回路)為該圖的一條歐拉通路(回路)

2、(Eulerian Entry/Circuit)。 具有歐拉回路的圖稱(chēng)為歐拉圖(Eulerian Graph)。 規(guī)定：平凡圖為歐拉圖。 以上定義既適合無(wú)向圖，又適合有向圖。,2020/8/6,歐拉通路和歐拉回路的特征,歐拉通路是經(jīng)過(guò)圖中所有邊的通路中長(zhǎng)度最短的通路，即為通過(guò)圖中所有邊的簡(jiǎn)單通路； 歐拉回路是經(jīng)過(guò)圖中所有邊的回路中長(zhǎng)度最短的回路，即為通過(guò)圖中所有邊的簡(jiǎn)單回路。 如果僅用邊來(lái)描述，歐拉通路和歐拉回路就是圖中所有邊的一種全排列。,2020/8/6,例11.2.1,判斷下面的6個(gè)圖中，是否是歐拉圖？是否存在歐拉通路？,歐拉圖,歐拉圖,不是歐拉圖，但存在歐拉通路,不存在歐拉通路,不存在

3、歐拉通路,不是歐拉圖，但存在歐拉通路,2020/8/6,11.2.2 歐拉圖的判定,定理11.2.1 無(wú)向圖G = 具有一條歐拉通路，當(dāng)且僅當(dāng)G是連通的，且僅有零個(gè)或兩個(gè)奇度數(shù)結(jié)點(diǎn)。 分析 只要找到了，就是存在的。我們具體找一條歐拉通路。對(duì)于結(jié)點(diǎn)的度數(shù)，我們?cè)谕分腥ビ?jì)算。 證明 若G為平凡圖，則定理顯然成立。故我們下面討論的均為非平凡圖。,2020/8/6,必要性：G有歐拉通路 = G連通，且僅有零個(gè)或兩個(gè)奇度數(shù)結(jié)點(diǎn),設(shè)G具有一條歐拉通路L = ，則L經(jīng)過(guò)G中的每條邊，由于G中無(wú)孤立結(jié)點(diǎn)，因而L經(jīng)過(guò)G的所有結(jié)點(diǎn)，所以G是連通的。 對(duì)歐拉通路L的任意非端點(diǎn)的結(jié)點(diǎn) ，在L中每出現(xiàn) 一次，都關(guān)聯(lián)兩

4、條邊 和 ，而當(dāng) 重復(fù)出現(xiàn)時(shí)，它又關(guān)聯(lián)另外的兩條邊，由于在通路L中邊不可能重復(fù)出現(xiàn)，因而每出現(xiàn)一次都將使某點(diǎn)獲得2度。若在L中重復(fù)出現(xiàn)p次，則deg( )= 2p。,2020/8/6,必要性：G有歐拉通路 = G連通，且僅有零個(gè)或兩個(gè)奇度數(shù)結(jié)點(diǎn),若端點(diǎn) ，設(shè) 、 在通路中作為非端點(diǎn)分別出現(xiàn)p1和p2次，則 deg( )= 2p1+1，deg( ) = 2p2+1 因而G有兩個(gè)度數(shù)為奇數(shù)的結(jié)點(diǎn)。 若端點(diǎn) = ，設(shè)在通路中作為非端點(diǎn)出現(xiàn)p3次，則 deg( )= 1+2p3+1 = 2(p3+1) 因而G無(wú)度數(shù)為奇數(shù)的結(jié)點(diǎn)。,2020/8/6,充分性：構(gòu)造性證明。,從兩個(gè)奇度數(shù)結(jié)點(diǎn)之一開(kāi)始(若無(wú)奇

5、度數(shù)結(jié)點(diǎn)，可從任一結(jié)點(diǎn)開(kāi)始)構(gòu)造一條歐拉通路，以每條邊最多經(jīng)過(guò)一次的方式通過(guò)圖中的邊。 對(duì)于度數(shù)為偶數(shù)的結(jié)點(diǎn)，通過(guò)一條邊進(jìn)入這個(gè)結(jié)點(diǎn)，總可以通過(guò)一條未經(jīng)過(guò)的邊離開(kāi)這個(gè)結(jié)點(diǎn)，因此，這樣的構(gòu)造過(guò)程一定以到達(dá)另一個(gè)奇度數(shù)結(jié)點(diǎn)而告終(若無(wú)奇度數(shù)結(jié)點(diǎn)，則以回到原出發(fā)點(diǎn)而告終)。 如果圖中所有的邊已用這種方式經(jīng)過(guò)了，顯然這就是所求的歐拉通路。如果圖中不是所有的邊都經(jīng)過(guò)了，則去掉已經(jīng)過(guò)的邊，得到一個(gè)由剩余的邊組成的子圖，這個(gè)子圖的所有結(jié)點(diǎn)的度數(shù)均為偶數(shù)。,2020/8/6,因?yàn)樵瓉?lái)的圖是連通的，因此，這個(gè)子圖必與我們已經(jīng)過(guò)的通路在一個(gè)或多個(gè)結(jié)點(diǎn)相接。 從這些結(jié)點(diǎn)中的一個(gè)開(kāi)始，我們?cè)偻ㄟ^(guò)邊構(gòu)造通路，因?yàn)榻Y(jié)點(diǎn)的

6、度數(shù)全是偶數(shù)，因此，這條通路一定最終回到起點(diǎn)。我們將這條回路加到已構(gòu)造好的通路中間組合成一條通路。如有必要，這一過(guò)程重復(fù)下去，直到我們得到一條通過(guò)圖中所有邊的通路，即歐拉通路。 由定理11.2.1的證明知：若連通的無(wú)向圖有兩個(gè)奇度數(shù)結(jié)點(diǎn)，則它們是G中每條歐拉通路的端點(diǎn)。,2020/8/6,結(jié)論,推論11.2.1 無(wú)向圖G = 具有一條歐拉回路，當(dāng)且僅當(dāng)G是連通的，并且所有結(jié)點(diǎn)的度數(shù)均為偶數(shù)。 定理11.2.2 有向圖G具有一條歐拉通路，當(dāng)且僅當(dāng)G是連通的，且除了兩個(gè)結(jié)點(diǎn)以外，其余結(jié)點(diǎn)的入度等于出度，而這兩個(gè)例外的結(jié)點(diǎn)中，一個(gè)結(jié)點(diǎn)的入度比出度大1，另一個(gè)結(jié)點(diǎn)的出度比入度大1。 推論11.2.2

7、有向圖G具有一條歐拉回路，當(dāng)且僅當(dāng)G是連通的，且所有結(jié)點(diǎn)的入度等于出度。,2020/8/6,歐拉通路與歐拉回路判別準(zhǔn)則,對(duì)任意給定的無(wú)向連通圖，只需通過(guò)對(duì)圖中各結(jié)點(diǎn)度數(shù)的計(jì)算，就可知它是否存在歐拉通路及歐拉回路，從而知道它是否為歐拉圖；對(duì)任意給定的有向連通圖，只需通過(guò)對(duì)圖中各結(jié)點(diǎn)出度與入度的計(jì)算，就可知它是否存在歐拉通路及歐拉回路，從而知道它是否為歐拉圖。 利用這項(xiàng)準(zhǔn)則，很容易判斷出哥尼斯堡七橋問(wèn)題是無(wú)解的，因?yàn)樗鶎?duì)應(yīng)的圖中所有4個(gè)結(jié)點(diǎn)的度數(shù)均為奇數(shù)；也很容易得到例11.2.1的結(jié)論。,2020/8/6,定義11.2.2,設(shè)G = ，eE，如果 p(G-e)p(G) 稱(chēng)e為G的橋(Bridg

8、e)或割邊(Cut edge)。 顯然，所有的懸掛邊都是橋。,2020/8/6,Fleury算法,算法11.2.1 求歐拉圖G = 的歐拉回路的Fleury算法： （1）任取v0V，令P0 = v0，i = 0； （2）按下面的方法從E-e1, e2, , ei中選取ei+1： a. ei+1與vi相關(guān)聯(lián)； b. 除非無(wú)別的邊可選取，否則ei+1不應(yīng)該為G = G-e1, e2, , ei中的橋； （3）將邊ei+1加入通路P0中，令P0 = v0e1v1e2eiviei+1vi+1，i = i+1； （4）如果i = |E|，結(jié)束，否則轉(zhuǎn)(2)。,2020/8/6,例11.2.2,用Fleu

9、ry算法求歐拉圖的一條歐拉回路。,v1,v7,v5,v3,v2,v8,v4,e1,e2,e3,e4,e5,e6,e10,e7,e8,e9,e11,e12,v6,分析 求從v1出發(fā)，按照Fleury算法，每次走一條邊，在可能的情況下，不走橋。例如，在得到 P7 = v1e1v2e2v3e3v4e4v5e5v6e6v7e7v8 時(shí)，G = G-e1, e2, , e7中的e8是橋，因此下一步選擇走e9，而不要走e8。,解 從v1出發(fā)的一條歐拉回路為： P12 = v1e1v2e2v3e3v4e4v5e5v6e6v7e7v8e9v2e10v4e11v6e12v8e8v1,2020/8/6,11.2.

10、3 歐拉圖的難點(diǎn),僅有歐拉通路而無(wú)歐拉回路的圖不是歐拉圖； 圖中是否存在歐拉通路、歐拉回路圖的判定非常簡(jiǎn)單，只需要數(shù)一下圖中結(jié)點(diǎn)的度數(shù)即可； 使用Fleury算法求歐拉通路(回路)時(shí)，每次走一條邊，在可能的情況下，不走橋。,2020/8/6,11.2.4 歐拉圖的應(yīng)用,1、一筆畫(huà)問(wèn)題 所謂“一筆畫(huà)問(wèn)題”就是畫(huà)一個(gè)圖形，筆不離紙，每條邊只畫(huà)一次而不許重復(fù)，畫(huà)完該圖。 “一筆畫(huà)問(wèn)題”本質(zhì)上就是一個(gè)無(wú)向圖是否存在歐拉通路(回路)的問(wèn)題。如果該圖為歐拉圖，則能夠一筆畫(huà)完該圖，并且筆又回到出發(fā)點(diǎn)；如果該圖只存在歐拉通路，則能夠一筆畫(huà)完該圖，但筆回不到出發(fā)點(diǎn)；如果該圖中不存在歐拉通路，則不能一筆畫(huà)完該圖。

11、,2020/8/6,例11.2.3,圖中的三個(gè)圖能否一筆畫(huà)？為什么？,解 因?yàn)閳D(a)和(b)中分別有0個(gè)和2個(gè)奇度數(shù)結(jié)點(diǎn)，所以它們分別是歐拉圖和存在歐拉通路，因此能夠一筆畫(huà)，并且在(a)中筆能回到出發(fā)點(diǎn)，而(b)中筆不能回到出發(fā)點(diǎn)。圖c中有4個(gè)度數(shù)為3的結(jié)點(diǎn)，所以不存在歐拉通路，因此不能一筆畫(huà)。,2020/8/6,2、螞蟻比賽問(wèn)題,例11.2.4 甲、乙兩只螞蟻分別位于圖的結(jié)點(diǎn)A、B處，并設(shè)圖中的邊長(zhǎng)度相等。甲、乙進(jìn)行比賽：從它們所在的結(jié)點(diǎn)出發(fā)，走過(guò)圖中所有邊最后到達(dá)結(jié)點(diǎn)C處。如果它們的速度相同，問(wèn)誰(shuí)先到達(dá)目的地？,解 圖中僅有兩個(gè)度數(shù)為奇數(shù)的結(jié)點(diǎn)B、C，因而存在從B到C的歐拉通路，螞蟻乙走

12、到C只要走一條歐拉通路，邊數(shù)為9條，而螞蟻甲要想走完所有的邊到達(dá)C，至少要先走一條邊到達(dá)B，再走一條歐拉通路，因而它至少要走10條邊才能到達(dá)C，所以乙必勝。,2020/8/6,3、計(jì)算機(jī)鼓輪設(shè)計(jì),假設(shè)一個(gè)旋轉(zhuǎn)鼓的表面被等分為24個(gè)部分，如圖所示，其中每一部分分別由導(dǎo)體或絕緣體構(gòu)成，圖中陰影部分表示導(dǎo)體，空白部分表示絕緣體，導(dǎo)體部分給出信號(hào)1，絕緣體部分給出信號(hào)0。根據(jù)鼓輪轉(zhuǎn)動(dòng)時(shí)所處的位置，,四個(gè)觸頭A、B、C、D將獲得一定的信息。因此，鼓輪的位置可用二進(jìn)制信號(hào)表示。試問(wèn)如何選取鼓輪16個(gè)部分的材料才能使鼓輪每轉(zhuǎn)過(guò)一個(gè)部分得到一個(gè)不同的二進(jìn)制信號(hào)，即每轉(zhuǎn)一周，能得到0000到1111的16個(gè)數(shù)。

13、,2020/8/6,問(wèn)題的等價(jià)描述與解決方法,問(wèn)題的等價(jià)描述：把16個(gè)二進(jìn)制數(shù)排成一個(gè)圓圈，使得四個(gè)依次相連的數(shù)字所組成的16個(gè)四位二進(jìn)制數(shù)互不相同。 問(wèn)題的解決思想：設(shè)ai0,1(i= 1,2,3, 16)，鼓輪每轉(zhuǎn)一個(gè)部分，信號(hào)就從a1a2a3a4變?yōu)閍2a3a4a5，前者的右三位決定了后者的左三位。 我們可把所有三位二進(jìn)制數(shù)作為結(jié)點(diǎn)，從每個(gè)結(jié)點(diǎn)a1a2a3到a2a3a4連一條有向邊表示a1a2a3a4這個(gè)四位二進(jìn)制數(shù)，作出的所有可能的碼變換的有向圖。,2020/8/6,所有可能的碼變換的有向圖,e00000e81000 e10001e91001 e20010e101010 e30011e

14、111011 e40100e121100 e50101e131101 e60110e141110 e70111e151111,2020/8/6,問(wèn)題的求解,問(wèn)題轉(zhuǎn)化為在這個(gè)有向圖中找一條歐拉回路。 這個(gè)有向圖中8個(gè)結(jié)點(diǎn)的出度和入度都是2，因此存在歐拉回路。 例如e0e1e2e4e9e3e6e13e10e5e11e7e15e14e12e8就是一條歐拉回路。根據(jù)鄰接邊的標(biāo)號(hào)記法，這16個(gè)二進(jìn)制數(shù)的可寫(xiě)成對(duì)應(yīng)的二進(jìn)制序列0000100110101111，把這個(gè)序列排成一個(gè)圓圈，與所求的鼓輪相對(duì)應(yīng)，就得到鼓輪的設(shè)計(jì)。,2020/8/6,推廣,存在一個(gè)2n個(gè)二進(jìn)制數(shù)的循環(huán)序列，其中2n個(gè)由n位二進(jìn)制數(shù)組

15、成的子序列全不相同。 將上述2n個(gè)二進(jìn)制數(shù)的循環(huán)序列稱(chēng)為布魯因(De Brujin)序列。,2020/8/6,11.3 哈密頓圖,11.2.1 哈密頓的引入與定義,2020/8/6,哈密頓圖,定義11.3.1 經(jīng)過(guò)圖中每個(gè)結(jié)點(diǎn)一次且僅一次的通路(回路)稱(chēng)為哈密頓通路(回路)(Hamiltonian Entry/circuit)。存在哈密頓回路的圖稱(chēng)為哈密頓圖(Hamiltonian Graph)。 規(guī)定：平凡圖為哈密頓圖。 以上定義既適合無(wú)向圖，又適合有向圖。,2020/8/6,哈密頓通路和哈密頓回路的特征,哈密頓通路是經(jīng)過(guò)圖中所有結(jié)點(diǎn)的通路中長(zhǎng)度最短的通路，即為通過(guò)圖中所有結(jié)點(diǎn)的基本通路；

16、哈密頓回路是經(jīng)過(guò)圖中所有結(jié)點(diǎn)的回路中長(zhǎng)度最短的回路，即為通過(guò)圖中所有結(jié)點(diǎn)的基本回路。 如果僅用結(jié)點(diǎn)來(lái)描述： 哈密頓通路就是圖中所有結(jié)點(diǎn)的一種全排列 哈密頓回路就是圖中所有結(jié)點(diǎn)的一種全排列再加上該排列中第一個(gè)結(jié)點(diǎn)的一種排列。,2020/8/6,例11.3.1,判斷下面的6個(gè)圖中，是否是哈密頓圖？是否存在哈密頓通路？,哈密 頓圖,不存在哈密頓通路,不是哈密頓圖，但存在哈密頓通路,哈密 頓圖,不是哈密頓圖，但存在哈密頓通路,不存在哈密頓通路,2020/8/6,11.3.2 哈密頓圖的判定,定理11.3.1 設(shè)無(wú)向圖G = 是哈密頓圖，V1是V的任意非空子集，則 p(G-V1) |V1| 其中p(G-

17、V1)是從G中刪除V1后，所得到的圖的連通分支數(shù)。 分析 考察G的一條哈密頓回路C，顯然C是G的生成子圖，從而C-V1也是G-V1的生成子圖，且有p(G-V1) p(C-V1)，故只需要證明p(C-V1) |V1|即可。,2020/8/6,定理11.3.1 證明,設(shè)C是G中的一條哈密頓回路，V1是V的任意非空子集。下面分兩種情況討論： （1）V1中結(jié)點(diǎn)在C中均相鄰，刪除C上V1中各結(jié)點(diǎn)及關(guān)聯(lián)的邊后，C-V1仍是連通的，但已非回路，因此p(C-V1) = 1 |V1|。 （2）V1中結(jié)點(diǎn)在C上存在r(2 r |V1|)個(gè)互不相鄰，刪除C上V1中各結(jié)點(diǎn)及關(guān)聯(lián)的邊后，將C分為互不相連的r段，即 p(

18、C-V1) = r |V1|。 一般情況下，V1中的結(jié)點(diǎn)在C中即有相鄰的，又有不相鄰的，因此總有p(C-V1) |V1|。 又因C是G的生成子圖，從而C-V1也是G-V1的生成子圖，故有 p(G-V1) p(C-V1) |V1|,2020/8/6,推論11.3.1,設(shè)無(wú)向圖G = 中存在哈密頓通路，則對(duì)V的任意非空子集V1，都有 p(G-V1) |V1| + 1,注意： 若存在V的某個(gè)非空子集V1使得p(G-V1)|V1|，則G不是哈密頓圖。,2020/8/6,例11.3.2,證明圖中不存在哈密頓回路。,證明：刪除結(jié)點(diǎn)子集d, e, f，得新圖，它的連通分支為4個(gè)，因而不會(huì)存在哈密頓回路。,2

19、020/8/6,定理11.3.2,設(shè)G = 是具有n個(gè)結(jié)點(diǎn)的簡(jiǎn)單無(wú)向圖。如果對(duì)任意兩個(gè)不相鄰的結(jié)點(diǎn)u, vV，均有 deg(u) + deg(v) n-1 則G中存在哈密頓通路。 證明 首先證明滿(mǎn)足上述條件的G是連通圖。 用反證法：假設(shè)G有兩個(gè)或更多連通分支。 設(shè)一個(gè)連通分支有n1個(gè)結(jié)點(diǎn)，另一個(gè)連通分支有n2個(gè)結(jié)點(diǎn)。這二個(gè)連通分支中分別有兩個(gè)結(jié)點(diǎn)v1、v2。 顯然，deg(v1)n1-1，deg(v2)n2-1。 從而deg(v1)+deg(v2)n1+n2-2 n-2與已知矛盾，故G是連通的。,2020/8/6,定理11.3.2 證明(續(xù)),其次，證明G中存在哈密頓通路。 設(shè)P = v1v2

20、vk為G中用“延長(zhǎng)通路法”得到的“極大基本通路”，即P的始點(diǎn)v1與終點(diǎn)vk不與P外的結(jié)點(diǎn)相鄰，顯然k n。 （1）若k = n，則P為G中經(jīng)過(guò)所有結(jié)點(diǎn)的通路，即為哈密頓通路。 （2）若k n，說(shuō)明G中還有在P外的結(jié)點(diǎn)，但此時(shí)可以證明存在僅經(jīng)過(guò)P上所有結(jié)點(diǎn)的基本回路，證明如下： （a）若在P上v1與vk相鄰，則v1v2vkv1為僅經(jīng)過(guò)P上所有結(jié)點(diǎn)的基本回路。,2020/8/6,定理11.3.2 證明(續(xù)),（b）若在P上v1與vk不相鄰，假設(shè)v1在P上與vi1= v2,vi2,vi3,vij相鄰(j必定大于等于2，否則deg(v1)+deg(vk) 1+k-2n-1)， 此時(shí)vk必與vi2,vi

21、3,vij相鄰的結(jié)點(diǎn)vi2-1,vi3-1,vij-1至少之一相鄰(否則deg(v1) + deg(vk) j+k-2-(j-1) = k-1n-1)。設(shè)vk與vir-1(2rj)相鄰，如圖所示。,2020/8/6,定理11.3.2 證明(續(xù)),在P中添加邊(v1,vir)、(vk,vir-1)，刪除邊(vir-1,vir)得基本回路C = v1v2vir-1vkvk-1virv1。,2020/8/6,定理11.3.2 證明(續(xù)),（3）證明存在比P更長(zhǎng)的通路。 因?yàn)閗n，所以V中還有一些結(jié)點(diǎn)不在C中，由G的連通性知，存在C外的結(jié)點(diǎn)與C上的結(jié)點(diǎn)相鄰，不妨設(shè)vk+1V-V(C)且與C上結(jié)點(diǎn)vt相

22、鄰，在C中刪除邊(vt-1,vt)而添加邊(vt,vk+1)得到通路P= vt-1v1virvkvir-1vtvk+1。 顯然，P比P長(zhǎng)1，且P上有k+1個(gè)不同的結(jié)點(diǎn)。 對(duì)P重復(fù)(1)(3)，得到G中的哈密頓通路或比P更長(zhǎng)的基本通路。 由于G中結(jié)點(diǎn)數(shù)目有限，故在有限步內(nèi)一定得到G中的一條哈密頓通路。,2020/8/6,推論,推論11.3.2 設(shè)G = 是具有n個(gè)結(jié)點(diǎn)的簡(jiǎn)單無(wú)向圖。如果對(duì)任意兩個(gè)不相鄰的結(jié)點(diǎn)u, vV，均有 deg(u) + deg(v) n 則G中存在哈密頓回路。 推論11.3.3 設(shè)G = 是具有n個(gè)結(jié)點(diǎn)的簡(jiǎn)單無(wú)向圖，n3。如果對(duì)任意vV，均有deg(v) n/2，則G是哈密

23、頓圖。,哈密頓圖的充分條件，而非必要條件。,2020/8/6,例11.3.3,某地有5個(gè)風(fēng)景點(diǎn)，若每個(gè)風(fēng)景點(diǎn)均有2條道路與其他點(diǎn)相通。問(wèn)游人可否經(jīng)過(guò)每個(gè)風(fēng)景點(diǎn)恰好一次而游完這5處？ 解 將5個(gè)風(fēng)景點(diǎn)看成是有5個(gè)結(jié)點(diǎn)的無(wú)向圖，兩風(fēng)景點(diǎn)間的道路看成是無(wú)向圖的邊，因?yàn)槊刻幘袃蓷l道路與其他結(jié)點(diǎn)相通，故每個(gè)結(jié)點(diǎn)的度數(shù)均為2，從而任意兩個(gè)不相鄰的結(jié)點(diǎn)的度數(shù)之和等于4，正好為總結(jié)點(diǎn)數(shù)減1。故此圖中存在一條哈密頓通路，因此游人可以經(jīng)過(guò)每個(gè)風(fēng)景點(diǎn)恰好一次而游完這5處。,2020/8/6,例11.3.4,判斷下圖是否存在哈密頓回路。,解 方法一：在圖中，刪除結(jié)點(diǎn)子集a, b, c, d, e，得到的圖有7個(gè)連通

24、分支，由定理11.2.1知，該圖不是哈密頓圖，因而不會(huì)存在哈密頓回路。,方法二：若圖中存在哈密頓回路，則該回路組成的圖中任何結(jié)點(diǎn)的度數(shù)均為2。因而結(jié)點(diǎn)1、2、3、4、5所關(guān)聯(lián)的邊均在回路中，于是在結(jié)點(diǎn)a、b、c、d、e處均應(yīng)將不與1、2、3、4、5關(guān)聯(lián)的邊刪除，而要?jiǎng)h除與結(jié)點(diǎn)a、b、c、d、e關(guān)聯(lián)的其它邊，得到右上圖，它不是連通圖，因而圖中不存在哈密頓回路。,2020/8/6,例11.3.5,證明下圖沒(méi)有哈密頓通路。,證明 任取一結(jié)點(diǎn)如1用A標(biāo)記，所有與它鄰接的結(jié)點(diǎn)用B標(biāo)記。繼續(xù)不斷地用A標(biāo)記所有鄰接于B的結(jié)點(diǎn)，用B標(biāo)記所有鄰接于A的結(jié)點(diǎn)，直到所有結(jié)點(diǎn)都標(biāo)記完畢。 如果圖中有一條哈密頓通路，那

25、么它必交替通過(guò)結(jié)點(diǎn)A和B，故而標(biāo)記A的結(jié)點(diǎn)與標(biāo)記B的結(jié)點(diǎn)數(shù)目或者相同，或者相差1個(gè)。然而圖中有3個(gè)結(jié)點(diǎn)標(biāo)記為A，5個(gè)結(jié)點(diǎn)標(biāo)記為B，它們相差兩個(gè)，所以該圖不存在哈密頓通路。,2020/8/6,定理11.3.3,設(shè)G = 是有n(n2)個(gè)結(jié)點(diǎn)的一些簡(jiǎn)單有向圖。如果忽略G中邊的方向所得的無(wú)向圖中含生成子圖Kn，則有向圖G中存在哈密頓通路。,在右圖中，它所對(duì)應(yīng)的無(wú)向圖中含完全圖K5，由定理11.3.3知，圖中含有哈密頓通路。事實(shí)上，通路v3v5v4v2v1為一條哈密頓通路。,2020/8/6,11.3.3 哈密頓圖的難點(diǎn),僅有哈密頓通路而無(wú)哈密頓回路的圖不是哈密頓圖； 還沒(méi)有判斷圖中是否存在歐拉通路、

26、歐拉回路圖的簡(jiǎn)單判定定理，我們只能對(duì)結(jié)點(diǎn)較少的圖憑經(jīng)驗(yàn)去判定； 在哈密頓圖中有定理僅是必要條件，此必要條件正方面的敘述無(wú)法用來(lái)判斷一個(gè)圖是否是哈密頓圖，此時(shí)該定理是毫無(wú)用處的，但必要條件的等價(jià)逆敘述卻非常的重要，用此逆敘述可以判斷一個(gè)圖不是哈密頓圖。,2020/8/6,11.3.4 哈密頓圖的應(yīng)用,1、巡回售貨員問(wèn)題 G = 是n個(gè)結(jié)點(diǎn)的賦權(quán)完全圖，這里V = v1, v2, , vn是城市的集合，E是連接城市的道路的集合，W是從E到正實(shí)數(shù)集合的一個(gè)函數(shù)(即W(vi, vj)是城市vi與vj之間的距離)，顯然對(duì)V中任意三個(gè)城市vi, vj, vk，顯然它們之間的距離應(yīng)滿(mǎn)足三角不等式： W(vi

27、, vj) + W(vj, vk)W(vi, vk)， 試求出該賦權(quán)圖上的最短哈密頓回路。,2020/8/6,算法11.3.1 最鄰近算法：,以vi為始點(diǎn)，在其余n-1個(gè)結(jié)點(diǎn)中，找出與始點(diǎn)最鄰近的結(jié)點(diǎn)vj(如果與vi最鄰近的結(jié)點(diǎn)不唯一，則任選其中的一個(gè)作為vj)，形成具有一條邊的通路vivj； 假設(shè)x是最新加入到這條通路中的結(jié)點(diǎn)，從不在通路上的結(jié)點(diǎn)中選取一個(gè)與x最鄰近的結(jié)點(diǎn)，把連接x與此結(jié)點(diǎn)的邊加到這條通路中。重復(fù)這一步，直到G中所有結(jié)點(diǎn)都包含在通路中； 把始點(diǎn)和最后加入的結(jié)點(diǎn)之間的邊放入，就得到一條回路。,2020/8/6,8,16,7,12,4,例11.3.6,用最鄰近算法計(jì)算下圖的以a為

28、始點(diǎn)的一條近似最短哈密頓回路。,回路的總距離為47,2020/8/6,其它結(jié)點(diǎn)為始點(diǎn)的哈密頓回路,以b為始點(diǎn)的哈密頓回路為：badecb，總距離為：42。 以c為始點(diǎn)的哈密頓回路為：cbadec，總距離為：42；或cdaebc，總距離為：35；或cdabec，總距離為：42。 以d為始點(diǎn)的哈密頓回路為：dabecd，總距離為：42；或daebcd，總距離為：35。 以e為始點(diǎn)的哈密頓回路為：eadbce，總距離為：41。,2020/8/6,分析及結(jié)論,圖中最短哈密頓回路的長(zhǎng)度為35 最長(zhǎng)哈密頓回路的長(zhǎng)度為48。 若以a為始點(diǎn)，用最鄰近算法求得的哈密頓回路的長(zhǎng)度為47，幾乎達(dá)到了最長(zhǎng)哈密頓回路的

29、長(zhǎng)度。 最鄰近算法不是好的算法?？梢宰C明這個(gè)算法的誤差可以很大。,2020/8/6,算法11.3.2 抄近路算法：,求G中的一棵最小生成樹(shù)T； 將T中各邊均加一條與原邊權(quán)值相同的平行邊，設(shè)所得圖為G，顯然G是歐拉圖； 求G中的一條歐拉回路E； 在E中按如下方法求從結(jié)點(diǎn)v出發(fā)的一個(gè)哈密頓回路H：從v出發(fā)，沿E訪問(wèn)G中各個(gè)結(jié)點(diǎn)，在沒(méi)有訪問(wèn)完所有結(jié)點(diǎn)之前，一旦出現(xiàn)重復(fù)出現(xiàn)的結(jié)點(diǎn)，就跳過(guò)它走到下一個(gè)結(jié)點(diǎn)，稱(chēng)這種走法為抄近路走法。W(H)作為最短哈密頓回路的長(zhǎng)度(設(shè)為d0)的近似值。,2020/8/6,例11.3.7,用抄近路算法計(jì)算下圖的以a為始點(diǎn)的一條近似最短哈密頓回路。 求一棵最小生成樹(shù)T； 將T

30、中各邊均加平行邊； 求從結(jié)點(diǎn)a出發(fā)的歐拉回路Ea = aeadabcba； 求從結(jié)點(diǎn)a出發(fā)按抄近路走法的哈密頓回路Ha = aedbca； W(Ha) = 41。,2020/8/6,其它結(jié)點(diǎn)為始點(diǎn)的哈密頓回路,求圖的一棵最小生成樹(shù)T； 將T中各邊均加平行邊； 從結(jié)點(diǎn)c出發(fā)的歐拉回路為Ec = cbaeadabc； 從結(jié)點(diǎn)c出發(fā)按抄近路走法的哈密頓回路為Hc = cbaedc； W(Hc) = 36。,2020/8/6,定理11.3.4,設(shè)賦權(quán)完全圖Kn(n3)滿(mǎn)足三角不等式，d0是Kn中最短哈密頓回路的長(zhǎng)度，H是用抄近路算法求出的Kn中的哈密頓回路，則 W(H) 2d0。,2020/8/6,定

31、理11.3.4 證明,設(shè)T是Kn中的最小生成樹(shù)，E是將T中每邊加平行邊后的圖中的歐拉回路，則W(E) = 2W(T)。由歐拉回路E產(chǎn)生哈密頓回路H時(shí)，因?yàn)镵n滿(mǎn)足三角不等式，所以H的長(zhǎng)度不會(huì)比E的權(quán)大，即 W(H) W(E) = 2W(T)。 Kn中的最短哈密頓回路H0去掉任意一條邊就產(chǎn)生的一棵生成樹(shù)T，從而有 W(T) W(T)d0 因此2W(T)2d0 故W(H)2d0,2020/8/6,2、中國(guó)郵路問(wèn)題,一個(gè)郵遞員送信，要走完他負(fù)責(zé)投遞的全部街道，完成任務(wù)后回到郵局，應(yīng)按怎樣的路線走，他所走的路程才會(huì)最短呢？ 如果將這個(gè)問(wèn)題抽象成圖論的語(yǔ)言，就是給定一個(gè)連通圖，連通圖的每條邊的權(quán)值為對(duì)應(yīng)

32、的街道的長(zhǎng)度(距離)，要在圖中求一回路，使得回路的總權(quán)值最小。,2020/8/6,中國(guó)郵路問(wèn)題,若圖為歐拉圖，只要求出圖中的一條歐拉回路即可。否則，郵遞員要完成任務(wù)就得在某些街道上重復(fù)走若干次。 如果重復(fù)走一次，就加一條平行邊，于是原來(lái)對(duì)應(yīng)的圖就變成了多重圖。只是要求加進(jìn)的平行邊的總權(quán)值最小就行了。 問(wèn)題就轉(zhuǎn)化為：在一個(gè)有奇度數(shù)結(jié)點(diǎn)的賦權(quán)連通圖中，增加一些平行邊，使得新圖不含奇度數(shù)結(jié)點(diǎn)，并且增加的邊的總權(quán)值最小。,2020/8/6,解決問(wèn)題的步驟,要解決上述問(wèn)題，應(yīng)分下面兩個(gè)大步驟。 首先，增加一些邊，使得新圖無(wú)奇度數(shù)結(jié)點(diǎn)，我們稱(chēng)這一步為可行方案(Feasible Scheme)； 其次，調(diào)整

33、可行方案，使其達(dá)到增加的邊的總權(quán)值最小，稱(chēng)這個(gè)最后的方案為最佳方案(Optimal Scheme)。,2020/8/6,例11.3.8,在下圖中，確定一條v1從v1到的回路，使它的權(quán)值最小。事實(shí)上，所確定的回路從任何一個(gè)結(jié)點(diǎn)出發(fā)都可以。,2020/8/6,第一個(gè)可行方案的確定,由于圖中奇度數(shù)結(jié)點(diǎn)為偶數(shù)個(gè)，所以圖中奇度數(shù)結(jié)點(diǎn)可以配對(duì)。又由于圖的連通性，每對(duì)奇度數(shù)結(jié)點(diǎn)之間均存在基本通路，在配好對(duì)的奇度數(shù)結(jié)點(diǎn)之間各確定一條基本通路，然后將通路中的所有邊均加一條平行邊，這樣產(chǎn)生的新圖中無(wú)奇度數(shù)結(jié)點(diǎn)，因而存在歐拉回路。 圖中奇度數(shù)結(jié)點(diǎn)有4個(gè)：v1, v3, v4, v6。任意將它們配2對(duì)：v1與v4配對(duì)

34、，v3與v6配對(duì)。選v1與v4之間的基本通路為v1v6v5v4，v3與v6之間的基本通路為v3v7v1v6。 每條通路中所含的邊均加一條平行邊。,2020/8/6,增加平行邊的圖如下圖所示，它無(wú)奇度數(shù)結(jié)點(diǎn)，因而是歐拉圖。 增加的邊的總權(quán)值為 W(v3,v7)+W(v7,v1)+2W(v1,v6)+W(v6,v5)+W(v5,v4) = 13。,2020/8/6,調(diào)整可行方案，使增加的邊的總數(shù)減少,圖中邊(v1,v6)的重?cái)?shù)為3，若去掉兩條邊，既不影響v1,v6度數(shù)的奇偶性，也不影響圖的連通性，因而可去掉兩條邊。一般情況下，若邊的重?cái)?shù)大于等于3，就去掉偶數(shù)條邊。于是，有下面結(jié)論： I）在最優(yōu)方案

35、中，圖中每條邊的重?cái)?shù)小于等于2 如果將某條基本回路中的平行邊均去掉，而給原來(lái)沒(méi)有平行邊的邊加上平行邊，也不影響圖中結(jié)點(diǎn)度數(shù)的奇偶性。因而，如果在某條基本回路中，平行邊的總權(quán)值大于該回路的權(quán)值的一半，就作上述調(diào)整。,2020/8/6,在圖中，回路v1v2v3v7v1的權(quán)值為6，而平行邊的總權(quán)值為4，大于3，因而應(yīng)給予調(diào)整，調(diào)整后的圖如右圖所示。,我們又有下面的結(jié)論： II）在最優(yōu)方案中，圖中每個(gè)基本回路上平行邊的總權(quán)值不大于該回路的權(quán)值的一半 經(jīng)過(guò)以上調(diào)整的圖，平行邊的總權(quán)值為： W(v1,v2)+W(v2,v3)+W(v4,v5)+W(v5,v6)=5,2020/8/6,判斷最佳方案的標(biāo)準(zhǔn),一

36、個(gè)最佳方案是滿(mǎn)足(1)、(2)的可行方案，反之，一個(gè)可行方案若滿(mǎn)足(1)、(2)兩條，它也一定是最佳方案。 因而I)、II)是最佳方案的充分必要條件。,右圖滿(mǎn)足I)、II)兩條，從而是最佳方案，即圖中的任意一條歐拉回路均為郵遞員的最佳送信路線。,2020/8/6,11.4 偶圖,11.4.1 偶圖的定義 定義11.4.1 若無(wú)向圖G = 的結(jié)點(diǎn)集V能夠劃分為兩個(gè)子集V1, V2，滿(mǎn)足V1V2 = ，且V1V2 = V，使得G中任意一條邊的兩個(gè)端點(diǎn)，一個(gè)屬于V1，另一個(gè)屬于V2，則稱(chēng)G為偶圖(Bipartite Graph)或二分圖(Bigraph)。 V1和V2稱(chēng)為互補(bǔ)結(jié)點(diǎn)子集，偶圖通常記為G

37、 = 。 偶圖沒(méi)有自回路。 平凡圖和零圖可看成特殊的偶圖。,2020/8/6,定義11.4.2,在偶圖G = 中，若V1中的每個(gè)結(jié)點(diǎn)與V2中的每個(gè)結(jié)點(diǎn)都有且僅有一條邊相關(guān)聯(lián)，則稱(chēng)偶圖G為完全偶圖(Complete Bipartite Graph)或完全二分圖(Complete Bigraph)。 記為Ki,j，其中，i = |V1|，j = |V2|。,2020/8/6,例11.4.1,判斷圖中的幾個(gè)圖，那些是偶圖？那些是完全偶圖？,偶圖,偶圖,偶圖,偶圖,不是偶圖,完全偶圖K2,3,完全偶圖K3,3,完全偶圖K3,3,2020/8/6,11.4.2 偶圖的判定,定理11.4.1 無(wú)向圖G =

38、 為偶圖的充分必要條件是G中所有回路的長(zhǎng)度均為偶數(shù)。 證明 必要性：設(shè)圖G是偶圖G = ，令C = v0v1v2vkv0是G的一條回路，其長(zhǎng)度為k+1。 不失一般性，假設(shè)v0V1，由偶圖的定義知，v1V2，v2V1。由此可知，v2iV1且v2i+1V2。 又因?yàn)関0V1，所以vkV2，因而k為奇數(shù)，故C的長(zhǎng)度為偶數(shù)。,2020/8/6,充分性：證明G = 為偶圖,設(shè)G中每條回路的長(zhǎng)度均為偶數(shù)，若G是連通圖，任選v0V，定義V的兩個(gè)子集如下： V1 = vi | d(v0, vi)為偶數(shù)， V2 = V-V1 現(xiàn)證明V1中任兩結(jié)點(diǎn)間無(wú)邊存在。 假若存在一條邊(vi, vj)E，其中vi, vjV

39、1，則由v0到vi間的短程線(長(zhǎng)度為偶數(shù))以及邊(vi, vj)，再加上vj到v0間的短程線(長(zhǎng)度為偶數(shù))所組成的回路的長(zhǎng)度為奇數(shù)，與假設(shè)矛盾。,2020/8/6,充分性（續(xù)）：,同理可證V2中任兩結(jié)點(diǎn)間無(wú)邊存在。 故G中每條邊(vi, vj)，必有viV1，vjV2或viV2，vjV1，因此G是具有互補(bǔ)結(jié)點(diǎn)子集V1和V2的偶圖。 若G中每條回路的長(zhǎng)度均為偶數(shù)，但G不是連通圖，則可對(duì)G的每個(gè)連通分支重復(fù)上述論證，并可得到同樣的結(jié)論。,2020/8/6,定理11.4.1的用途,在實(shí)際應(yīng)用中，定理11.4.1本身使用不多，我們常使用它的逆否命題來(lái)判斷一個(gè)圖不是偶圖： 無(wú)向圖G不是偶圖的充分必要條件

40、是G中存在長(zhǎng)度為奇數(shù)的回路。 例如下圖中存在長(zhǎng)度為3的回路v1v2v4v1，所以它不是偶圖。,2020/8/6,11.4.3 匹配,定義11.4.2 在偶圖G = 中，V1 = v1, v2, , vq，若存在E的子集E = (v1, v1)，(v2, v2)，(vq, vq)，其中v1, v2, , vq 是V2中的q個(gè)不同的結(jié)點(diǎn)，則稱(chēng)G的子圖G = 為從V1到V2的一個(gè)完全匹配(Complete Matching)，簡(jiǎn)稱(chēng)匹配。,2020/8/6,必要條件,在偶圖G = 中，若存在V1到V2的單射f，使得對(duì)任意vV1，都有(v, f(v)E，則存在V1到V2的匹配。 由單射的性質(zhì)知，不是所有

41、的偶圖都有匹配，存在匹配的必要條件是|V1| |V2|。 然而，這個(gè)條件并不是充分條件。,2020/8/6,例11.4.2,下面的3個(gè)偶圖哪些存在V1到V2匹配？對(duì)存在匹配的偶圖給出一個(gè)匹配。,不存在匹配,不存在匹配,存在匹配,2020/8/6,霍爾定理,定理11.4.2 (霍爾定理) 偶圖G = 中存在從V1到V2的匹配的充分必要條件是V1中任意k個(gè)結(jié)點(diǎn)至少與V2中的k個(gè)結(jié)點(diǎn)相鄰，k = 1, 2, , |V1|。 定理11.4.2中的條件通常稱(chēng)為相異性條件(Diversity Condition)。,2020/8/6,例,不滿(mǎn)足相異性條件，故沒(méi)有匹配。,滿(mǎn)足相異性條件，故存在匹配,2020

42、/8/6,定理11.4.3,設(shè)G = 是一個(gè)偶圖。如果滿(mǎn)足條件 （1）V1中每個(gè)結(jié)點(diǎn)至少關(guān)聯(lián)t條邊； （2）V2中每個(gè)結(jié)點(diǎn)至多關(guān)聯(lián)t條邊； 則G中存在從V1到V2的匹配。其中t為正整數(shù)。 該定理是偶圖G存在匹配的充分性條件。 優(yōu)點(diǎn)：計(jì)算量少。只需要判斷V1中結(jié)點(diǎn)的最小度數(shù)與V2中結(jié)點(diǎn)的最大度數(shù)即可。,2020/8/6,定理11.4.3證明,設(shè)G = 是一個(gè)偶圖。如果滿(mǎn)足條件 （1）V1中每個(gè)結(jié)點(diǎn)至少關(guān)聯(lián)t條邊； （2）V2中每個(gè)結(jié)點(diǎn)至多關(guān)聯(lián)t條邊； 則G中存在從V1到V2的匹配。其中t為正整數(shù)。 證明 由條件(1)知，V1中k個(gè)結(jié)點(diǎn)至少關(guān)聯(lián)tk條邊(1k|V1|)，由條件(2)知，這tk條邊至

43、少與V2中k個(gè)結(jié)點(diǎn)相關(guān)聯(lián)，于是V1中的k個(gè)結(jié)點(diǎn)至少與V2中的k個(gè)結(jié)點(diǎn)相鄰接，因而滿(mǎn)足相異性條件，所以G中存在從V1到V2的匹配。,2020/8/6,11.4.4 偶圖的難點(diǎn),判斷一個(gè)圖是否是偶圖已有充分必要條件，更重要的是，我們經(jīng)常使用其逆敘述來(lái)判斷一個(gè)圖不是偶圖； 匹配本質(zhì)上是一個(gè)單射； 判斷一個(gè)偶圖是否存在匹配的相異性條件通常比較復(fù)雜，通常在考察相異性條件之前，先判斷是否滿(mǎn)足t條件。,2020/8/6,11.4.5 偶圖的應(yīng)用,例11.4.3 有n臺(tái)計(jì)算機(jī)和n個(gè)磁盤(pán)驅(qū)動(dòng)器。每臺(tái)計(jì)算機(jī)與m0個(gè)磁盤(pán)驅(qū)動(dòng)器兼容，每個(gè)磁盤(pán)驅(qū)動(dòng)器與m臺(tái)計(jì)算機(jī)兼容。能否為每臺(tái)計(jì)算機(jī)配置一臺(tái)與它兼容的磁盤(pán)驅(qū)動(dòng)器？ 解

44、用V1表示n臺(tái)計(jì)算機(jī)的集合，V2表示n臺(tái)磁盤(pán)驅(qū)動(dòng)器的集合。以V1，V2為互補(bǔ)結(jié)點(diǎn)子集，以E = (vi, vj) | viV1, vjV2且vi與vj兼容為邊集，構(gòu)造偶圖。它顯然滿(mǎn)足t條件(t = m)，所以存在匹配，故能夠?yàn)槊颗_(tái)計(jì)算機(jī)配置一臺(tái)與它兼容的磁盤(pán)驅(qū)動(dòng)器。,2020/8/6,例11.4.4,現(xiàn)有三個(gè)課外小組：物理組，化學(xué)組和生物組，有五個(gè)學(xué)生s1,s2,s3,s4,s5。 （1）已知s1,s2為物理組成員；s1,s3,s4為化學(xué)組成員；s3,s4,s5為生物組成員。 （2）已知s1為物理組成員；s2,s3,s4為化學(xué)組成員；s2,s3,s4,s5為生物組成員。 （3）已知s1即為物理

45、組成員，又為化學(xué)組成員；s2,s3,s4,s5為生物組成員。 在以上三種情況的每一種情況下，在s1,s2,s3,s4, s5中選三位組長(zhǎng)，不兼職，問(wèn)能否辦到？,2020/8/6,例11.4.4 解,用c1,c2,c3分別表示物理組、化學(xué)組和生物組。 V1=c1,c2,c3，V2=s1,s2,s3,s4,s5 以V1，V2為互補(bǔ)結(jié)點(diǎn)子集，以E=(ci,sj)|ciV1, sjV2且ci中有成員sj為邊集，構(gòu)造偶圖。,不存在匹配,2020/8/6,11.5 平面圖,11.5.1 平面圖的定義 在一張紙上畫(huà)幾何模型時(shí)常常會(huì)發(fā)現(xiàn)，不僅需要允許各邊在結(jié)點(diǎn)處相交，而且還應(yīng)該允許各邊在某些非結(jié)點(diǎn)處相交，這樣

46、的點(diǎn)稱(chēng)為交叉點(diǎn)(Cross Point)；而相交的邊，稱(chēng)為交叉邊(Cross Edge)。,2020/8/6,定義11.5.1,如果能把一個(gè)無(wú)向圖G的所有結(jié)點(diǎn)和邊畫(huà)在平面上，使得任何兩邊除公共結(jié)點(diǎn)外沒(méi)有其他交叉點(diǎn)，則稱(chēng)G為平面圖(Plane Graph)，否則稱(chēng)G為非平面圖(Nonplanar Graph)。 當(dāng)且僅當(dāng)一個(gè)圖的每個(gè)連通分支都是平面圖時(shí)，這個(gè)圖是平面圖。,2020/8/6,非平面圖,有些圖形不論如何改畫(huà)，除去結(jié)點(diǎn)外，總有邊相交叉。 即不管怎樣改畫(huà)，至少有一條邊與其他邊相交叉，故它是非平面圖。,2020/8/6,11.5.2 觀察法,設(shè)G是畫(huà)于平面上的圖，并設(shè) C = v1v2v3

47、v4v1 是G中的任何基本回路。此外，設(shè)P1 = v1v3和P2 = v2v4是G中的任意兩條無(wú)公共結(jié)點(diǎn)的基本通路。,觀察法,2020/8/6,例11.5.1,用觀察法來(lái)判定圖K3,3為非平面圖。,2020/8/6,11.5.3 歐拉公式,定義11.5.2 在平面圖G的一個(gè)平面表示中， 由邊所包圍的其內(nèi)部不包含圖的結(jié)點(diǎn)和邊的區(qū)域，稱(chēng)為G的一個(gè)面(Surface)， 包圍該面的諸邊所構(gòu)成的回路稱(chēng)為這個(gè)面的邊界(Bound)， 面r的邊界的長(zhǎng)度稱(chēng)為該面的次數(shù)(Degree)，記為D(r)。 區(qū)域面積有限的面稱(chēng)為有限面(Finite Surface)，區(qū)域面積無(wú)限的面稱(chēng)為無(wú)限面(Infinite S

48、urface)。 平面圖有且僅有一個(gè)無(wú)限面。,2020/8/6,面的形象描述：,假設(shè)我們把一個(gè)平面圖的平面表示畫(huà)在平面上，然后用一把小刀，沿著圖的邊切開(kāi)，那么平面就被切成許多塊，每一塊就是圖的一個(gè)面。 更確切地說(shuō)，平面圖的一個(gè)面就是平面的一塊，它用邊作邊界線，且不能再分成子塊。,2020/8/6,例11.5.2,考察下圖所示平面圖的面、邊界和次數(shù)。,解 平面圖把平面分成4個(gè)面： r0，邊界為abdeheca，D(r0)=7 r1，邊界為abca，D(r1)=3 r2，邊界為becikijicb，D(r2)=9 r3，邊界為bdeb，D(r3)=3 r1、r2和r3是有限面，r0是無(wú)限面。,20

49、20/8/6,例11.5.2,注意：對(duì)于平面圖的不同平面表示，雖然面的數(shù)目相同，但各面的邊界和次數(shù)會(huì)不同。,2020/8/6,定理11.5.1,平面圖中所有面的次數(shù)之和等于邊數(shù)的二倍。 證明 因任何一條邊，或者是兩個(gè)面邊界的公共邊，或者是在一個(gè)面中作為邊界被重復(fù)計(jì)算兩次，故平面圖所有面的次數(shù)之和等于其邊數(shù)的二倍。 1750年，歐拉發(fā)現(xiàn)，任何一個(gè)凸多面體，若有n個(gè)頂點(diǎn)、m條棱和r個(gè)面，則有n-m+r = 2。這個(gè)公式可以推廣到平面圖上來(lái)，稱(chēng)之為歐拉公式。,2020/8/6,歐拉公式,定理11.5.2 設(shè)G = 是連通平面圖，若它有n個(gè)結(jié)點(diǎn)、m條邊和r個(gè)面，則有 n-m+r = 2 證明 我們對(duì)G

50、的邊數(shù)m進(jìn)行歸納。 若m = 0，由于G是連通圖，故必有n = 1，這時(shí)只有一個(gè)無(wú)限面，即r = 1。所以 n-m+r = 1-0+1 = 2 定理成立。,2020/8/6,定理11.5.2 證明（續(xù)）, 若m = 1，這時(shí)有兩種情況： （1）該邊是自回路，則有n=1，r=2，這時(shí) n - m + r = 1 1 + 2 = 2 （2）該邊不是自回路，則有n=2，r=1，這時(shí) n m + r = 2 1 + 1 = 2 所以m=1時(shí)，定理也成立。 假設(shè)對(duì)少于m條邊的所有連通平面圖，歐拉公式成立。 現(xiàn)考慮m條邊的連通平面圖，設(shè)它有n個(gè)結(jié)點(diǎn)。分以下兩種情況：,2020/8/6,定理11.5.2 證

51、明（續(xù)）,（1）若G是樹(shù)，那么m=n-1，這時(shí)r=1。所以 n-m+r = n-(n-1)+1 = 2 （2）若G不是樹(shù)，則G中必有回路，因此有基本回路，設(shè)e是某基本回路的一條邊，則G= 仍是連通平面圖，它有n個(gè)結(jié)點(diǎn)，m-1條邊和r-1個(gè)面，按歸納假設(shè)知 n-(m-1)+(r-1) = 2 整理得 n-m+r=2 所以對(duì)m條邊時(shí)，歐拉公式也成立。,2020/8/6,代入歐拉公式有2n-m+kn-m+2m/3 即2n-m/3 整理得m3n-6,推論11.5.1,設(shè)G是一個(gè)(n,m)簡(jiǎn)單連通平面圖，若m1，則有 m3n-6 證明 設(shè)G有k個(gè)面，因?yàn)镚是簡(jiǎn)單圖，所以G的每個(gè)面至少由3條邊圍成。所以G

52、所有面的次數(shù)之和,由定理11.5.1知，2m3k，即k2m/3，,平面圖中所有面的次數(shù)之和等于邊數(shù)的二倍,2020/8/6,說(shuō)明,推論11.5.1本身可能用處不大，但它的逆否命題卻非常有用，可以用它來(lái)判定某些圖是非平面圖。即 一個(gè)簡(jiǎn)單連通圖，若不滿(mǎn)足m3n-6，則一定是非平面圖。 但需要注意，滿(mǎn)足不等式m3n-6的簡(jiǎn)單連通圖未必是平面圖。,2020/8/6,例11.5.3,證明5個(gè)結(jié)點(diǎn)的完全圖K5是非平面圖。 分析 因?yàn)镵5是簡(jiǎn)單連通圖，我們可以驗(yàn)證m 3n-6不成立，因此它不是平面圖。 證明 因?yàn)镵5是簡(jiǎn)單連通圖，n=5，m=10，因此m3n-6=35-6=9，故不滿(mǎn)足m3n-6，因此它不是

53、平面圖。 再看圖K3,3，n=6，m=9，滿(mǎn)足不等式m3n-6，但是我們已用觀察法證明了它是一個(gè)非平面圖。,2020/8/6,推論11.5.2,設(shè)G是一個(gè)(n, m)簡(jiǎn)單連通平面圖，若每個(gè)面的次數(shù)至少為k(k3)，則有,證明 設(shè)G共有r個(gè)面，各面的次數(shù)之和為T(mén)， 由條件可知Tkr 又由定理11.5.1知T = 2m 利用歐拉公式解出面數(shù) r = 2-n+m 由此得出下式成立2mk(2-n+m) 從而有(k-2)m k(n-2) 由于k3，因而結(jié)論成立,2020/8/6,說(shuō)明,推論11.5.2本身可能用處不大，但它的逆否命題卻非常有用，可以用它來(lái)判定某些圖是非平面圖。即 一個(gè)簡(jiǎn)單連通圖，若每個(gè)面的次數(shù)至少為k(k3)，若不滿(mǎn)足 ，則一定是非平面圖。,2020/8/6,例11.5.4,不使用觀察法證明圖K3,3是一個(gè)非平面圖。 證明 利用推論11.5.2可以判斷。事實(shí)上，假設(shè)K3,3是一個(gè)平面圖，那么它的每個(gè)面的次數(shù)均不能小于