離散數(shù)學(xué)第7章 幾類特殊的圖

1、1Chapter 7 幾類特殊的圖幾類特殊的圖n本章討論幾類在理論研究和實(shí)際應(yīng)用中都有著重本章討論幾類在理論研究和實(shí)際應(yīng)用中都有著重要意義的特殊圖：要意義的特殊圖：nEuler圖圖;nHamilton圖圖;n平面圖。平面圖。27.1 Euler圖圖n1. Euler圖的有關(guān)概念圖的有關(guān)概念A(yù)BCDABCD3n定義定義 設(shè)設(shè)G = (V, E)是任意圖是任意圖, G中經(jīng)過所有邊一次中經(jīng)過所有邊一次且僅一次的路稱為且僅一次的路稱為Euler軌跡軌跡;n G中經(jīng)過所有邊一次且僅一次的回路稱為中經(jīng)過所有邊一次且僅一次的回路稱為Euler回回路路;n存在存在Euler回路的圖稱為回路的圖稱為Euler圖

2、圖或簡稱為或簡稱為E圖圖. nEuler回路回路Euler軌跡軌跡, 但反過來一般不成立但反過來一般不成立.abcde歐拉軌跡：歐拉軌跡：(a, c, d, e, b, d, a, b)歐拉回路歐拉回路 ? ?deabcdeabc無無 歐拉回路：歐拉回路：(a, e, c, d, e, b, a, )無歐拉軌跡；無歐拉回路無歐拉軌跡；無歐拉回路42. Euler定理定理nTheorem 設(shè)設(shè)G是連通無向圖是連通無向圖, 則則G是是Euler圖的充要圖的充要條件是條件是G的每節(jié)點(diǎn)度數(shù)為偶數(shù)的每節(jié)點(diǎn)度數(shù)為偶數(shù).證：必要性顯然。證：必要性顯然。充分性：充分性： 設(shè)設(shè)G的所有結(jié)點(diǎn)都是偶結(jié)點(diǎn)，來構(gòu)造一條

3、歐拉回的所有結(jié)點(diǎn)都是偶結(jié)點(diǎn)，來構(gòu)造一條歐拉回路。路。從從G的任一結(jié)點(diǎn)的任一結(jié)點(diǎn)v v0 0開始，必可沿著某一邊到另一結(jié)點(diǎn)開始，必可沿著某一邊到另一結(jié)點(diǎn)v v1 1。v v1 1為偶結(jié)點(diǎn)，可沿著沒有走過的邊至為偶結(jié)點(diǎn)，可沿著沒有走過的邊至v v2 2每個(gè)結(jié)點(diǎn)均為偶結(jié)點(diǎn)，這個(gè)過程必以回到每個(gè)結(jié)點(diǎn)均為偶結(jié)點(diǎn)，這個(gè)過程必以回到v v0 0告終。告終。則得到一條簡單回路則得到一條簡單回路C1，如經(jīng)過了，如經(jīng)過了G所有邊，則為歐拉回路。所有邊，則為歐拉回路。否則，否則，C1沒有經(jīng)過的邊中至少有一條與沒有經(jīng)過的邊中至少有一條與C1的某個(gè)結(jié)點(diǎn)的某個(gè)結(jié)點(diǎn)關(guān)聯(lián)（否則關(guān)聯(lián)（否則G不連通）。不連通）。設(shè)此結(jié)點(diǎn)為設(shè)此結(jié)

4、點(diǎn)為v vk k, ,從它出發(fā)，沿著從它出發(fā)，沿著C1沒有走過的邊走，與上述同法，沒有走過的邊走，與上述同法，必回到必回到v vk k ，構(gòu)成簡單回路，構(gòu)成簡單回路C2，加到，加到C1中得到更大簡單回路。中得到更大簡單回路。重復(fù)這個(gè)過程，由于邊數(shù)有限，最后得到一條重復(fù)這個(gè)過程，由于邊數(shù)有限，最后得到一條Euler回路?；芈?。5n根據(jù)根據(jù)Euler定理容易得出定理容易得出nTheorem 設(shè)設(shè)G是連通無向圖是連通無向圖, 則則G不是不是Euler圖但圖但存在存在Euler軌跡軌跡 G有有2個(gè)度數(shù)為奇數(shù)的節(jié)點(diǎn)個(gè)度數(shù)為奇數(shù)的節(jié)點(diǎn).n根據(jù)定理根據(jù)定理,“七橋問題七橋問題”無解無解, 甚至不存在甚至不存

