離散數(shù)學(xué)第七章第六節(jié)

第7-6講對偶圖與著色1.著色問題2.對偶圖的概念3.正常著色4.WelchPowell著色法5.四色定理6.課堂練習(xí)7.第7-6講作業(yè)11、著色問題與平面圖密切相關(guān)的一個問題是圖形的著色。它起源于地圖的著色，即讓一張地圖上相鄰的國家著以不同的顏色，最少要用多少種顏色？

100多年前，英國人Guthrie提出了用四種顏色就可以實現(xiàn)對地圖的著色。直到1976年，美國伊利諾斯州立大學(xué)教師K.Appel和W.Haken借助于大型電子計算機，花費1200多機時，分析了2000多個圖，包含幾百萬種情況，宣稱四色猜想成立。但由于程序冗長而復(fù)雜，使一些人還想重新證明。22、對偶圖的概念（1）定義1給定平面圖G=<V,E>，設(shè)它有n個面F1，F(xiàn)2，…，F(xiàn)n。若圖G*

=<V*,E*>滿足下列條件：(1)對圖G任意一個面Fi，其內(nèi)部有且僅有一個結(jié)點vi*屬于V*；(2)對圖G任意兩個面Fi、Fj的公共邊界ek有且僅有一條邊ek*屬于E*，使ek*=（vi*，vj*），且ek*與ek相交；(3)當(dāng)且僅當(dāng)ek只是一個面Fi的邊界時，vi*有一個環(huán)ek*與ek相交。則稱圖G*是圖G的對偶圖。對偶圖顯然是相互的。G*是G的對偶圖，則G*也是G的對偶圖。特別是連通平面圖的對偶圖也是平面圖。32、對偶圖的概念（2）定義2圖G的對偶圖G*

同構(gòu)于G，則稱圖G是自對偶圖。自對偶圖的例子：43、正常著色

由對偶圖的概念，可以將地圖的著色轉(zhuǎn)化為對平面圖結(jié)點的著色。因而四色問題歸結(jié)為證明對任何一個平面圖，可用四種顏色對其結(jié)點實施著色，使鄰接的結(jié)點有不同的顏色。圖G的正常著色(簡稱“著色”)指對G的每個結(jié)點指定一種顏色，使鄰接的結(jié)點具有不同的顏色。如果圖G著色用了n種顏色，則稱圖G是n-色的。圖G著色所需的最少顏色數(shù)稱為G的著色數(shù)，記作x(G)。左圖著色所需的最少顏色數(shù)為4，因此它是4-色的54、WelchPowell著色法至今還沒有找出一個簡單的方法以確定某個圖G是否是n-色的。但可以用WelchPowell方法對圖G實施著色，步驟如下：（1）將圖G的所有結(jié)點按度數(shù)遞減的次序排列(度數(shù)相同的結(jié)點次序隨意);（2）用第一種顏色對度數(shù)最大的結(jié)點著色，并按排列次序，依次對與前面已著色點不相鄰的結(jié)點著上同色；（3）用第二種顏色對結(jié)點序列中未著色結(jié)點按步驟(2)著色；用第三種顏色繼續(xù)如法著色，…，直到所有結(jié)點全部著色為止。例：對右圖著色。解：結(jié)點排序：HCFABGDE用紅色對H及不相鄰的結(jié)點A著色；用藍色對C及不相鄰的結(jié)點E、G著色；用黃色對F及不相鄰的結(jié)點B、D著色；64、WelchPowell著色法(續(xù))不用WelchPowell方法對圖隨意實施著色，可能要多用顏色。前例x(G)=3,下面對圖隨意著色：用第一色對A及不相鄰的結(jié)點D著同色；用第二色對B及不相鄰的結(jié)點E著同色；用第三色對C及不相鄰的結(jié)點G著同色；用第四色對F著色；用第五色對H著色。75、四色定理定理1x(Kn)=n，Kn是有n個結(jié)點的完全圖。證：因完全圖Kn的每個結(jié)點與其它的n-1個結(jié)點都鄰接，所以每個結(jié)點必須著不同的顏色，才能使鄰接結(jié)點有不同的顏色，故Kn的著色數(shù)不少于n。又因n個結(jié)點的著色數(shù)至多為n,因而x(Kn)=n。定理2任意平面圖最多是5-色的。（證明略）

定理3（四色定理）任意平面圖最多是4-色的86、課堂練習(xí)練習(xí)六人在一起，或者三人互相認識，或者三人彼此不認識。解：將6個人分別用平面上A、B、C、D、E、F六點表示。從任一人出發(fā)，該人與其它五人或認識，或不認識，如兩人認識，則相應(yīng)兩點用紅線相連，否則，用藍線相連。不失一般性，考慮從A開始，與其它五點可以有五條線相連。那么五條線中必有3條會著上相同的顏色。假定AB、AC、AD為蘭色，如果此時BC、CD、BD中有一條邊為藍色