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

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

如果無孤立結(jié)點(diǎn)圖G上有一條經(jīng)過G的所有邊一次且僅一次的路徑，則稱該路徑為圖G的歐拉路徑（Eulerwalk）。如果圖G上有一條經(jīng)過G邊一次且僅一次的的回路，則稱該回路為圖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)邊序列v0e1v1e2…ekvk，其中結(jié)點(diǎn)可能重復(fù)，但邊不重復(fù)。因歐拉路經(jīng)過（所有邊）所有結(jié)點(diǎn)，所以圖G是連通的。

對于任一非端點(diǎn)結(jié)點(diǎn)vi，在歐拉路中每當(dāng)vi出現(xiàn)一次，必關(guān)聯(lián)兩條邊，故vi雖可重復(fù)出現(xiàn)，但是deg(vi)必是偶數(shù)。對于端點(diǎn),若v0=vk，則deg(v0)必是偶數(shù)，即G中無奇數(shù)度結(jié)點(diǎn)。若v0≠vk，則deg(v0)必是奇數(shù)，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:v0e1v1e2…ekvk。若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é)點(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的每一邊一次僅一次到達(dá)另一結(jié)點(diǎn)。另一種就是從G的某個(gè)結(jié)點(diǎn)出發(fā)，經(jīng)過G的每一邊一次僅一次再回到該結(jié)點(diǎn)。v1v2v3v4v5為歐拉路，有從v2到v3的一筆畫。為歐拉回路，可以從任一結(jié)點(diǎn)出發(fā)，一筆畫回到原出發(fā)點(diǎn)。5.定義7-4.2：給定有向圖G，通過圖中每邊一次且僅一次的一條單向路（回路），稱作單向歐拉路（回路）?？梢詫W拉路和歐拉回路的概念推廣到有向圖中。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。

證明思路與定理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ù)信息。01111111100000001110abcd

設(shè)有一個(gè)八個(gè)結(jié)點(diǎn)的有向圖，如下圖所示。其結(jié)點(diǎn)分別記為三位二進(jìn)制數(shù){000，001，……，111}，設(shè)ai{0,1}，從結(jié)點(diǎn)a1a2a3可引出兩條有向邊，其終點(diǎn)分別是a2a30以及a2a31。該兩條邊分別記為a1a2a30和a1a2a31。按照上述方法，對于八個(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)制信息，即對應(yīng)于圖中的一條歐拉回路。010101110100011001111000e10=1010e13=1101e5=0101e3=0011e11=1011e6=0110e7=0111e14=1110e15=1111e12=1100e2=0010e4=0100e1=0001e8=1000e9=1001e0=0000a1a2a3(=000)0a1a2a3(=000)1a1a2a3(=001)1a1a2a3(=100)0a1a2a3(=111)0a1a2a3(=111)1a1a2a3(=110)0a1a2a3(=011)1所求的歐拉回路為：e0e1e2e4e9e3e6e13e10e5e11e7e16e14e12e8(e0)