5、在Euler軌跡軌跡.設(shè)設(shè)G中僅有奇結(jié)點(diǎn)中僅有奇結(jié)點(diǎn)v1 ，v2，在它們之間添一條邊，所得圖記為，在它們之間添一條邊，所得圖記為G。G有連接有連接v1 ，v2的歐拉路的歐拉路 G有一條歐拉回路有一條歐拉回路G所有結(jié)點(diǎn)為偶結(jié)點(diǎn)所有結(jié)點(diǎn)為偶結(jié)點(diǎn)G的所有結(jié)點(diǎn)除了的所有結(jié)點(diǎn)除了v1 ，v2奇結(jié)點(diǎn)外，其余全為偶結(jié)點(diǎn)。奇結(jié)點(diǎn)外，其余全為偶結(jié)點(diǎn)。ABCD6abcdefabcde 下右圖不是歐拉圖，但恰有兩個(gè)奇結(jié)點(diǎn)，有一下右圖不是歐拉圖，但恰有兩個(gè)奇結(jié)點(diǎn)，有一條歐拉軌跡條歐拉軌跡( (bcdeabe).). 在下左圖中在下左圖中, ,所有結(jié)點(diǎn)均為偶結(jié)點(diǎn)所有結(jié)點(diǎn)均為偶結(jié)點(diǎn), ,故為歐拉圖故為歐拉圖. . 一條歐

6、拉回路為：一條歐拉回路為：( (abcdefcebfa).). 7 我國民間很早就流傳一種我國民間很早就流傳一種“一筆畫一筆畫”游戲游戲, ,即筆不離紙即筆不離紙, ,邊邊不重復(fù)不重復(fù), ,畫完該圖畫完該圖. .根據(jù)上述定理知根據(jù)上述定理知, ,有兩種情況可以一筆畫：有兩種情況可以一筆畫： (1) (1) 如果圖中所有結(jié)點(diǎn)都是偶結(jié)點(diǎn)如果圖中所有結(jié)點(diǎn)都是偶結(jié)點(diǎn), ,則可以任選一個(gè)結(jié)點(diǎn)作則可以任選一個(gè)結(jié)點(diǎn)作為起始點(diǎn)一筆畫完；為起始點(diǎn)一筆畫完； (2) 2) 如果圖中恰有兩個(gè)奇結(jié)點(diǎn)如果圖中恰有兩個(gè)奇結(jié)點(diǎn), ,則可以選一個(gè)奇結(jié)點(diǎn)作為起則可以選一個(gè)奇結(jié)點(diǎn)作為起始點(diǎn)一筆畫完始點(diǎn)一筆畫完, ,并終止于另一個(gè)

7、奇結(jié)點(diǎn)并終止于另一個(gè)奇結(jié)點(diǎn). . 例例 如下圖是某街道圖形如下圖是某街道圖形. .灑水車從灑水車從A點(diǎn)出發(fā)執(zhí)行灑水任務(wù)點(diǎn)出發(fā)執(zhí)行灑水任務(wù). .試問是否存在一條灑水路線試問是否存在一條灑水路線, ,使灑水車通過所有街道且不重使灑水車通過所有街道且不重復(fù)而最后回到車庫復(fù)而最后回到車庫B？ ABCDFEG解解 此問題即為求證圖中是否存在此問題即為求證圖中是否存在A到到B的歐拉軌跡的歐拉軌跡. .由于圖中只有由于圖中只有A, ,B為為奇結(jié)點(diǎn)奇結(jié)點(diǎn), ,因此這樣的灑水線路是存在因此這樣的灑水線路是存在的的, ,例如例如, ,ACDEFBGCFGAB或或AGFEDCFBGCAB, ,等等等等. . 8 從

