離散數(shù)學(xué)第八章(第4講)課件

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

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

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

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

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

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

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

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

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

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

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