（從圖示位置開始）e13e10e5e11e7e16e14e12e8e0e1e2e4e9e3e6(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年漢密爾頓首先提出的一個(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＝<V，E>具有漢密爾頓回路，則對于結(jié)點(diǎn)集V的每個(gè)非空子集S均有W(G-S)≤|S|，其中W(G-S)是G-S的連通分支數(shù)。證明設(shè)C是G的一條漢密爾頓回路，對于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是必要條件，可以用來證明一個(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|，但是可以證明它不是漢密爾頓圖。說明：此定理是必要條件而不是充分條件。有的圖滿足此必要條件，但也不是漢密爾頓圖。3.定理7-4.4

設(shè)圖G具有n個(gè)結(jié)點(diǎn)的簡單圖,如果G中每一對結(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-2<n-1,與假設(shè)矛盾,G是連通的。

2)先證(構(gòu)造)要求的漢密爾頓路存在:

不要求掌握！

2)先證(構(gòu)造)要求的漢密爾頓路存在:

設(shè)G中有p-1條邊的路,p<n,它的結(jié)點(diǎn)序列為v1,v2,…,vp。如果有v1或vp鄰接于不在這條路上的一個(gè)結(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}中之一,這里2≤l,m,...,j,...,t≤p-1,如果vp是鄰接于vl-1,vm-1,…,…,vj-1,…,vt-1中之一,譬如是vj-1,則v1v2…vj-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(vp)+deg(v1)≤p-k-1+k<n-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，每一對結(jié)點(diǎn)度數(shù)之和等于4，小于n-1，但在G中存在一條漢密爾頓路。3.定理7-4.4

設(shè)圖G具有n個(gè)結(jié)點(diǎn)的簡單圖,如果G中每一對結(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)的無向圖。由題意，對每個(gè)結(jié)點(diǎn)vi(i=1,2,3,4,5)有deg(vi)=2。則對任兩點(diǎn)和均有deg(vi)+deg(vj)=2+2=4=5–1所以此圖有一條漢密爾頓回路。即經(jīng)過每個(gè)景點(diǎn)一次而游完這5個(gè)景點(diǎn)。例：在七天內(nèi)安排七門課程的考試，使得同一位教師所任的兩門課程不排在接連的兩天中，試證明如果沒有教師擔(dān)任多于四門課程，則符合上述要求的考試安排總是可能的。證明：設(shè)G為具有七個(gè)結(jié)點(diǎn)的圖，每個(gè)結(jié)點(diǎn)對應(yīng)于一門課程考試，如果這兩個(gè)結(jié)點(diǎn)對應(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總是包含一條漢密爾頓路，它對應(yīng)于一個(gè)七門考試課程的一個(gè)適當(dāng)?shù)陌才拧?.定理7-4.5

設(shè)圖G具有n個(gè)結(jié)點(diǎn)的簡單圖,如果G中每一對結(jié)點(diǎn)度數(shù)之和大于等于n,則G中存在一條漢密爾頓回路。證明：略5、圖的閉包定義7-4.4：給定圖G=<V，E>有n個(gè)結(jié)點(diǎn)，若將圖G中度數(shù)之和至少是n(≥n)的非鄰接結(jié)點(diǎn)連接起來得圖G’，對圖G’重復(fù)上述步驟，直到不再有這樣的結(jié)點(diǎn)對存在為止，所得到的圖，稱為是原圖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平面圖一、平面圖1、定義7-5.1如果無向圖G=<V,E>的所有結(jié)點(diǎn)和邊可以在一個(gè)平面上圖示出來，而使各邊僅在頂點(diǎn)處相交。無向圖G稱為平面圖（planargraph），否則稱G為非平面圖。有些圖形從表面看有幾條邊是相交的，但是不能就此肯定它不是平面圖。例如，下面左圖表面看有幾條邊相交，但如把它畫成右圖，則可看出它是一個(gè)平面圖。有些圖形不論怎樣改畫，除去結(jié)點(diǎn)外，總有邊相交，故它是非平面圖。定義7-5.2設(shè)圖G=<V,E>是一連通平面圖，由圖中各邊所界定的區(qū)域稱為平面圖的面(regions)。有界的區(qū)域稱為有界面，無界的區(qū)域稱為無界面。界定各面的閉的擬路徑稱為面的邊界(boundary).面r的邊界長度稱為面r的度（degree）記為deg(r)

，又稱為面r的次數(shù)。2、面、邊界例如圖7-5.3deg(r1)=3deg(r2)=3deg(r3)=5deg(r4)=4deg(r5)=3deg(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為一平面連通圖，v為其頂點(diǎn)數(shù)，e為其邊數(shù)，r為其面數(shù)，那么歐拉公式成立

v–e+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）+（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ù)v≥3，其邊數(shù)為e，那么e≤3v–6

證明思路：設(shè)G的面數(shù)為r,當(dāng)v=3,e=2時(shí)上式成立,若e=3,則每一面的次數(shù)不小于3,各面次數(shù)之和不小于2e,因此2e≥3r,r≤2e/3

代入歐拉公式:2=v-e+r≤v-e+2e/3

整理后得:e≤3v–6

說明：這是簡單圖是平面圖的必要條件。本定理的用途:判定某圖是非平面圖。例如：K5中e=10，v=5，3v-6=9，從而e>3v-6，所以K5不是平面圖。

定理7-5.3的條件不是充分的。如K3,3圖滿足定理7-5.3的條件（v=6，e=9，3v-6=12，e≤3v-6成立），但K3,3不是平面圖。315頁例2證明K3,3圖不是平面圖。在K3,3中有6個(gè)結(jié)點(diǎn)9條邊，2v-4=2×6-4=8<9,與2v-4≥e矛盾，故K3,3不是平面圖。證明假設(shè)K3,3圖是平面圖。

在K3,3中任取三個(gè)結(jié)點(diǎn)，其中必有兩個(gè)結(jié)點(diǎn)不鄰接，故每個(gè)面的次數(shù)都不小于4，由4r≤2e，r≤e/2，即v-e+e/2≥v-e+r=2，v-e/2≥2，2v-e≥4，2v-4≥e。6、定義7-5.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)，使一條邊分成兩條邊，或者對于關(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，3K5K5和K3，3常稱作庫拉托夫斯基圖。作業(yè)P317：（1）（2）7-6對偶圖與著色掌握對偶圖的定義，會(huì)畫圖G的對偶圖

G*掌握自對偶圖的定義及必要條件。與平面圖有密切關(guān)系的一個(gè)圖論的應(yīng)用是圖形的著色問題，這個(gè)問題最早起源于地圖的著色，一個(gè)地圖中相鄰國家著以不同顏色，那么最少需用多少種顏色？一百多年前，英國格色里(Guthrie)提出了用四種顏色即可對地圖著色的猜想，1879年肯普(Kempe)給出了這個(gè)猜想的第一個(gè)證明，但到1890年希伍德(Hewood)發(fā)現(xiàn)肯普證明是錯(cuò)誤的，但他指出肯普的方法雖不能證明地圖著色用四種顏色就夠了，但可證明用五種顏色就夠了，即五色定理成立。此后四色猜想一直成為數(shù)學(xué)家感興趣而未能解決的難題。直到1976年美國數(shù)學(xué)家阿佩爾和黑肯宣布：他們用電子計(jì)算機(jī)證明了四色猜想是成立的。所以從1976年以后就把四色猜想這個(gè)名詞改成“四色定理”了。為了敘述圖形著色的有關(guān)定理，下面先介紹對偶圖的概念。一、對偶圖1、對偶圖定義7-6.1對具有面F1,F2,...,

Fn的連通平面圖G=<V,E>實(shí)施下列步驟所得到的圖G*稱為圖G的對偶圖（dualofgraph）：如果存在一個(gè)圖G*=<V*，E*>滿足下述條件：（a）在G的每一個(gè)面Fi的內(nèi)部作一個(gè)G*的頂點(diǎn)vi*。即對圖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中面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的對偶圖。實(shí)線邊圖為平面圖，虛線邊圖為其對偶圖。v*=r，e*=e，r*=v2、自對偶圖定義7-6.2如果圖G的對偶圖G*同構(gòu)于G,則稱G是自對偶圖。二、圖的著色1、問題的提出該問題起源于地圖的著色問題。圖著色的三種情況:對點(diǎn)著色是對圖G的每個(gè)結(jié)點(diǎn)指定一種顏色，使得相鄰結(jié)點(diǎn)的顏色不同;對邊著色給每條邊指定一種顏色使得相鄰的邊的顏色不同，給面著色給每個(gè)面指定一種顏色使得有公共邊的兩個(gè)面有不同的顏色。對邊著色和對面著色均可轉(zhuǎn)化為對結(jié)點(diǎn)著色問題。從對偶圖的概念，可以看到，對于地圖的著色問題，可以歸納為對于平面圖的結(jié)點(diǎn)的著色問題，因此四色問題可以歸結(jié)為要證明對于任何一個(gè)平面圖，一定可以用四種顏色，對它的結(jié)點(diǎn)進(jìn)行著色，使得鄰接的結(jié)點(diǎn)都有不同的顏色。2、圖的正常著色：圖G的正常著色(或簡稱著色)是指對它的每一個(gè)結(jié)點(diǎn)指定一種顏色，使得沒有兩個(gè)鄰接的結(jié)點(diǎn)有同一種顏色。如果圖在著色時(shí)用了n種顏色，我們稱G為n-色的圖。3、色數(shù)：對于圖G著色時(shí)，需要的最少顏色數(shù)稱為G的色數(shù)，記作x(G)。證明一個(gè)圖的色數(shù)為n，首先必須證明用n種顏色可以著色該圖，其次證明