8、歐拉回路和歐拉軌跡的定義可知從歐拉回路和歐拉軌跡的定義可知, ,圖中的歐拉回路圖中的歐拉回路( (歐歐拉軌跡拉軌跡) )是經(jīng)過圖中所有邊的最短回路是經(jīng)過圖中所有邊的最短回路( (軌跡軌跡). ). 例例（螞蟻比賽問題）如下圖（螞蟻比賽問題）如下圖, ,甲、乙兩只螞蟻分別位于結(jié)點(diǎn)甲、乙兩只螞蟻分別位于結(jié)點(diǎn)a, ,b處處, ,并設(shè)圖中的邊長度相等并設(shè)圖中的邊長度相等. .甲、乙進(jìn)行比賽：從它們所甲、乙進(jìn)行比賽：從它們所在的結(jié)點(diǎn)出發(fā)在的結(jié)點(diǎn)出發(fā), ,走過圖中的所有邊最后到達(dá)結(jié)點(diǎn)走過圖中的所有邊最后到達(dá)結(jié)點(diǎn)e處處. .如果他如果他們的速度相同們的速度相同, ,問誰先到達(dá)目的地？問誰先到達(dá)目的地？ bc

9、dae解解 在圖中在圖中, ,僅有兩個(gè)奇結(jié)點(diǎn)僅有兩個(gè)奇結(jié)點(diǎn)b, ,e, ,因而因而存在從存在從b到到e的歐拉軌跡的歐拉軌跡, ,螞蟻乙走到螞蟻乙走到e只要走一條歐拉軌跡只要走一條歐拉軌跡, ,邊數(shù)為邊數(shù)為9 9條；而條；而螞蟻甲要想走完所有的邊到達(dá)螞蟻甲要想走完所有的邊到達(dá)e, ,至少至少要先走一條邊到達(dá)要先走一條邊到達(dá)b, ,再走一條歐拉軌再走一條歐拉軌跡跡, ,因而它至少要走因而它至少要走1010條邊才能到達(dá)條邊才能到達(dá)e, ,所以乙必勝所以乙必勝. . 91v2v3v4v5vvvvvvvvvv是歐拉圖是歐拉圖10對于有向圖：對于有向圖：nTheorem 設(shè)設(shè)G是

10、弱連通有向圖是弱連通有向圖, 則則G是是Euler圖圖的充要條件是的充要條件是G的每節(jié)點(diǎn)的入度等于其出度的每節(jié)點(diǎn)的入度等于其出度.nTheorem 設(shè)設(shè)G是弱連通有向圖是弱連通有向圖, 則則G中存在中存在Euler軌跡的充要條件是軌跡的充要條件是 (1) G的每節(jié)點(diǎn)的入度等于其出度的每節(jié)點(diǎn)的入度等于其出度, 或者或者 (2) G中存在一個(gè)節(jié)點(diǎn)出度比入度多中存在一個(gè)節(jié)點(diǎn)出度比入度多1,存在一個(gè)節(jié)存在一個(gè)節(jié)點(diǎn)入度比出度多點(diǎn)入度比出度多1,而其余所有節(jié)點(diǎn)的入度等于其而其余所有節(jié)點(diǎn)的入度等于其出度出度.作業(yè)作業(yè) P185 習(xí)題習(xí)題7.1 2，5117.2 Hamilton 圖圖 所謂哈密爾頓圖所謂哈密

11、爾頓圖,起源于一個(gè)名叫起源于一個(gè)名叫“周游世界周游世界”的游戲的游戲, 它是由英國它是由英國數(shù)學(xué)家哈密爾頓數(shù)學(xué)家哈密爾頓(Hamilton)于于1859年提出的年提出的.他用一個(gè)正十二面體的他用一個(gè)正十二面體的20個(gè)頂點(diǎn)代表個(gè)頂點(diǎn)代表20個(gè)大城市個(gè)大城市(見下左圖見下左圖), 這個(gè)正十二面體同構(gòu)于一個(gè)平面圖這個(gè)正十二面體同構(gòu)于一個(gè)平面圖(見下右圖見下右圖).要求沿著正十二面體的棱要求沿著正十二面體的棱, 從一個(gè)城市出發(fā)從一個(gè)城市出發(fā), 經(jīng)過每個(gè)城市經(jīng)過每個(gè)城市恰好一次恰好一次, 然后回到出發(fā)點(diǎn)然后回到出發(fā)點(diǎn). 這個(gè)游戲曾風(fēng)靡一時(shí)這個(gè)游戲曾風(fēng)靡一時(shí), 它有若干個(gè)解它有若干個(gè)解.下頁下頁給出了一個(gè)

