圖論課件圖的頂點著色

圖論課件圖的頂點著色1第1頁，共39頁，2023年，2月20日，星期六本次課主要內容(一)、相關概念(二)、圖的點色數(shù)的幾個結論(三)、四色與五色定理圖的頂點著色(四)、頂點著色的應用2第2頁，共39頁，2023年，2月20日，星期六跟圖的邊著色問題一樣，生活中的很多問題，也可以模型為所謂的圖的頂點著色問題來處理。例如課程安排問題。(一)、相關概念課程安排問題：某大學數(shù)學系要為這個夏季安排課程表。所要開設的課程為：圖論(GT),統(tǒng)計學(S),線性代數(shù)(LA),高等微積分(AC),幾何學(G),和近世代數(shù)(MA)。現(xiàn)有10名學生(如下所示)需要選修這些課程。根據(jù)這些信息，確定開設這些課程所需要的最少時間段數(shù)，使得學生選課不會發(fā)生沖突。(學生用Ai表示）

A1:LA,S;A2:MA,LA,G;A3:MA,G,LA;

A4:G,LA,AC;A5:AC,LA,S;A6:G,AC;

A7:GT,MA,LA;A8:LA,GT,S;A9:AC,S,LA;3第3頁，共39頁，2023年，2月20日，星期六

A10:GT,S。把課程模型為圖G的頂點，兩頂點連線當且僅當有某個學生同時選了這兩門課程。GTMAGACLAS選課狀態(tài)圖4第4頁，共39頁，2023年，2月20日，星期六如果我們用同一顏色給同一時段的課程頂點染色，那么，問題轉化為在狀態(tài)圖中求所謂的點色數(shù)問題。GTMAGACLAS選課狀態(tài)圖5第5頁，共39頁，2023年，2月20日，星期六定義1設G是一個圖，對G的每個頂點著色，使得相鄰頂點著不同顏色，稱為對G的正常頂點著色；如果用k種顏色可以對G進行正常頂點著色，稱G可k正常頂點著色；對圖G正常頂點著色需要的最少顏色數(shù)，稱為圖G的點色數(shù)。圖G的點色數(shù)用表示。例1說明下圖的點色數(shù)是4。GTMAGACLAS6第6頁，共39頁，2023年，2月20日，星期六解：一方面，由圖的結構特征容易知道另一方面，通過具體著色，用4種顏色可以得到該圖的一種正常點著色，則：GTMAGACLAS所以，7第7頁，共39頁，2023年，2月20日，星期六注：對圖的正常頂點著色，帶來的是圖的頂點集合的一種劃分方式。所以，對應的實際問題也是分類問題。屬于同一種顏色的頂點集合稱為一個色組，它們彼此不相鄰接，所以又稱為點獨立集。用點色數(shù)種顏色對圖G正常著色，稱為對圖G的最優(yōu)點著色。定義2色數(shù)為k的圖稱為k色圖。(二)、圖的點色數(shù)的幾個結論定理1對任意的圖G，有：分析：事實上，定理結論容易想到，因為任意一個頂點度數(shù)至多為Δ，因此，正常著色過程中，其鄰點最多用去Δ種顏色，所以，至少還有一種色可供該點正常著色使用。8第8頁，共39頁，2023年，2月20日，星期六證明：我們對頂點數(shù)作數(shù)學歸納證明。當n=1時，結論顯然成立。設對頂點數(shù)少于n的圖來說，定理結論成立?？紤]一般的n階圖G。任取v∈V(G),令G1=G-v，由歸納假設：設п是G1的一種Δ(G)+1正常點著色方案，因為v的鄰點在п下至多用去Δ(G)種色，所以給v染上其鄰點沒有用過的色，就把п擴充成了G的Δ(G)+1著色方案。對于G來說，可以給出其Δ(G)+1正常點著色算法。9第9頁，共39頁，2023年，2月20日，星期六G的Δ(G)+1正常點著色算法

設G=(V,E),V=｛v1,v2,…,vn｝,色集合C=｛1,2,…,Δ+1｝,著色方案為п。(1)令п(v1)=1,i=1;(2)若i=n,則停止；否則令：

設k為C-C(vi+1)中的最小整數(shù)，令(3)令i=i+1,轉(2)。10第10頁，共39頁，2023年，2月20日，星期六

例2給出下圖的Δ+1正常點著色。v5v4v3v2v1v6

解：色集C=｛1,2,3,4,5｝11第11頁，共39頁，2023年，2月20日，星期六v5v4v3v2v1v6v5(2)v4(1)v3(3)v2(2)v1(1)v6(4)12第12頁，共39頁，2023年，2月20日，星期六v5v4v3v2v1v6

注:(1)不能通過上面算法求出色數(shù)，例如，根據(jù)上面算法，我們求出了一個4色方案，但G是3色圖：

