離散數學 7-4 歐拉圖和漢

1、7-4歐拉圖和漢密爾頓圖,要求：1、理解歐拉圖、漢密爾頓圖的定義。2、掌握歐拉圖的判定方法。3、會判斷一些圖不是漢密爾頓圖。4、熟悉一些歐拉圖和漢密爾頓圖。,一、歐拉圖1、哥尼斯堡七橋問題,近代圖論的歷史可追溯到18世紀的七橋問題穿過哥尼斯堡城的七座橋，要求每座橋通過一次且僅通過一次。,七橋問題等價于在圖中求一條回路，此回路經過每條邊一次且僅有一次。歐拉在1736年的論文中提出了一條簡單的準則，確定了哥尼斯堡七橋問題是不能解的。,2、歐拉圖(Euler),如果無孤立結點圖G上有一條經過G的所有邊一次且僅一次的路徑，則稱該路徑為圖G的歐拉路徑（Eulerwalk）。如果圖G上有一條經過G邊一次且

2、僅一次的的回路，則稱該回路為圖G的歐拉回路。具有歐拉回路的圖稱為歐拉圖（Eulergraph）。,定理7-4.1無向圖G具有一條歐拉路，當且僅當G連通，并且有零個或兩個奇數度結點。,證明思路：1)先證必要性:G有歐拉路G連通且（有0個或2個奇數度結點）設G的歐拉路是點邊序列v0e1v1e2ekvk，其中結點可能重復，但邊不重復。因歐拉路經過（所有邊）所有結點，所以圖G是連通的。對于任一非端點結點vi，在歐拉路中每當vi出現一次，必關聯兩條邊，故vi雖可重復出現，但是deg(vi)必是偶數。對于端點,若v0=vk，則deg(v0)必是偶數，即G中無奇數度結點。若v0vk，則deg(v0)必是奇數

3、，deg(vk)必是奇數,即G中有兩個奇數度結點。必要性證完。,2)再證充分性:(證明過程給出了一種構造方法)G連通且（有0個或2個奇數度結點）G有歐拉路(1)若有2個奇數度結點,則從其中一個結點開始構造一條跡,即從v0出發(fā)經關聯邊e1進入v1,若deg(v1)為偶數,則必可由v1再經關聯邊e2進入v2,如此下去,每邊僅取一次,由于G是連通的,故必可到達另一奇數度結點停下,得到一條跡L1:v0e1v1e2ekvk。若G中沒有奇數度結點,則從任一結點v0出發(fā),用上述方法必可回到結點v0,得到一條閉跡。(2)若L1通過了G的所有邊,L1就是一條歐拉路。(3)若G中去掉L1后得到子圖G,則G中每個結

4、點度數都為偶數,因為原來的圖G是連通的,故L1與G至少有一個結點vi重合,在G中由vi出發(fā)重復(1)的方法,得到閉跡L2。(4)當L1與L2組合,若恰是G,得歐拉路,否則重復(3),可得閉跡L3,依此類推可得一條歐拉路。充分性證完,由于有了歐拉路和歐拉回路的判別準則，因此哥尼斯堡七橋問題立即有了確切的否定答案，因為從圖中可以看到deg(A)5，deg(B)deg(C)deg(D)=3，故歐拉回路必不存在。,定理7-4.1的推論無向圖G具有一條歐拉回路，當且僅當G連通且所有結點度數皆為偶數。,4、一筆畫問題要判定一個圖G是否可一筆畫出，有兩種情況：一是從圖G中某一結點出發(fā)，經過圖G的每一邊一次僅