12、解給出了一個(gè)解. 12131.Hamilton 圖的有關(guān)概念圖的有關(guān)概念n定義定義 設(shè)設(shè)G = (V, E)是任意圖是任意圖, G中經(jīng)過所有節(jié)點(diǎn)一中經(jīng)過所有節(jié)點(diǎn)一次且僅一次的路徑稱為次且僅一次的路徑稱為H路徑路徑; nG中經(jīng)過所有節(jié)點(diǎn)一次且僅一次中經(jīng)過所有節(jié)點(diǎn)一次且僅一次(除起點(diǎn)重復(fù)一次除起點(diǎn)重復(fù)一次外外)的圈稱為的圈稱為H回路回路;n存在存在H回路的圖稱為回路的圖稱為Hamilton圖圖或簡稱為或簡稱為H圖圖. n由由H回路可得到回路可得到H路徑路徑, 不返回出發(fā)點(diǎn)即可不返回出發(fā)點(diǎn)即可, 但反但反過來一般不成立過來一般不成立.14下列圖中是否有下列圖中是否有H路徑或路徑或H回路？回路？abc

13、deabcdabcdefg回路回路: abcdea路徑路徑: abcdabced無回路無回路Kn 必有必有H回路回路 （n3） 因?yàn)槿我鈨牲c(diǎn)之間都有邊連接因?yàn)槿我鈨牲c(diǎn)之間都有邊連接. .無路徑無路徑15n到目前為止還沒有一種方法可以有效地解決到目前為止還沒有一種方法可以有效地解決Hamilton 圖的判斷問題圖的判斷問題, 這是一個(gè)計(jì)算機(jī)科學(xué)中這是一個(gè)計(jì)算機(jī)科學(xué)中的一個(gè)的一個(gè)NP難問題難問題.n下面分別介紹下面分別介紹Hamilton 圖的必要條件和圖的必要條件和Hamilton 圖的充分條件圖的充分條件.162. Hamilton 圖的必要條件圖的必要條件nTheorem 設(shè)設(shè)G = (V,

14、 E)是是Hamilton無向圖無向圖, 則對于則對于任意任意 W V, 均有均有w(G -W) |W|.利用該定理可判別某些圖不是哈密爾頓圖利用該定理可判別某些圖不是哈密爾頓圖. .v1v2173. Hamilton 圖的充分條件圖的充分條件nTheorem 設(shè)設(shè)G = (V, E)是是n(n 3)階簡單無向圖階簡單無向圖, 若對于任意的不相鄰節(jié)點(diǎn)若對于任意的不相鄰節(jié)點(diǎn)u, v V, 有有deg(u) + deg(v) n, 則則G是是Hamilton圖圖.nTheorem 設(shè)設(shè)G = (V, E)是是n(n 3)階簡單無向圖階簡單無向圖, 若對于任意的不相鄰節(jié)點(diǎn)若對于任意的不相鄰節(jié)點(diǎn)u,