(2)Welsh—Powell稍微對上面算法做了一個修改，著色時按所謂最大度優(yōu)先策略，即使用上面算法時，按頂點度數(shù)由大到小的次序著色。這樣的著色方案起到了對上面算法的一個改進作用。13第13頁，共39頁，2023年，2月20日，星期六

對于簡單圖G來說，數(shù)學家布魯克斯(Brooks)給出了一個對定理1的色數(shù)改進界。這就是下面著名的布魯克斯定理。

定理2(布魯克斯，1941)若G是連通的單圖，并且它既不是奇圈，又不是完全圖，則：

數(shù)學家羅瓦斯在1973年給出了如下證明。

證明：不失一般性，我們可以假設G是正則的，2連通的，最大度Δ≥3的簡單圖。原因如下：(1)容易證明：若G是非正則連通單圖，最大度是Δ，則

事實上，我們可以對G的頂點數(shù)作數(shù)學歸納證明：14第14頁，共39頁，2023年，2月20日，星期六

當n=1時，結論顯然成立；

設對于階數(shù)小于n的簡單非正則連通單圖來說，結論成立。假設G是階數(shù)為n的非正則連通單圖。

設u是G中頂點，且d(u)=δ<Δ，考慮G1=G-u

若G1是正則單圖，則Δ(G1)=Δ(G)-1。于是G1是可Δ(G)頂點正常著色的，從而，G是可Δ(G)正常頂點著色的；

若G1是非正則單圖，則由數(shù)學歸納，G1是可Δ(G)頂點正常著色的，從而，G是可Δ(G)正常頂點著色的。(2)容易證明：若G是1連通單圖，最大度是Δ，則15第15頁，共39頁，2023年，2月20日，星期六(3)Δ(G)≥3

若不然，結合(2),G為圈。因G不是奇圈，所以定理結論顯然成立。

所以，下面只需證明：假設G是正則的，2連通的，最大度Δ≥3的簡單圖，且不是完全圖或奇圈，有：

分兩步完成證明。1)在上面條件下，我們證明：G中存在三點x1,x2,xn,使得G-｛x1,x2｝連通，x1與x2不鄰接，但x1,x2與xn均鄰接；16第16頁，共39頁，2023年，2月20日，星期六

情形1設G是3連通的正則非完全圖。

對于G中點xn,顯然在其鄰點中存在兩個不鄰接頂點x1與x2,使得G-｛x1,x2｝連通。

情形2設G是連通度為2的正則非完全圖。

此時，存在點xn,使得G-xn連通且有割點v,于是G-xn至少含有兩個塊。vG-v塊塊塊17第17頁，共39頁，2023年，2月20日，星期六

由于G本身2連通，所以G-xn的每個僅含有一個割點的塊中均有點與xn鄰接。設分屬于H1與H2中的點x1與x2，它們與xn鄰接。由于x1與x2分屬于不同塊，所以x1與x2不鄰接。又因為Δ≥3，所以G-｛x1,x2｝連通。2)對G中頂點進行如下排序：

令xn-1∈V(G)-｛x1,x2,xn｝且與xn鄰接；xn-2∈V(G)-｛x1,x2,xn，xn-1｝且與xn或xn-1鄰接；xn-3∈V(G)-｛x1,x2,xn，xn-1,xn-2｝且與xn或xn-1或xn-2鄰接；

不斷這樣作下去，可得到G的頂點排序：x1,x2,…,xn18第18頁，共39頁，2023年，2月20日，星期六

該頂點序列的特征是，對于1≦i≦n-1,xi與某個xi+k鄰接。

把著色算法用于G，按照上面頂點排序著色，容易知道，用Δ(G)種顏色可以完成G的正常點著色。

對于簡單圖的點色數(shù)，還可以在定理2的基礎上獲得改進。定義3設G是至少有一條邊的簡單圖，定義：其中N(u)為G中點u的鄰域。稱Δ2(G)為G的次大度。19第19頁，共39頁，2023年，2月20日，星期六

如果令：那么，例如：求下面圖的次大度Δ2(G)G1G220第20頁，共39頁，2023年，2月20日，星期六

解：(1)G1v5v4v3v2v1G2v5v4v3v2v1v8v7v6v9(2)21第21頁，共39頁，2023年，2月20日，星期六G2v5v4v3v2v1v8v7v6v9

注：由次大度的定義知：Δ2(G)≦Δ(G)

定理3設G是非空簡單圖，則：

注：定理3是對定理2的一個改進！22第22頁，共39頁，2023年，2月20日，星期六G2v5v4v3v2v1v8v7v6v9

例如：對下面單圖來說，由定理2得：

而由定理3得：

推論：設G是非空簡單圖，若G中最大度點互不鄰接，則有：23第23頁，共39頁，2023年，2月20日，星期六