5、一次到達另一結點。另一種就是從G的某個結點出發(fā)，經過G的每一邊一次僅一次再回到該結點。,v1,v2,v3,v4,v5,為歐拉路，有從v2到v3的一筆畫。為歐拉回路，可以從任一結點出發(fā)，一筆畫回到原出發(fā)點。,5.定義7-4.2：給定有向圖G，通過圖中每邊一次且僅一次的一條單向路（回路），稱作單向歐拉路（回路）。,可以將歐拉路和歐拉回路的概念推廣到有向圖中。,6.定理7-4.2(1)有向圖G為具有一條單向歐拉回路，當且僅當G連通，并且每個結點的入度等于出度。(2)有向圖G有單向歐拉路，當且僅當G連通，并且恰有兩個結點的入度與出度不等，它們中一個的出度比入度多1，另一個入度比出度多1。證明思路與定理

6、7-4.1類似,例1有向歐拉圖應用示例：計算機鼓輪的設計。鼓輪表面分成24=16等份，其中每一部分分別用絕緣體或導體組成，絕緣體部分給出信號0，導體部分給出信號1，在下圖中陰影部分表示導體，空白體部分表示絕緣體，根據鼓輪的位置，觸點將得到信息4個觸點a,b,c,d讀出1101(狀態(tài)圖中的邊e13),轉一角度后將讀出1010(邊e10)。問鼓輪上16個部分怎樣安排導體及絕緣體才能使鼓輪每旋轉一個部分，四個觸點能得到一組不同的四位二進制數信息。,0,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,1,1,1,0,a,b,c,d,設有一個八個結點的有向圖，如下圖所示。其結點分別記為三位二

7、進制數000，001，111，設ai0,1，從結點a1a2a3可引出兩條有向邊，其終點分別是a2a30以及a2a31。該兩條邊分別記為a1a2a30和a1a2a31。按照上述方法，對于八個結點的有向圖共有16條邊，在這種圖的任一條路中，其鄰接的邊必是a1a2a3a4和a2a3a4a5的形式，即是第一條邊標號的后三位數與第二條邊的頭三位數相同。由于圖中16條邊被記為不同的二進制數，可見前述鼓輪轉動所得到16個不同位置觸點上的二進制信息，即對應于圖中的一條歐拉回路。,010,101,110,100,011,001,111,000,e10=1010,e13=1101,e5=0101,e3=0011,

8、e11=1011,e6=0110,e7=0111,e14=1110,e15=1111,e12=1100,e2=0010,e4=0100,e1=0001,e8=1000,e9=1001,e0=0000,a1a2a3(=000)0,a1a2a3(=000)1,a1a2a3(=001)1,a1a2a3(=100)0,a1a2a3(=111)0,a1a2a3(=111)1,a1a2a3(=110)0,a1a2a3(=011)1,所求的歐拉回路為：e0e1e2e4e9e3e6e13e10e5e11e7e16e14e12e8(e0)（從圖示位置開始）e13e10e5e11e7e16e14e12e8e0e1

9、e2e4e9e3e6(e13)所求的二進制序列為：0000100110101111(0)1101011110000100(1)（從圖示位置開始）,上述結論可推廣到鼓輪具有n個觸點的情況。構造2n-1個結點的有向圖，每個結點標記為n-1位二進制數,從結點a1a2a3.an-1出發(fā),有一條終點為a2a3.an-10的邊,該邊記為a1a2a3.an-10；還有一條終點標記為a2a3.an-11的邊,該邊記為a1a2a3.an-11。鄰接邊的標記規(guī)則為：“第一條邊后n-1位與第二條邊前n-1位二進制數相同”。哈密爾頓回路問題見圖7-4.6。,二、漢密爾頓圖,與歐拉回路類似的是漢密爾頓回路。它是1859