15、v V, 有有deg(u) + deg(v) n-1, 則則G中存在中存在Hamilton路徑路徑.18例例 某地有某地有5 5個(gè)風(fēng)景點(diǎn)個(gè)風(fēng)景點(diǎn), ,若每個(gè)風(fēng)景點(diǎn)均有兩條路與其它風(fēng)景點(diǎn)若每個(gè)風(fēng)景點(diǎn)均有兩條路與其它風(fēng)景點(diǎn)相通相通. .問游人可否經(jīng)過每個(gè)風(fēng)景點(diǎn)恰好一次而游完這問游人可否經(jīng)過每個(gè)風(fēng)景點(diǎn)恰好一次而游完這5 5個(gè)風(fēng)景點(diǎn)？個(gè)風(fēng)景點(diǎn)？ 解解 我們將風(fēng)景點(diǎn)看成結(jié)點(diǎn)我們將風(fēng)景點(diǎn)看成結(jié)點(diǎn), ,道路看成邊構(gòu)成無向簡單圖道路看成邊構(gòu)成無向簡單圖, ,這樣這樣每個(gè)結(jié)點(diǎn)的度數(shù)為每個(gè)結(jié)點(diǎn)的度數(shù)為2,2,因此每對結(jié)點(diǎn)的度數(shù)之和等于因此每對結(jié)點(diǎn)的度數(shù)之和等于4,4,正好為結(jié)正好為結(jié)點(diǎn)數(shù)減點(diǎn)數(shù)減1,1,由定理可知

16、由定理可知, ,圖中存在一條哈密爾頓路徑圖中存在一條哈密爾頓路徑, ,因此本題有因此本題有解解. . 需要注意的是需要注意的是, ,定理給出的是充分條件而不是必要條件定理給出的是充分條件而不是必要條件. .例例如如, ,在六邊形中在六邊形中, ,任兩個(gè)結(jié)點(diǎn)的度數(shù)和等于任兩個(gè)結(jié)點(diǎn)的度數(shù)和等于4,4,小于小于6,6,但六邊形是但六邊形是哈密爾頓圖哈密爾頓圖. . 作業(yè)作業(yè) P189 習(xí)題習(xí)題7. 2 5197.5 平面圖平面圖 n本節(jié)僅討論無向圖本節(jié)僅討論無向圖.n有些實(shí)際問題要求把圖畫在一個(gè)平面上，同時(shí)使有些實(shí)際問題要求把圖畫在一個(gè)平面上，同時(shí)使 得圖的邊僅僅在節(jié)點(diǎn)處才相交得圖的邊僅僅在節(jié)點(diǎn)處才

17、相交. 例如單層印刷電路例如單層印刷電路版、集成電路的布線等問題就需要滿足上面的要求版、集成電路的布線等問題就需要滿足上面的要求.20n1.平面圖的有關(guān)概念平面圖的有關(guān)概念n定義：定義： 設(shè)設(shè)G是無向圖是無向圖,若可將若可將G畫在一個(gè)平面上畫在一個(gè)平面上,同同時(shí)使得任意兩條邊僅僅在節(jié)點(diǎn)處才相交時(shí)使得任意兩條邊僅僅在節(jié)點(diǎn)處才相交,則稱則稱G是是可平面圖可平面圖(planar graph)或簡稱或簡稱G為為平面圖平面圖(plane graph).n設(shè)設(shè)G是平面圖是平面圖,則可在一個(gè)平面上將圖則可在一個(gè)平面上將圖G畫出來且畫出來且使得其任意兩條邊僅僅在節(jié)點(diǎn)處才相交使得其任意兩條邊僅僅在節(jié)點(diǎn)處才相交,

18、這樣畫出這樣畫出的圖稱為平面圖的圖稱為平面圖G的的平面嵌入平面嵌入(embedding)或或平面平面表示表示. n由于一個(gè)平面圖與其平面表示是同構(gòu)的由于一個(gè)平面圖與其平面表示是同構(gòu)的, 因此平面因此平面圖通常是指其平面表示圖通常是指其平面表示.21:4K如如完完全全圖圖 在同構(gòu)的意義下，這兩張圖并沒有實(shí)質(zhì)上的在同構(gòu)的意義下，這兩張圖并沒有實(shí)質(zhì)上的區(qū)別，但右圖的畫法，避免了邊的交叉。區(qū)別，但右圖的畫法，避免了邊的交叉。221. 1. 鐵路互不交叉能否實(shí)現(xiàn)鐵路互不交叉能否實(shí)現(xiàn) K3,3把把工工廠廠和和采采礦礦點(diǎn)點(diǎn)看看成成結(jié)結(jié)點(diǎn)點(diǎn)，鐵鐵路路看看成成邊邊，則則得得到到。 有三個(gè)工廠和三個(gè)采礦點(diǎn)，想要從