1、四色定理(三)、四色與五色定理1852年，剛畢業(yè)于倫敦大學的格斯里(1831—1899)發(fā)現(xiàn)：給一張平面地圖正常著色，至少需要4種顏色。這就是著名的4色定理。格斯里把他的證明通過他弟弟轉交給著名數(shù)學家摩爾根，引起摩爾根極大興趣并于當天給數(shù)學家哈密爾頓寫了封相關信件。但沒有引起哈密爾頓的注意。直到1878年，在英國數(shù)學會議上，數(shù)學家凱萊才再一次提到4色問題。24第24頁，共39頁，2023年，2月20日，星期六1879年7月，業(yè)余數(shù)學家肯普(1849---1922）在英國自然雜志上宣稱證明了4色定理。肯普是凱萊在劍橋大學的學生。

1890年，英國數(shù)學家希五德發(fā)表文章地圖染色定理，通過構造反例，指出了肯普證明中的缺陷。后來，西五德一直研究4色問題60年。泰特在此期間也研究4色問題，但其證明被托特否定。希五德文章之后，4色問題研究進程開始走向停滯。到了20世紀，美國數(shù)學家比爾荷夫提出可約性概念，在此基礎上，德國數(shù)學家Heesch(1906—1995)認為，可以通過尋找所謂的不可約構形來證明4色定理。25第25頁，共39頁，2023年，2月20日，星期六Heesch估計不可約構形集合可能包含10000個元素，手工驗證是不太可能。于是他給出了一種可用計算機來驗證的方法。20世紀70年代，Haken和他的學生Appel著力用計算機方法證明4色定理，借助于Appel在編程方面的深厚功底。他們于1976年6月終于成功解決了尋找不可約構形集合中的元素，宣告4色定理的成功證明。數(shù)學家托特在圖論頂級刊物《圖論雜志》上寫了一首詩：WolfgangHaken

重重打擊著巨妖

一次！兩次！三次！四次！

他說：“妖怪已經(jīng)不存在了.”26第26頁，共39頁，2023年，2月20日，星期六

2、五色定理

定理4(希五德)每個平面圖是5可著色的。

根據(jù)平面圖和其對偶圖的關系，上面定理等價于每個平面圖是5可頂點正常著色的。

證明：我們對圖的頂點作數(shù)學歸納證明。

當n=1時，結論顯然。

設n=k時，結論成立?？紤]n=k+1的平面圖G。

因G是平面圖，所以δ(G)≦5

設d(u)=δ(G)≦5。27第27頁，共39頁，2023年，2月20日，星期六

令G1=G–u。由歸納假設，G1是5可頂點正常著色的。設п是G1的5著色方案。(1)如果d(u)=δ(G)<5,顯然п可以擴充為G的5正常頂點著色；

(2)如果d(u)=δ(G)=5,分兩種情況討論。

情形1在п下，如果u的鄰接點中，至少有兩個頂點著相同顏色，則容易知道，п可以擴充為G的5正常頂點著色；

情形2在п下，設u的鄰接點中，5個頂點著了5種不同顏色。28第28頁，共39頁，2023年，2月20日，星期六

不失一般性，設п(xi)=i(1≦i≦5)。x5x4x3x2x1u

設H(i,j)表示著i和j色的點在G1中的點導出子圖。

如果x1與x3屬于H(1,3)的不同分支。則通過交換含x1的分支中的著色順序，可得到G1的新正常點著色方案，使x1與x3著同色，于是由情形1，可以得到G的5正常頂點著色方案；29第29頁，共39頁，2023年，2月20日，星期六

設x1與x3屬于H(1,3)的相同分支。x5x4x3x2x1u3131

在上面假設下，x2與x4必屬于H(2,4)的不同分支。否則，將會得到H(1,3)與H(2,4)的交叉點。因此，п可以擴充為G的5正常頂點著色。30第30頁，共39頁，2023年，2月20日，星期六(四)、頂點著色的應用

圖的正常頂點著色對應的實際問題是“劃分”問題。例1課程安排問題：某大學數(shù)學系要為這個夏季安排課程表。所要開設的課程為：圖論(GT),統(tǒng)計學(S),線性代數(shù)(LA),高等微積分(AC),幾何學(G),和近世代數(shù)(MA)?，F(xiàn)有10名學生(如下所示)需要選修這些課程。根據(jù)這些信息，確定開設這些課程所需要的最少時間段數(shù)，使得學生選課不會發(fā)生沖突。(學生用Ai表示）

A1:LA,S;A2:MA,LA,G;A3:MA,G,LA;

A4:G,LA,AC;A5:AC,LA,S;A6:G,AC;

A7:GT,MA,LA;A8:LA,GT,S;A9:AC,S,LA;31第31頁，共39頁，2023年，2月20日，星期六

A10:GT,S。解：把課程模型為圖G的頂點，兩頂點連線當且僅當有某個學生同時選了這兩門課程。GTMAGACLAS選課狀態(tài)圖32第32頁，共39頁，2023年，2月20日，星期六如果我們用同一顏色給同一時段的課程頂點染色，那么，問題轉化為在狀態(tài)圖中求對應于點色數(shù)的著色。

(1)求點色數(shù)一方面，因圖中含有奇圈(紅色邊),所以，點色數(shù)至少為3。又因為點