1、8.5 特殊的圖歐拉圖漢密爾頓圖平面圖對偶圖 歐拉圖 哥尼斯堡七橋問題：18世紀在哥尼斯堡城(今俄羅斯加里寧格勒)的普萊格爾河上有7座橋，將河中的兩個島和河岸連結，如下圖所示。 城中的居民經常沿河過橋散步，于是提出了一個問題：能否一次走遍7座橋，而每座橋只許通過一次，最后仍回到起始地點。這就是七橋問題，一個著名的圖論問題。 于是“七橋問題”就等價于上圖能否一筆畫成的問題 。歐拉提出不存在一次走遍7座橋，而每座橋只許通過一次的走法。陸地是橋梁的連接地點，不妨把圖中被河隔開的陸地看成4個結點，7座橋表示成7條連接這4個結點的邊，如下圖所示。 定義1：給定無孤立結點圖G，若存在一條路，經過圖中每邊一

2、次且僅一次，該條路稱為歐拉路。 定義2：給定無孤立結點圖G，若存在一條回路，經過圖中每邊一次且僅一次，該回路稱為歐拉回路。具有歐拉回路的圖稱為歐拉圖。v2v3v4v1（V1、V2、V3、V1、V4、V3）是一條歐拉路定理1：給定無向連通圖G，G是歐拉圖，當且僅當圖中每個結點都是偶數度結點。定理2：無向圖連通圖G有一條歐拉路，當且僅當G有零個或兩個奇數度結點。 v2v3v4v1 例：證明：n階完全無向圖Kn是歐拉圖當且僅當n為奇數。 證： n階完全無向圖Kn是連通圖且每個節點的度數均為n-1，于是Kn是歐拉圖當且僅當n-1是偶數，即n為奇數。例：從圖中找一條歐拉路。解 ：有兩個奇數度結點 : v

3、1和v4，所以存在歐拉路。L = v1,v2,v3,v4,v5,v2,v4 是一條歐拉路。定理3：有向圖G為歐拉圖，當且僅當G是連通的，且每個結點入度等于出度。 定理4：一個有向圖G中具有 歐拉路，當且僅當它是連通的，而且除兩個結點外，每個結點的入度等于出度，但這兩個結點中，一個結點的入度比出度小1，一個結點的入度比出度大1。歐拉回路問題既是一個有趣的游戲問題, 又是一個有實用價值的問題。郵遞員一般的郵遞路線是需要遍歷某些特定的街道, 理想地, 他應該走一條歐拉路, 即不重復地走遍圖中的每一條邊。有的郵遞任務是聯系某些特定的收發點, 不要求走遍每一條邊, 只要求不重復地遍歷圖中的每一個頂點,

4、此時感興趣的是圖中的頂點, 這就是下面研究的漢密爾頓圖。漢密爾頓圖 1859年, 愛爾蘭數學家漢密爾頓(Halmiton)提出一個“周游世界”的游戲, 它把圖(a)所示的正十二面體的二十個頂點當作是地球上的二十個城市, 要求旅游者從某個城市出發, 沿棱走過每個城市一次且僅一次, 最后回到出發點。(b)圖中粗線所構成的回路就是問題的答案。ab 定義1：給定圖G，若存在一條通路，經過圖中的每個結點恰好一次，這條通路稱作漢密爾頓路。 定義2：給定圖G，若存在一條回路，經過圖中的每個結點恰好一次，這條回路稱作漢密爾頓回路。具有漢密爾頓回路的圖稱作漢密爾頓圖。 例：(a)存在漢密爾頓回路, (a)是漢密

5、爾頓圖。(b)存在漢密爾頓通路但不存在漢密爾頓回路, (b)不是漢密爾頓圖。(c)不存在漢密爾頓通路且不存在漢密爾頓回路, (c)不是漢密爾頓圖。（a）（b）（c） 練習：一只小螞蟻可否從立方體的一個頂點出發，沿著棱爬行， 它爬過每一個頂點一次且僅一次，最后回到原出發點？例：證明：若一個無向圖G = (V，E)存在一個節點v,使得deg(v)=1，則G不是漢密爾頓圖。證: 因為圖G的漢密爾頓回路要經過節點v，這是顯然 deg(v)2，故G不是漢密爾頓圖。 定理1：若圖G =為漢密爾頓圖，則對于結點集V的每個非空子集S(真子集S )有：W(G-S)|S| 成立，其中W(G-S)是G-S中的連通分

6、支數。(必要條件)。v1v2v7v3v5v8v4v6v2v7v3v5v8v6 定理2：設圖G是有n個結點的簡單無向圖，若G中任意兩個結點度數之和大于等于n，則 G 是 漢密爾頓圖。（這是充分條件，但不是必要條件）（a）（b）歐拉圖和漢密爾頓圖之間的區別：(1)歐拉回路是簡單回路, 而漢密爾頓圖回路是基本回路。簡單回路：各邊都不相同的回路?；净芈罚撼K點與始點外，其它結點都不相同的回路。 (2) 歐拉圖遍歷邊, 而漢密爾頓圖遍歷頂點。 平面圖 例 ：K3,3圖如下，試問：能否轉變成與其等價的，且使得任何兩條邊除了端點外沒有其它的交點的平面上的圖？ 456定義1 ：設G=是一個無向圖，如果能夠把