10、年漢密爾頓首先提出的一個關于12面體的數學游戲：能否在圖7-4.6中找到一個回路，使它含有圖中所有結點一次且僅一次？若把每個結點看成一座城市，連接兩個結點的邊看成是交通線，那么這個問題就變成能否找到一條旅行路線，使得沿著該旅行路線經過每座城市恰好一次，再回到原來的出發(fā)地？他把這個問題稱為周游世界問題。,定義7-4.3：給定圖G，若存在一條路經過圖中的每個結點恰好一次，這條路稱作漢密爾頓路。若存在一條回路，經過圖中的每個結點恰好一次，這條回路稱作漢密爾頓回路。具有漢密爾頓回路的圖稱作漢密爾頓圖。,二、漢密爾頓圖,圖7-4.6存在一條漢密爾頓回路，它是漢密爾頓圖,2、定理7-4.3若圖G具有漢密爾

11、頓回路，則對于結點集V的每個非空子集S均有W(G-S)|S|，其中W(G-S)是G-S的連通分支數。,證明設C是G的一條漢密爾頓回路，對于V的任何一個非空子集S，在C中刪去S中任一結點a1，則C-a1是連通的非回路，W(C-a1)=1，|S|1，這時W(C-S)|S|。若再刪去S中另一結點a2，則W(C-a1-a2)2，而|S|2，這時W(C-S)|S|。由歸納法可得：W(C-S)|S|。同時C-S是G-S的一個生成子圖，因而W(G-S)W(C-S)，所以W(G-S)|S|。,C經過圖G的每個結點恰好一次，C與G的結點集合是同一個，因此C-S與G-S的結點集合是同一個，,定理7-4.3是必要條

12、件，可以用來證明一個圖不是漢密爾頓圖。,如右圖，取S=v1,v4，則G-S有3個連通分支，,不滿足W(G-S)|S|，故該圖不是漢密爾頓圖。,所以用此定理來證明某一特定圖不是漢密爾頓圖并不是總是有效的。例如，著名的彼得森(Petersen)圖，在圖中刪去任一個結點或任意兩個結點，不能使它不連通；刪去3個結點，最多只能得到有兩個連通分支的子圖；刪去4個結點，只能得到最多三個連通分支的子圖；刪去5個或5個以上的結點，余下子圖的結點數都不大于6，故必不能有5個以上的連通分支數。所以該圖滿足W(G-S)|S|，但是可以證明它不是漢密爾頓圖。,說明：此定理是必要條件而不是充分條件。有的圖滿足此必要條件，

13、但也不是漢密爾頓圖。,3.定理7-4.4設圖G具有n個結點的簡單圖,如果G中每一對結點度數之和大于等于n-1,則G中存在一條漢密爾頓路。,證明思路：1)先證G連通:若G有兩個或多個互不連通的分支,設一個分圖有n1個結點,任取一個結點v1,另一分圖有n2個結點,任取一個結點v2,因為deg(v1)n1-1,deg(v2)n2-1,deg(v1)+deg(v2)n1+n2-2n-1,與假設矛盾,G是連通的。,2)先證(構造)要求的漢密爾頓路存在:不要求掌握！,2)先證(構造)要求的漢密爾頓路存在:設G中有p-1條邊的路,pn,它的結點序列為v1,v2,vp。如果有v1或vp鄰接于不在這條路上的一個

14、結點,立刻擴展該路,使它包含這個結點,從而得到p條邊的路。否則v1和vp都只鄰接于這條路上的結點,我們證明在這種情況下,存在一條回路包含結點v1,v2,vp。,若v1鄰接于vp,則v1,v2,vp即為所求。若v1鄰接于結點集vl,vm,vj,vt中之一,這里2l,m,.,j,.,tp-1,如果vp是鄰接于vl-1,vm-1,vj-1,vt-1中之一,譬如是vj-1,則v1v2vj-1vpvp-1.vjv1是所求回路（如圖7-4.9(a)所示）。如果vp不鄰接于vl-1,vm-1,vj-1,vt-1中任一個,則vp最多鄰接于p-k-1個結點,deg(vp)p-k-1,deg(v1)=k,故deg

