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

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

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

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

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

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

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