19、每一個(gè)工有三個(gè)工廠和三個(gè)采礦點(diǎn)，想要從每一個(gè)工廠到每一個(gè)采礦點(diǎn)各修一條專用鐵路，這些鐵路廠到每一個(gè)采礦點(diǎn)各修一條專用鐵路，這些鐵路互不交叉能否實(shí)現(xiàn)？互不交叉能否實(shí)現(xiàn)？23n 二部圖二部圖：V劃分為劃分為V1和和V2, 任意邊關(guān)聯(lián)的兩個(gè)節(jié)點(diǎn)任意邊關(guān)聯(lián)的兩個(gè)節(jié)點(diǎn)中一個(gè)在中一個(gè)在V1中中, 一個(gè)在一個(gè)在V2中中.n完全二部圖完全二部圖： V1中的所有節(jié)點(diǎn)與中的所有節(jié)點(diǎn)與V2的所有節(jié)點(diǎn)都的所有節(jié)點(diǎn)都鄰接的二部圖，記為鄰接的二部圖，記為Km, n 1v2v3v4v5v6v7v8v4, 3K24 從上圖可以看出，無論怎么畫，交叉似乎是從上圖可以看出，無論怎么畫，交叉似乎是不可避免的。不可避免的。252.

20、2. 土地分割問題土地分割問題 K5如如果果把把每每塊塊土土地地看看成成一一個(gè)個(gè)結(jié)結(jié)點(diǎn)點(diǎn)，相相鄰鄰的的土土地地用用一一條條邊邊相相連連，則則地地主主的的愿愿望望就就是是構(gòu)構(gòu)成成一一個(gè)個(gè)五五階階完完全全圖圖。 MobiusK5可可以以證證明明：任任何何實(shí)實(shí)際際地地圖圖構(gòu)構(gòu)成成的的圖圖，邊邊之之間間是是不不可可能能發(fā)發(fā)生生交交叉叉的的。因因此此，的的問問題題變變?yōu)闉椋捍娲嬖谠谶呥厸]沒有有交交叉叉的的畫畫法法嗎嗎？ 大約大約9090年前，德國數(shù)學(xué)家年前，德國數(shù)學(xué)家A.F.Mbius提出了提出了這樣一個(gè)問題：有一個(gè)地主，打算在生前把他的這樣一個(gè)問題：有一個(gè)地主，打算在生前把他的土地分成五塊，要求每塊土

21、地與另外四塊都相鄰。土地分成五塊，要求每塊土地與另外四塊都相鄰。他的愿望能實(shí)現(xiàn)嗎？他的愿望能實(shí)現(xiàn)嗎？2627是是平平面面圖圖嗎嗎？和和結(jié)結(jié)為為：現(xiàn)現(xiàn)在在，上上述述兩兩個(gè)個(gè)問問題題歸歸53, 3 KK 回答是：回答是：No。為了證明這個(gè)結(jié)論，我們要用。為了證明這個(gè)結(jié)論，我們要用到一個(gè)重要的公式到一個(gè)重要的公式歐拉公式。歐拉公式。28n定義定義： 設(shè)設(shè)G是平面圖是平面圖,由由G的若干條邊所圍成的連的若干條邊所圍成的連通區(qū)域稱為圖通區(qū)域稱為圖G的的面面(face),圍成面的圍成面的(回路所在的回路所在的)邊稱為面的邊稱為面的邊界邊界(boundary).n特別注意特別注意,任何平面圖都有一個(gè)由若干條