15、(vp)+deg(v1)p-k-1+kn-1,即v1與vp度數之和最多為n-2，得到矛盾。,至此，已經構造出一條包含結點v1,v2,vp的回路,因為G是連通的,所以在G中必有一個不屬于該回路的結點vx與回路中某一結點vk鄰接,如圖7-4.9(b)所示,于是就得到一條包含p條邊的回路(vx,vk,vk+1,vj-1,vp,vp-1,vj,v1,v2,vk-1),如圖7-4.9(c)所示,重復前述構造方法，直到得到n-1條邊的路。,說明：該定理的條件是充分條件但不是必要條件。例：見308頁圖7-4.10。n=6，每一對結點度數之和等于4，小于n-1，但在G中存在一條漢密爾頓路。,3.定理7-4.4

16、設圖G具有n個結點的簡單圖,如果G中每一對結點度數之和大于等于n-1,則G中存在一條漢密爾頓路。,例某地有5個風景點，若每個景點均有兩條道路與其他景點相通，問是否可經過每個景點一次而游完這5處。,解將景點作為結點，道路作為邊，則得到一個有5個結點的無向圖。由題意，對每個結點vi(i=1,2,3,4,5)有deg(vi)=2。則對任兩點和均有deg(vi)+deg(vj)=2+2=4=51所以此圖有一條漢密爾頓回路。即經過每個景點一次而游完這5個景點。,例：在七天內安排七門課程的考試，使得同一位教師所任的兩門課程不排在接連的兩天中，試證明如果沒有教師擔任多于四門課程，則符合上述要求的考試安排總是

17、可能的。,證明：設G為具有七個結點的圖，每個結點對應于一門課程考試，如果這兩個結點對應的課程考試是由不同教師擔任的，那么這兩個結點之間有一條邊，因為每個教師所任課程數不超過4，故每個結點的度數至少是3，任兩個結點的度數之和至少是6，故G總是包含一條漢密爾頓路，它對應于一個七門考試課程的一個適當的安排。,4.定理7-4.5設圖G具有n個結點的簡單圖,如果G中每一對結點度數之和大于等于n,則G中存在一條漢密爾頓回路。證明：略,5、圖的閉包定義7-4.4：給定圖G=有n個結點，若將圖G中度數之和至少是n(n)的非鄰接結點連接起來得圖G，對圖G重復上述步驟，直到不再有這樣的結點對存在為止，所得到的圖，

18、稱為是原圖G的閉包，記作C(G)。,在這個例子中C(G)是完全圖，一般情況下，C(G)也可能不是完全圖。,6、定理7-4.6：當且僅當一個簡單圖的閉包是漢密爾頓圖時，這個簡單圖是漢密爾頓圖。7、推論：n3的有向(無向)完全圖Kn為漢密爾頓圖。,判別漢密爾頓路不存在的標號法,關于圖中沒有漢密爾頓路的判別尚沒有確定的方法。介紹一個判別漢密爾頓路不存在的標號法。,例證明下圖沒有漢密爾頓路。,任取一結點如v1,用A標記，所有與它鄰接的結點標B。,繼續(xù)不斷地用A標記所有與B鄰接的結點，用B標記所有與A鄰接的結點，直到圖中的所有結點全部標記完畢。,作業(yè),P311：（2）（6）（9）,7-5平面圖,一、平面

19、圖1、定義7-5.1如果無向圖G=的所有結點和邊可以在一個平面上圖示出來，而使各邊僅在頂點處相交。無向圖G稱為平面圖（planargraph），否則稱G為非平面圖。,有些圖形從表面看有幾條邊是相交的，但是不能就此肯定它不是平面圖。例如，下面左圖表面看有幾條邊相交，但如把它畫成右圖，則可看出它是一個平面圖。,有些圖形不論怎樣改畫，除去結點外，總有邊相交，故它是非平面圖。,定義7-5.2設圖G=是一連通平面圖，由圖中各邊所界定的區(qū)域稱為平面圖的面(regions)。有界的區(qū)域稱為有界面，無界的區(qū)域稱為無界面。界定各面的閉的擬路徑稱為面的邊界(boundary).面r的邊界長度稱為面r的度（degr

