7-6 對(duì)偶圖與著色.ppt

1、離散數(shù)學(xué)Discrete Mathematics,7-6 對(duì)偶圖與著色,要求： 掌握2個(gè)定理，會(huì)畫圖G的對(duì)偶圖 G* 掌握韋爾奇.鮑威爾著色法。,學(xué)習(xí)本節(jié)要熟悉如下術(shù)語(yǔ)（4個(gè)）：,對(duì)偶圖、,自對(duì)偶圖、,正常著色、,著色數(shù),與平面圖有密切關(guān)系的一個(gè)圖論的應(yīng)用是圖形的著色問題，這個(gè)問題最早起源于地圖的著色，一個(gè)地圖中相鄰國(guó)家著以不同顏色，那么最少需用多少種顏色？一百多年前，英國(guó)格色里(Guthrie)提出了用四種顏色即可對(duì)地圖著色的猜想，1879年肯普(Kempe)給出了這個(gè)猜想的第一個(gè)證明，但到1890年希伍德(Hewood)發(fā)現(xiàn)肯普證明是錯(cuò)誤的，但他指出肯普的方法雖不能證明地圖著色用四種顏色就

2、夠了，但可證明用五種顏色就夠了，即五色定理成立。,此后四色猜想一直成為數(shù)學(xué)家感興趣而未能解決的難題。直到1976年美國(guó)數(shù)學(xué)家阿佩爾和黑肯宣布：他們用電子計(jì)算機(jī)證明了四色猜想是成立的。所以從1976年以后就把四色猜想這個(gè)名詞改成“四色定理”了。為了敘述圖形著色的有關(guān)定理，下面先介紹對(duì)偶圖的概念。,一、對(duì)偶圖 1、對(duì)偶圖 定義7-6.1 對(duì)具有面F1 ,F2,., Fn的連通平面圖G=實(shí)施下列步驟所得到的圖G*稱為圖G的對(duì)偶圖（dual of graph）：,如果存在一個(gè)圖G*=滿足下述條件：,（a）在G的每一個(gè)面Fi的內(nèi)部作一個(gè)G*的頂點(diǎn)vi* 。即對(duì)圖G的任一個(gè)面Fi內(nèi)部有且僅有一個(gè)結(jié)點(diǎn)vi*

3、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的對(duì)偶圖。,v*=r，e*=e，r*=v,說明：v*=r，e*=e，r*=v。 平面圖的對(duì)偶圖仍滿足歐拉定理，且仍

4、是平面圖。,例 畫出下圖的對(duì)偶圖。,練習(xí)321頁(yè) (1) 畫出各圖的對(duì)偶圖,練習(xí) 321頁(yè)（1）,(a) v*=5,e*=8,r*=5,(b) v*=7,e*=17,r*=12,(c) v*=5,e*=6,r*=3,(d) v*=7,e*=12,r*=7,2、自對(duì)偶圖 定義7-6.2 如果圖G的對(duì)偶圖G*同構(gòu)于G,則稱G是自對(duì)偶圖。,二、圖的著色 1、問題的提出 該問題起源于地圖的著色問題。 對(duì)點(diǎn)的著色就是對(duì)圖G的每個(gè)結(jié)點(diǎn)指定一種顏色，使得相鄰結(jié)點(diǎn)的顏色不同，對(duì)邊著色就是，給每條邊指定一種顏色使得相鄰的邊的顏色不同，給面著色就是給每個(gè)面指定一種顏色使得有公共邊的兩個(gè)面有不同的顏色。 對(duì)邊著色和

5、對(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的正常著色(或簡(jiǎn)稱著色)是指對(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種顏色不能著色該圖。,4、對(duì)點(diǎn)著色的韋爾奇

6、.鮑威爾方法： 第一步：對(duì)每個(gè)結(jié)點(diǎn)按度數(shù)遞減次序進(jìn)行排列(相同度數(shù)的結(jié)點(diǎn)次序可隨意) 第二步：用第一種顏色對(duì)第一個(gè)結(jié)點(diǎn)著色，并按次序?qū)εc前面著色點(diǎn)不相鄰的每一點(diǎn)著同樣的顏色。 第三步：用第二種顏色對(duì)未著色的點(diǎn)重復(fù)第二步，用第三種顏色繼續(xù)這種做法，直到全部點(diǎn)均著了色為止。,例題1 用韋爾奇鮑威爾法對(duì)圖7-6.3著色。,解 a)根據(jù)遞減次序排列各點(diǎn)A5，A3，A7，A1，A2，A4，A6，A8。 b)第一種顏色對(duì)A5著色，并對(duì)不相鄰結(jié)點(diǎn)A1也著第一種色。 c)對(duì)結(jié)點(diǎn)A3和它不鄰接的A4，A8著第二種顏色。 d)對(duì)結(jié)點(diǎn)A7和它不鄰接的A2， A6著第三種顏色。 因此G是三色的。注意G不可能是二色的，