22、邊往外圍任何平面圖都有一個(gè)由若干條邊往外圍成的一個(gè)面成的一個(gè)面,它是唯一的一個(gè)無限面它是唯一的一個(gè)無限面.n定義定義 平面圖的一個(gè)面的邊界所含的邊數(shù)稱為該平面圖的一個(gè)面的邊界所含的邊數(shù)稱為該面面的度數(shù)的度數(shù),記為記為 deg(R).R4 R3 R2 R1d(R1)=3 d(R2)=3d(R3)=3 d(R4)=329aR2fedbcR1R3g定理定理 在一個(gè)平面圖中在一個(gè)平面圖中, ,所有面的度數(shù)之和等于邊所有面的度數(shù)之和等于邊數(shù)的兩倍數(shù)的兩倍: : d(Ri)=2|E|.d(R1)=3, , d(R2)=6, , d(R3)=7, , d(Ri)= 16, |E|=8 .n平面圖的兩個(gè)面相鄰

23、是指這兩個(gè)面有公共的邊界平面圖的兩個(gè)面相鄰是指這兩個(gè)面有公共的邊界.30F2F1F3afedbcghiF4例例d(F1)=3, , d(F2)=4, , d(F3)=3, , d(F4)=10, , d(Fi)=20, |E|=10 .31n2.Euler公式公式nTheorem (Euler公式) 任意任意(n, m)連通平面圖的面連通平面圖的面數(shù)數(shù) r = m n +2, 即即 n m + r = 2。n證：對邊數(shù)證：對邊數(shù)m進(jìn)行歸納：進(jìn)行歸納：n1） m =1時(shí)，僅有兩種類型連通平面圖，時(shí)，僅有兩種類型連通平面圖，n n=2, r=1或或 n=1, r=2，均滿足公式。，均滿足公式。n2

24、）設(shè)對）設(shè)對m -1條邊公式成立，現(xiàn)考慮條邊公式成立，現(xiàn)考慮m條邊的連通平面圖條邊的連通平面圖G，若若G是樹，那么是樹，那么m =n-1，而此時(shí)，而此時(shí)r=1,成立，成立，若若G不是樹，則不是樹，則G中至少存在一個(gè)圈中至少存在一個(gè)圈c，設(shè)，設(shè)j是是c的一條邊，的一條邊， 令令G=G-j，則，則G也是連通平面圖，且有也是連通平面圖，且有n個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn), m -1條邊和條邊和r-1個(gè)面，由歸納假設(shè)個(gè)面，由歸納假設(shè) n-(m -1)+(r-1)=2,即即n- m +r=2， 故公式對故公式對m條邊也成立，條邊也成立， 由歸納法可知，公式成立。由歸納法可知，公式成立。 32例例 設(shè)連通平面圖除無限面是

25、四邊形外設(shè)連通平面圖除無限面是四邊形外, , 其余面其余面全為三角形全為三角形, , 結(jié)點(diǎn)數(shù)為結(jié)點(diǎn)數(shù)為 n = 50, 求邊數(shù)求邊數(shù)m和面數(shù)和面數(shù)k.解解 由前述定理和歐拉公式，有由前述定理和歐拉公式，有 25013) 1( 34)deg(21kmkkFmkii.14395 mk33定理定理 若連通平面圖的每個(gè)面的度數(shù)至少為若連通平面圖的每個(gè)面的度數(shù)至少為k，則則.2)2( knkm證證 設(shè)設(shè)G有有r個(gè)面，則由定理可得個(gè)面，則由定理可得 iirkFdm )(2再由歐拉公式，得再由歐拉公式，得rmn 2.2)2( knk m.2 kmr kmknkmmn)2(2 34m = 10, n = 53

26、n - 6 = 9m 3n - 6K5 不是平面圖不是平面圖K5是否平面圖是否平面圖?.2)2( knk mCorollary 1 任意任意(n, m)簡單平面圖簡單平面圖, 若若n 3, 則則m 3n - 6.35nTheorem 任何簡單平面圖必存在一個(gè)度數(shù)任何簡單平面圖必存在一個(gè)度數(shù) 5 的的節(jié)點(diǎn)節(jié)點(diǎn).nProof 不妨設(shè)不妨設(shè)n 3. 假設(shè)假設(shè) v V, deg(v) 6. ).63(22)deg(6 nmvnVv矛盾！矛盾！,120 36m = 9, n = 6, 無長度為無長度為3的回路，的回路，2n - 4 = 8m 2n - 4K3,3不是平面圖不是平面圖nCorollary 2 任意任意