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

1、1Chapter 7 幾類特殊的圖幾類特殊的圖n本章討論幾類在理論研究和實際應用中都有著重本章討論幾類在理論研究和實際應用中都有著重要意義的特殊圖：要意義的特殊圖：nEuler圖圖;nHamilton圖圖;n平面圖。平面圖。27.1 Euler圖圖n1. Euler圖的有關概念圖的有關概念ABCDABCD3n定義定義 設設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 設設G是連通無向圖是連通無向圖, 則則G是是Euler圖的充要圖的充要條件是條件是G的每節(jié)點度數(shù)為偶數(shù)的每節(jié)點度數(shù)為偶數(shù).證：必要性顯然。證：必要性顯然。充分性：充分性： 設設G的所有結(jié)點都是偶結(jié)點，來構(gòu)造一條

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

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

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

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

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

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

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

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

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

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

13、eabcdabcdefg回路回路: abcdea路徑路徑: abcdabced無回路無回路Kn 必有必有H回路回路 （n3） 因為任意兩點之間都有邊連接因為任意兩點之間都有邊連接. .無路徑無路徑15n到目前為止還沒有一種方法可以有效地解決到目前為止還沒有一種方法可以有效地解決Hamilton 圖的判斷問題圖的判斷問題, 這是一個計算機科學中這是一個計算機科學中的一個的一個NP難問題難問題.n下面分別介紹下面分別介紹Hamilton 圖的必要條件和圖的必要條件和Hamilton 圖的充分條件圖的充分條件.162. Hamilton 圖的必要條件圖的必要條件nTheorem 設設G = (V,

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

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

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

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

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

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

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

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

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

23、指這兩個面有公共的邊界平面圖的兩個面相鄰是指這兩個面有公共的邊界.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進行歸納：進行歸納：n1） m =1時，僅有兩種類型連通平面圖，時，僅有兩種類型連通平面圖，n n=2, r=1或或 n=1, r=2，均滿足公式。，均滿足公式。n2）

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

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

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