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

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

3、V*。,(b)若G的面Fi，F(xiàn)j有公共邊ek，則作ek*=(vi*，vj*)，且ek*與ek相交。 即若G中面Fi與Fj有公共邊界ek ，那么過邊界的每一邊ek作關聯(lián)vi*與vj*的一條邊ek* =(vi*, vj*) 。 ek*與G*的其它邊不相交。,(c)當且僅當ek只是一個面Fi的邊界時(割邊)，vi*存在一個環(huán)e*k與ek相交。 即當ek為單一面Fi的邊界而不是與其它面的公共邊界時，作vi*的一條環(huán)與ek相交（且僅交于一處）。所作的環(huán)不與 G*的其他邊相交。,則稱圖G*為G的對偶圖。,v*=r，e*=e，r*=v,說明：v*=r，e*=e，r*=v。 平面圖的對偶圖仍滿足歐拉定理，且仍

4、是平面圖。,例 畫出下圖的對偶圖。,練習321頁 (1) 畫出各圖的對偶圖,練習 321頁（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、自對偶圖 定義7-6.2 如果圖G的對偶圖G*同構于G,則稱G是自對偶圖。,二、圖的著色 1、問題的提出 該問題起源于地圖的著色問題。 對點的著色就是對圖G的每個結點指定一種顏色，使得相鄰結點的顏色不同，對邊著色就是，給每條邊指定一種顏色使得相鄰的邊的顏色不同，給面著色就是給每個面指定一種顏色使得有公共邊的兩個面有不同的顏色。 對邊著色和

5、對面著色均可以轉化為對結點著色問題。,從對偶圖的概念，我們可以看到，對于地圖的著色問題，可以歸納為對于平面圖的結點的著色問題，因此四色問題可以歸結為要證明對于任何一個平面圖，一定可以用四種顏色，對它的結點進行著色，使得鄰接的結點都有不同的顏色。,2、圖的正常著色：圖G的正常著色(或簡稱著色)是指對它的每一個結點指定一種顏色，使得沒有兩個鄰接的結點有同一種顏色。如果圖在著色時用了n種顏色，我們稱G為n-色的。,3、色數(shù)：對于圖G著色時，需要的最少顏色數(shù)稱為G的色數(shù)，記作x(G)。,證明一個圖的色數(shù)為n，首先必須證明用n種顏色可以著色該圖，其次證明用少于n種顏色不能著色該圖。,4、對點著色的韋爾奇

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

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

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

9、來，一直成為數(shù)學上的著名難題，它吸引許許多多的人，為之而作出大量辛勞，也得到很多重要結果，但長久未能得到解決。直到1976年6月，由美國伊利諾斯大學兩名數(shù)學家愛普爾(K.I.Apple)、黑肯(W.Haken)在考西(J.Koch)幫助下借助于電子計算機，用了一百多億次邏輯判斷，花了1200多機時才證明四色猜想是成立的，從此宣告，四色猜想成為四色定理?，F(xiàn)將它敘述如下：,相應地有下面的定理。 9、定理：對于任何地圖M，M是四著色的，即(M)4。,8、四色定理：平面圖的色數(shù)不超過4。,練習 321頁 （2）-（b）,圖的對偶圖有12個面，用三種顏色對其進行了著色。,圖有7個面，用三種顏色對其進行了著色。,應用： 例：如何安排一次7門課程考試，使得沒有學生在同一時有兩門考試？,解：用結點表示課程，若在兩個結點所表示的課程里有公共學生，則在這兩個結點之間有邊。用不同顏色來表示考試的各個時間段?？荚嚨陌才啪蛯趫D的著色。,如上圖所示，因為這個圖的色數(shù)為4，所以需要4個時間段：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