離散數(shù)學(xué) 7-4 歐拉圖和漢

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

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

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

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

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

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

7、進(jìn)制數(shù)000，001，111，設(shè)ai0,1，從結(jié)點(diǎn)a1a2a3可引出兩條有向邊，其終點(diǎn)分別是a2a30以及a2a31。該兩條邊分別記為a1a2a30和a1a2a31。按照上述方法，對(duì)于八個(gè)結(jié)點(diǎn)的有向圖共有16條邊，在這種圖的任一條路中，其鄰接的邊必是a1a2a3a4和a2a3a4a5的形式，即是第一條邊標(biāo)號(hào)的后三位數(shù)與第二條邊的頭三位數(shù)相同。由于圖中16條邊被記為不同的二進(jìn)制數(shù)，可見前述鼓輪轉(zhuǎn)動(dòng)所得到16個(gè)不同位置觸點(diǎn)上的二進(jìn)制信息，即對(duì)應(yīng)于圖中的一條歐拉回路。,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)所求的二進(jìn)制序列為：0000100110101111(0)1101011110000100(1)（從圖示位置開始）,上述結(jié)論可推廣到鼓輪具有n個(gè)觸點(diǎn)的情況。構(gòu)造2n-1個(gè)結(jié)點(diǎn)的有向圖，每個(gè)結(jié)點(diǎn)標(biāo)記為n-1位二進(jìn)制數(shù),從結(jié)點(diǎn)a1a2a3.an-1出發(fā),有一條終點(diǎn)為a2a3.an-10的邊,該邊記為a1a2a3.an-10；還有一條終點(diǎn)標(biāo)記為a2a3.an-11的邊,該邊記為a1a2a3.an-11。鄰接邊的標(biāo)記規(guī)則為：“第一條邊后n-1位與第二條邊前n-1位二進(jìn)制數(shù)相同”。哈密爾頓回路問題見圖7-4.6。,二、漢密爾頓圖,與歐拉回路類似的是漢密爾頓回路。它是1859

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

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

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

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

14、結(jié)點(diǎn),立刻擴(kuò)展該路,使它包含這個(gè)結(jié)點(diǎn),從而得到p條邊的路。否則v1和vp都只鄰接于這條路上的結(jié)點(diǎn),我們證明在這種情況下,存在一條回路包含結(jié)點(diǎn)v1,v2,vp。,若v1鄰接于vp,則v1,v2,vp即為所求。若v1鄰接于結(jié)點(diǎn)集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中任一個(gè),則vp最多鄰接于p-k-1個(gè)結(jié)點(diǎn),deg(vp)p-k-1,deg(v1)=k,故deg

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

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

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

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

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

20、ee）記為deg(r)，又稱為面r的次數(shù)。,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,如邊是兩個(gè)面的分界線，該邊在兩個(gè)面的度數(shù)中各記1次。如邊不是兩個(gè)面的分界線(稱為割邊)則該邊在該面的度數(shù)中重復(fù)記了兩次，故定理結(jié)論成立。,3.定理7-5.1設(shè)G為一有限平面圖，面的次數(shù)之和等于其邊數(shù)的兩倍。,證明思路：任一條邊或者是兩個(gè)面的共同邊界（貢獻(xiàn)2次），或者是一個(gè)面的重復(fù)邊（貢獻(xiàn)2次）,4、歐拉定理定理7-5.2（歐拉定理）設(shè)G為一平面

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

22、）+（rk+1）=vk-ek+rk=2。,例：已知一個(gè)平面圖中結(jié)點(diǎn)數(shù)v=10，每個(gè)面均由4條邊圍成，求該平面圖的邊數(shù)和面數(shù)。,解：因每個(gè)面的次數(shù)均為4，則2e=4r，即e=2r，又v=10，代入歐拉公式v-e+r=2有10-2r+r=2解得r=8，則e=2r=16。,5.定理7-5.3設(shè)G為一簡單連通平面圖，其頂點(diǎn)數(shù)v3，其邊數(shù)為e，那么e3v6,證明思路：設(shè)G的面數(shù)為r,當(dāng)v=3,e=2時(shí)上式成立,若e=3,則每一面的次數(shù)不小于3,各面次數(shù)之和不小于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個(gè)結(jié)點(diǎn)9條邊，2v-4=26-4=89,與2v-4e矛盾，故K3,3不是平面圖。,證明假設(shè)K3,3圖是平面圖。,在K3,3中任取三個(gè)結(jié)點(diǎn)，其中必有兩個(gè)結(jié)點(diǎn)不鄰接，故每個(gè)面的次數(shù)都不小于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，或者它們是同構(gòu)的，或者反復(fù)地插入或去掉二度結(jié)點(diǎn)后，使G1和G2同構(gòu)，則稱G1和G2是在2度結(jié)點(diǎn)內(nèi)同構(gòu)的，也稱G1和G2是同胚的。,在給定圖G的邊上，插入一個(gè)新的度數(shù)為2的結(jié)點(diǎn)，使一條邊分成兩條邊，或者對(duì)于關(guān)于度數(shù)為2的結(jié)點(diǎn)的兩條邊，去掉這個(gè)結(jié)點(diǎn)，使兩條邊化成一條邊，這些都不會(huì)影響圖的平面性。,7、庫拉托夫斯基定理(Kuratowski定理)定理7-5.4：一個(gè)圖是平面圖的充要條件是它不含與K5或K3，3在二度結(jié)點(diǎn)內(nèi)同構(gòu)的子圖。,歐拉公式有時(shí)可以用來判定某個(gè)圖是非平面圖。下面的庫拉托夫斯基定理給出了判定一個(gè)圖是平面圖的充要條件.,K3，3,K5,K5和K3，3常稱作庫拉托夫

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

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

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

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