20、ee）記為deg(r)，又稱為面r的次數。,2、面、邊界,例如圖7-5.3,deg(r1)=3deg(r2)=3deg(r3)=5deg(r4)=4deg(r5)=3,deg(r1)+deg(r2)+deg(r3)+deg(r4)+deg(r5)=18,如邊是兩個面的分界線，該邊在兩個面的度數中各記1次。如邊不是兩個面的分界線(稱為割邊)則該邊在該面的度數中重復記了兩次，故定理結論成立。,3.定理7-5.1設G為一有限平面圖，面的次數之和等于其邊數的兩倍。,證明思路：任一條邊或者是兩個面的共同邊界（貢獻2次），或者是一個面的重復邊（貢獻2次）,4、歐拉定理定理7-5.2（歐拉定理）設G為一平面

21、連通圖，v為其頂點數，e為其邊數，r為其面數，那么歐拉公式成立ve+r=2,證明（1）若G為一個孤立結點，則v=1，e=0，r=1，故v-e+r=2成立。,（2）若G為一個邊，即v=2，e=1，r=1，則v-e+r=2成立。,（3）設G為k條邊時，歐拉公式成立，即vk-ek+rk=2?？疾斓那闆r。,因為在k條邊的連通圖上增加一條邊，使它仍為連通圖，只有下述兩種情況：,加上一個新結點b，b與圖上的一點a相連，此時vk和ek兩者都增加1，而面數rk沒變，故（vk+1）-（ek+1）+rk=vk-ek+rk=2。,用一條邊連接圖上的已知兩點，此時ek和rk都增加1，結點數vk沒變，故vk-（ek+1

22、）+（rk+1）=vk-ek+rk=2。,例：已知一個平面圖中結點數v=10，每個面均由4條邊圍成，求該平面圖的邊數和面數。,解：因每個面的次數均為4，則2e=4r，即e=2r，又v=10，代入歐拉公式v-e+r=2有10-2r+r=2解得r=8，則e=2r=16。,5.定理7-5.3設G為一簡單連通平面圖，其頂點數v3，其邊數為e，那么e3v6,證明思路：設G的面數為r,當v=3,e=2時上式成立,若e=3,則每一面的次數不小于3,各面次數之和不小于2e,因此2e3r,r2e/3代入歐拉公式:2=v-e+rv-e+2e/3整理后得:e3v6說明：這是簡單圖是平面圖的必要條件。本定理的用途:判

23、定某圖是非平面圖。,例如：K5中e=10，v=5，3v-6=9，從而e3v-6，所以K5不是平面圖。,定理7-5.3的條件不是充分的。如K3,3圖滿足定理7-5.3的條件（v=6，e=9，3v-6=12，e3v-6成立），但K3,3不是平面圖。,315頁例2證明K3,3圖不是平面圖。,在K3,3中有6個結點9條邊，2v-4=26-4=89,與2v-4e矛盾，故K3,3不是平面圖。,證明假設K3,3圖是平面圖。,在K3,3中任取三個結點，其中必有兩個結點不鄰接，故每個面的次數都不小于4，由4r2e，re/2，即v-e+e/2v-e+r=2，v-e/22，2v-e4，2v-4e。,6、定義7-5.

24、3：給兩圖G1和G2，或者它們是同構的，或者反復地插入或去掉二度結點后，使G1和G2同構，則稱G1和G2是在2度結點內同構的，也稱G1和G2是同胚的。,在給定圖G的邊上，插入一個新的度數為2的結點，使一條邊分成兩條邊，或者對于關于度數為2的結點的兩條邊，去掉這個結點，使兩條邊化成一條邊，這些都不會影響圖的平面性。,7、庫拉托夫斯基定理(Kuratowski定理)定理7-5.4：一個圖是平面圖的充要條件是它不含與K5或K3，3在二度結點內同構的子圖。,歐拉公式有時可以用來判定某個圖是非平面圖。下面的庫拉托夫斯基定理給出了判定一個圖是平面圖的充要條件.,K3，3,K5,K5和K3，3常稱作庫拉托夫

