第四節(jié)平面圖的著色

第四節(jié)平面圖的著色第1頁，共10頁，2023年，2月20日，星期三12341324第2頁，共10頁，2023年，2月20日，星期三定義2圖的著色是對該圖的每個(gè)頂點(diǎn)都指定一種顏色，使沒有兩個(gè)相鄰的頂點(diǎn)指定為相同的顏色。如果這些頂點(diǎn)選自于一個(gè)有k種顏色的集合，而不管k種顏色是否都用到，這樣的著色稱為k著色。定義3圖G的色數(shù)是著色這個(gè)圖G所需要的最少顏色數(shù)。記作(G)。圖G的色素也稱為圖G的點(diǎn)色素.從定義可知,對于G的任何子圖H,均有x(H)x(G).若G是n階完全圖,若G是n階完全圖,則x(G)=n;若G是至少有一邊的二分圖,則x(G)=2;若G是長為奇數(shù)的圈,則x(G)=3.當(dāng)x(G)3時(shí),G的特征至今尚未清楚,在下一節(jié),將給出G的色素x(G)的一個(gè)上界.第3頁，共10頁，2023年，2月20日，星期三定理1設(shè)u和v是圖G中兩個(gè)不相鄰的頂點(diǎn),則(G)=min{(G+{u,v}),(G?{u,v})},其中G?{u,v}是把G中結(jié)點(diǎn)u與v重合成一個(gè)新結(jié)點(diǎn)，且G中分別與u與v關(guān)聯(lián)的邊都與該新結(jié)點(diǎn)關(guān)聯(lián)。證明:記e={u,v},（1）設(shè)x(G)=k,并考慮G的K著色.假設(shè)頂點(diǎn)u與v染不同的顏色,則G的k著色也是G+e的k著色.此時(shí)x(G+e)k=x(G).現(xiàn)假設(shè)頂點(diǎn)u和v的染色相同,則G的一個(gè)k染色可得到G?e的一個(gè)染色.故(G?e)k=x(G).又在G的k染色中,或者u與v染為不同的顏色,或者為相同的顏色,故min{(G+{u,v}),(G?{u,v})}x(G).第4頁，共10頁，2023年，2月20日，星期三（2）G是G+e的子圖,顯然x(G)x(G+e).

設(shè)(G?e)=k1,并把結(jié)點(diǎn)u和v重合所得的新結(jié)點(diǎn)記為y,則在G?e的k1著色中,把分配給y的顏色分配給G中u和v(u,v不相鄰),即可得到G的一個(gè)k1著色.故

x(G)k1=x(G?e)

所以x(G)min{(G+e),(G?{u,v})}.

綜（1）（2）所述,有(G)=min{(G+{u,v}),(G?{u,v})}.四色問題:連通簡單平面圖的色素不超過4.

四色問題是蓋思里于1852年提出,后經(jīng)眾多數(shù)學(xué)家嘗試證明,均以失敗告終.1976年,美國數(shù)學(xué)家阿佩爾和黑肯宣布借助用計(jì)算機(jī)證明,但時(shí)間超過了1000小時(shí),其可靠性仍在置疑之中.第5頁，共10頁，2023年，2月20日，星期三定理2（五色定理）連通簡單平面圖G的色數(shù)為不超過5.證明:對圖的頂點(diǎn)數(shù)n作歸納.n5時(shí),結(jié)論顯然.若n-1個(gè)頂點(diǎn)時(shí)結(jié)論成立.下證有n個(gè)頂點(diǎn)時(shí)結(jié)論也成立.由于G是平面圖,則(G)5.故在G中至少存在一個(gè)頂點(diǎn)v0,其度數(shù)d(v0)5.在圖中刪去頂點(diǎn)v0得圖G’,由歸納假設(shè)知G’的色素為5.然后將v0又加回去,有兩種情況:(1)d(v0)<5或d(v0)=5但和v0鄰接的5個(gè)結(jié)點(diǎn)的顏色數(shù)小于5.則v0極易著色,只要選擇與四周頂點(diǎn)不同的顏色著色即可.第6頁，共10頁，2023年，2月20日，星期三(2)d(v0)=5且和v0鄰接著的5個(gè)結(jié)點(diǎn)著的顏色的是5種顏色,如下圖(a)所示.稱G’中所有紅黃色頂點(diǎn)為紅黃集,稱G’中所有黑白色頂點(diǎn)為黑白集.故又有兩種可能.(i)v1和v3屬于紅黃集導(dǎo)出子圖的兩個(gè)不同塊中,如下圖(b)所示.將v1所在塊的紅黃色對調(diào),并不影響G’的正常著色.然后將v0著上紅色,即的圖G的正常著色.藍(lán)v3

黑v4v0黃v3白v2紅v1(a)(b)第7頁，共10頁，2023年，2月20日，星期三(ii)v1和v3屬于紅黃集導(dǎo)出子圖的同一塊中,則v1和v3之間必有一條屬于紅黃集的路P,P加上結(jié)點(diǎn)v0可構(gòu)成圈C:v0v1pv3v0,如下圖?所示.由于C的存在,將黑白集分成兩個(gè)子集,一個(gè)在C內(nèi),一個(gè)在C外.于是問題轉(zhuǎn)化為(i)的類型,對黑白集按(i)型的辦法處理,即得圖G的正常著色.藍(lán)v3

黑v4v0黃v3白v2紅v1(b)(c)(a)第8頁，共10頁，2023年，2月20日，星期三例1求下圖G和H的色數(shù)acfgbedGHa:紅,b:藍(lán),c:綠,d:紅,e:綠，f:藍(lán),g:紅(3色)第9頁，共10頁，2023年，2月20日，星期三例2.由n(n3)個(gè)頂點(diǎn)v1,v2,…,vn以及邊{v1,v2},{v2,v3},…,{vn-1,vn}{vn,v1}組成的圖稱為圈圖,記作Cn,試問圈圖的Cn的色數(shù)是多少。（分n為奇數(shù)，或偶數(shù)）例3.Kn和Km,n的色數(shù)分別是多少？