7、因?yàn)锳1，A2，A3相互鄰接。故必須著三種顏色。所以x(G) 3。,5、定理7-6.1：對(duì)于完全圖Kn有(Kn)=n。,證明：因?yàn)橥耆珗D的每一個(gè)結(jié)點(diǎn)與其他各個(gè)結(jié)點(diǎn)都鄰接，故n個(gè)結(jié)點(diǎn)的著色數(shù)不能少于n，又n個(gè)結(jié)點(diǎn)的著色數(shù)至多為n，故(Kn)=n。 ,6、定理7-6.2：連通平面圖G=至少有三個(gè)結(jié)點(diǎn)，則必有一點(diǎn)uV使得deg(u)5。,證明：設(shè)|V|=v，|E|=e，若G的每個(gè)結(jié)點(diǎn)均有 v deg(u)6， deg(vi )= 2|E|= 2e i=1 則有2e6v，即e3v3v-6，與定理矛盾。 ,7、定理7-6.3：(五色定理)任意平面圖最多是5-色的。, 證明思路：對(duì)結(jié)點(diǎn)個(gè)數(shù)v采用歸納法 (

8、1)歸納基礎(chǔ)：圖G的結(jié)點(diǎn)數(shù)為v=1,2，3，4，5時(shí)，結(jié)論成立。 (2)歸納假設(shè)：設(shè)G有k個(gè)結(jié)點(diǎn)時(shí)結(jié)論成立。即G是最多可5-著色的。 (3)歸納推理：需要證明G有k+1個(gè)結(jié)點(diǎn)時(shí)結(jié)論仍成立。 先在G中刪去度數(shù)小于等于5的結(jié)點(diǎn)u,根據(jù)歸納假設(shè)，所得的圖G-u有k個(gè)結(jié)點(diǎn),結(jié)論成立。然后考慮在G-u中加上一個(gè)結(jié)點(diǎn)的情況。若加入的結(jié)點(diǎn)滿足deg (u)5，則可以對(duì)u正常著色。若加入的結(jié)點(diǎn)滿足deg (u)=5，則與它鄰接的5個(gè)結(jié)點(diǎn)可以用4種顏色著色。分兩種情況證明： . 對(duì)調(diào)v1,v3兩個(gè)結(jié)點(diǎn)的顏色后，給著v1的顏色。 . 對(duì)調(diào)v2,v4兩個(gè)結(jié)點(diǎn)的顏色后，給著v2的顏色。 ,自從四色猜想提出后，一百多年

9、來(lái)，一直成為數(shù)學(xué)上的著名難題，它吸引許許多多的人，為之而作出大量辛勞，也得到很多重要結(jié)果，但長(zhǎng)久未能得到解決。直到1976年6月，由美國(guó)伊利諾斯大學(xué)兩名數(shù)學(xué)家愛普爾(K.I.Apple)、黑肯(W.Haken)在考西(J.Koch)幫助下借助于電子計(jì)算機(jī)，用了一百多億次邏輯判斷，花了1200多機(jī)時(shí)才證明四色猜想是成立的，從此宣告，四色猜想成為四色定理?，F(xiàn)將它敘述如下：,相應(yīng)地有下面的定理。 9、定理：對(duì)于任何地圖M，M是四著色的，即(M)4。,8、四色定理：平面圖的色數(shù)不超過4。,練習(xí) 321頁(yè) （2）-（b）,圖的對(duì)偶圖有12個(gè)面，用三種顏色對(duì)其進(jìn)行了著色。,圖有7個(gè)面，用三種顏色對(duì)其進(jìn)行了著色。,應(yīng)用： 例：如何安排一次7門課程考試，使得沒有學(xué)生在同一時(shí)有兩門考試？,解：用結(jié)點(diǎn)表示課程，若在兩個(gè)結(jié)點(diǎn)所表示的課程里有公共學(xué)生，則在這兩個(gè)結(jié)點(diǎn)之間有邊。用不同顏色來(lái)表示考試的各個(gè)時(shí)間段。考試的安排就對(duì)應(yīng)于圖的著色。,如上圖所示，因?yàn)檫@個(gè)圖的色數(shù)為4，所以需要4個(gè)時(shí)間段：1和5、3和7、4和6、2。,deg(v1)=5 deg(v2)=4 deg(v3)=5 deg(v4)=5 deg(v5)=5 deg(v6)=4 deg(v