7、G的所有結點和邊畫在平面上，且使得任何兩條邊除了端點外沒有其它的交點，就稱G是一個平面圖。 判斷一個圖是否為平面圖的簡單方法是觀察法： 找出基本循環，將交叉的邊分別放置在基本循環內或外而避免交叉。如下圖所示：但并非所有的圖經過處理之后都可變為平面圖。 定義2：設G是一連通平面圖，由圖中的邊所包圍的區域，且在該區域內既不包含圖的結點，也不包含圖的邊，這樣的區域稱為G的面。 包圍一個面的諸邊稱為此面的邊界。 面的面積為有限者稱為有限面，面的面積為無限者稱為無限面。 例：為有限面為無限面定義3：一個面的邊界的回路長度稱作是該面的次數，記為：deg(r)定理1 ：一個有限平面圖，面的次數之和等于其邊數

8、的兩倍。證明 ：對于G中的每一條邊e，e或是兩個面的公共邊，或是在一個面中為懸掛邊被作為邊界計算兩次，故定理成立。 定理2： (歐拉定理)設圖G是一個n個結點,m條邊的連通平面圖，它的面數為r，則有歐拉公式： nmr2。 證明 :用歸納法 m=0時，G為平凡圖，n=1，r=1，公式成立。 設m=k-1（k1）時公式成立，現在考慮m=k時的情況。因為在連通圖上增加一條邊仍為連通圖，則有三種情況： （1）所增邊為懸掛邊，此時G的面數不變，頂點數增1，公式成立。 （2）在圖的任意兩個不相鄰點間增加一條邊，此時G的面數增1，邊數增1，但頂點數不變，公式成立。 （3）所增邊為一個環，此時G的面數增1，邊

9、數增1，但頂點數不變，公式成立。 練習： 在由6個結點，12條邊構成的連通簡單平面圖中，每個面由幾條邊圍成？ 定理3 :設G是一個包含n個結點,m條邊的連通簡單平面圖，且每個面的次數至少為 l（l 3），則于是有故 證明 :由定理1 (r為G的面數)再由歐拉公式 n-m+r=2 推論1:設圖G是一個包含n個結點,m條邊的連通簡單平面圖，若n3,則m3n-6。 證明 ：由于G是n 3的簡單連通平面圖，所以G的每個面至少由3條邊圍成，即l 3，由定理3得m3n-6. 推論1給出了平面圖的必要條件，若不滿足這些條件，則一定不是平面圖。例：K5 圖不是平面圖。 例：證明當每個結點的度數大于等于3時，不

10、存在7條邊的連通簡單平面圖。證： (反證)：設G是(n，m)圖，若m=7，根據推論1知，m3n-6，即73n-6，于是3n13。根據握手定理，有 即 3n14。這與3n13矛盾。 練習： (1) 設G是包含n個結點 (n3),m條邊的連通簡單平面圖，證明G中至少有一個結點的度數小于等于5。 (2) 設G是包含n個結點 (n3),邊數m小于30的連通簡單平面圖，證明G中存在結點 v , d(v) 4。 推論2: 若連通簡單平面圖G不以K3為子圖，則 m 2n- 4。 證明 :由于G中不含K3，所以G的每個面至少由4條邊圍成，即l 4，代入定理3，得m2n- 4. 例：證明K5和K3，3是非平面圖

11、。 證明: 假設K5是平面圖，由推論1可知應有m3n-6，而當n=5，m=10時，這是不可能的，所以K5是非平面圖。 假設K3，3是平面圖，因其不含子圖K3，由推論2可 知，當n=6，m=9時，m2n-4是不可能的，所以 K3，3是非平面圖。 (2) 若e是G中兩個不同面Ri和Rj的公共邊，則存在且僅存在一條邊e*k G*與e相交； (3) 若e是一個面Ri內的邊，則在G*中有一條與e交叉的環。 則稱G*為G的對偶圖， G*與G互為對偶圖。定義 設平面圖G=V,E有r個面R1，R2，Rr，若有圖G*=V*,E*滿足下述條件：(1) RiG，內部有且僅有一個結點v*i V*，i=1，2，r。1. 對偶圖 對偶圖 例:圖（a）和（b）中，G*是G的對偶圖，G的邊用實線表示，G*的邊用虛線 表示。（a）（b）2. 著色問題 在地圖上，相鄰國家涂不同的顏色，最少需要多少種顏色？100多年前，有人提出了“四色猜想”，即只用四種顏色就能做到，但一直無法證明，直到1976年美國數學家才用電子計算機證明了這一猜想。 地圖著色自然是對平面圖的面著色，利用對偶圖，可將其轉化為相對簡單的頂點著色問題，即對圖中相鄰的頂點涂不同的顏色。韋爾奇鮑威爾（WelchPowell）給出了一種對圖的著色方法，步驟如下：（1）將圖G中的頂點按度數遞減次序排列。（2）用第一種顏色對第一頂點著色，并將與