25、斯基圖。,作業(yè),P317：（1）（2）,7-6對偶圖與著色,掌握對偶圖的定義，會畫圖G的對偶圖G*掌握自對偶圖的定義及必要條件。,與平面圖有密切關系的一個圖論的應用是圖形的著色問題，這個問題最早起源于地圖的著色，一個地圖中相鄰國家著以不同顏色，那么最少需用多少種顏色？一百多年前，英國格色里(Guthrie)提出了用四種顏色即可對地圖著色的猜想，1879年肯普(Kempe)給出了這個猜想的第一個證明，但到1890年希伍德(Hewood)發(fā)現肯普證明是錯誤的，但他指出肯普的方法雖不能證明地圖著色用四種顏色就夠了，但可證明用五種顏色就夠了，即五色定理成立。,此后四色猜想一直成為數學家感興趣而未能解決

26、的難題。直到1976年美國數學家阿佩爾和黑肯宣布：他們用電子計算機證明了四色猜想是成立的。所以從1976年以后就把四色猜想這個名詞改成“四色定理”了。為了敘述圖形著色的有關定理，下面先介紹對偶圖的概念。,一、對偶圖1、對偶圖定義7-6.1對具有面F1,F2,.,Fn的連通平面圖G=實施下列步驟所得到的圖G*稱為圖G的對偶圖（dualofgraph）：,如果存在一個圖G*=滿足下述條件：,（a）在G的每一個面Fi的內部作一個G*的頂點vi*。即對圖G的任一個面Fi內部有且僅有一個結點vi*V*。,(b)若G的面Fi，Fj有公共邊ek，則作ek*=(vi*，vj*)，且ek*與ek相交。即若G中面

27、Fi與Fj有公共邊界ek，那么過邊界的每一邊ek作關聯vi*與vj*的一條邊ek*=(vi*,vj*)。ek*與G*的其它邊不相交。,(c)當且僅當ek只是一個面Fi的邊界時(割邊)，vi*存在一個環(huán)e*k與ek相交。即當ek為單一面Fi的邊界而不是與其它面的公共邊界時，作vi*的一條環(huán)與ek相交（且僅交于一處）。所作的環(huán)不與G*的邊相交。,則稱圖G*為G的對偶圖。,實線邊圖為平面圖，虛線邊圖為其對偶圖。,v*=r，e*=e，r*=v,2、自對偶圖定義7-6.2如果圖G的對偶圖G*同構于G,則稱G是自對偶圖。,二、圖的著色1、問題的提出該問題起源于地圖的著色問題。圖著色的三種情況:對點著色是對

28、圖G的每個結點指定一種顏色，使得相鄰結點的顏色不同;對邊著色給每條邊指定一種顏色使得相鄰的邊的顏色不同，給面著色給每個面指定一種顏色使得有公共邊的兩個面有不同的顏色。對邊著色和對面著色均可轉化為對結點著色問題。,從對偶圖的概念，可以看到，對于地圖的著色問題，可以歸納為對于平面圖的結點的著色問題，因此四色問題可以歸結為要證明對于任何一個平面圖，一定可以用四種顏色，對它的結點進行著色，使得鄰接的結點都有不同的顏色。,2、圖的正常著色：圖G的正常著色(或簡稱著色)是指對它的每一個結點指定一種顏色，使得沒有兩個鄰接的結點有同一種顏色。如果圖在著色時用了n種顏色，我們稱G為n-色的圖。3、色數：對于圖G著色時，需要的最少顏色數稱為G的色數，記作x(G)。,證明一個圖的色數為n，首先必須證明用n種顏色可以著色該圖，其次證明用少于n種顏