圖論課件圖的頂點著色

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

2、 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 A10: GT, S。 把課程模型為圖G的頂點，兩頂點連線當且僅當有某個學生同時選了這兩門課程。GTMAGACLAS選課狀態(tài)圖4 如果我們用同一顏色給同一時段的課程頂點染色，那么，問題轉(zhuǎn)化為在狀態(tài)圖中求所謂的點色數(shù)問題。GTMAGACLAS選課狀態(tài)圖5 定義1 設(shè)G是一個圖，對G的每個頂點著色，使得相鄰頂點著不同顏色，稱為對G的正常頂點著色； 如果用k種顏色可

3、以對G進行正常頂點著色，稱G可k正常頂點著色； 對圖G正常頂點著色需要的最少顏色數(shù)，稱為圖G的點色數(shù)。圖G的點色數(shù)用 表示。 例1 說明下圖的點色數(shù)是4。GTMAGACLAS6 解：一方面，由圖的結(jié)構(gòu)特征容易知道 另一方面，通過具體著色，用4種顏色可以得到該圖的一種正常點著色，則：GTMAGACLAS 所以，7 注：對圖的正常頂點著色，帶來的是圖的頂點集合的一種劃分方式。所以，對應的實際問題也是分類問題。屬于同一種顏色的頂點集合稱為一個色組，它們彼此不相鄰接，所以又稱為點獨立集。用點色數(shù)種顏色對圖G正常著色，稱為對圖G的最優(yōu)點著色。 定義2 色數(shù)為k的圖稱為k色圖。(二)、圖的點色數(shù)的幾個結(jié)論

4、 定理1 對任意的圖G，有： 分析：事實上，定理結(jié)論容易想到，因為任意一個頂點度數(shù)至多為，因此，正常著色過程中，其鄰點最多用去種顏色，所以，至少還有一種色可供該點正常著色使用。8 證明：我們對頂點數(shù)作數(shù)學歸納證明。 當n=1時，結(jié)論顯然成立。 設(shè)對頂點數(shù)少于n的圖來說，定理結(jié)論成立?？紤]一般的n階圖G。 任取v V(G), 令G1=G-v， 由歸納假設(shè)： 設(shè)是G1的一種(G)+1正常點著色方案，因為v的鄰點在下至多用去(G)種色，所以給v染上其鄰點沒有用過的色，就把擴充成了G的(G)+1著色方案。 對于G來說，可以給出其(G)+1正常點著色算法。9G的(G)+1正常點著色算法 設(shè)G=(V, E

5、), V=v1,v2,vn,色集合C=1,2,+1,著色方案為。 (1) 令(v1)=1, i=1; (2) 若i=n,則停止；否則令： 設(shè)k為C-C(vi+1)中的最小整數(shù)，令 (3) 令i=i+1,轉(zhuǎn)(2)。10 例2 給出下圖的+1正常點著色。v5v4v3v2v1v6 解：色集C=1, 2, 3, 4, 511v5v4v3v2v1v6v5(2)v4(1)v3(3)v2(2)v1(1)v6(4)12v5v4v3v2v1v6 注: (1)不能通過上面算法求出色數(shù)，例如，根據(jù)上面算法，我們求出了一個4色方案，但G是3色圖： (2) WelshPowell稍微對上面算法做了一個修改，著色時按所謂

6、最大度優(yōu)先策略，即使用上面算法時，按頂點度數(shù)由大到小的次序著色。這樣的著色方案起到了對上面算法的一個改進作用。13 對于簡單圖G來說，數(shù)學家布魯克斯(Brooks)給出了一個對定理1的色數(shù)改進界。這就是下面著名的布魯克斯定理。 定理2(布魯克斯，1941) 若G是連通的單圖，并且它既不是奇圈，又不是完全圖，則： 數(shù)學家羅瓦斯在1973年給出了如下證明。 證明：不失一般性，我們可以假設(shè)G是正則的，2連通的，最大度3的簡單圖。原因如下： (1) 容易證明：若G是非正則連通單圖，最大度是，則 事實上，我們可以對G的頂點數(shù)作數(shù)學歸納證明：14 當n=1時，結(jié)論顯然成立； 設(shè)對于階數(shù)小于n的簡單非正則連

7、通單圖來說，結(jié)論成立。假設(shè)G是階數(shù)為n的非正則連通單圖。 設(shè)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 (3) (G)3 若不然，結(jié)合(2), G為圈。因G不是奇圈，所以定理結(jié)論顯然成立。 所以，下面只需證明：假設(shè)G是正則的，2連通的，最大度3的簡單圖，且不是完全圖或奇圈，有： 分兩步完成證明。 1) 在上面條件下，我們證明：G中

8、存在三點x1, x2, xn,使得G -x1, x2連通，x1與x2不鄰接，但x1, x2與xn均鄰接；16 情形1 設(shè)G是3連通的正則非完全圖。 對于G中點xn, 顯然在其鄰點中存在兩個不鄰接頂點x1與x2, 使得G-x1, x2連通。 情形2 設(shè)G是連通度為2的正則非完全圖。 此時，存在點xn,使得G-xn連通且有割點v, 于是G-xn至少含有兩個塊。vG -v塊塊塊17 由于G本身2連通，所以G-xn的每個僅含有一個割點的塊中均有點與xn鄰接。設(shè)分屬于H1與H2中的點x1與x2，它們與xn鄰接。由于x1與x2分屬于不同塊，所以x1與x2不鄰接。又因為3，所以G-x1, x2連通。 2)

9、對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 該頂點序列的特征是，對于1in-1,xi與某個xi+k鄰接。 把著色算法用于G，按照上面頂點排序著色，容易知道，用(G)種顏色可以完成G的正常點著色。 對于簡單圖的點色數(shù)，還可以在定理2的基礎(chǔ)上獲得改進。 定義3 設(shè)G是至少有一條邊的簡單圖，定義： 其中N(u)為G中點u的鄰域。稱2(

10、G)為G的次大度。19 如果令： 那么， 例如：求下面圖的次大度2(G)G1G220 解：(1) G1v5v4v3v2v1G2v5v4v3v2v1v8v7v6v9 (2) 21G2v5v4v3v2v1v8v7v6v9 注：由次大度的定義知：2(G)(G) 定理3 設(shè)G是非空簡單圖，則： 注：定理3是對定理2的一個改進！22G2v5v4v3v2v1v8v7v6v9 例如：對下面單圖來說，由定理2得： 而由定理3得： 推論：設(shè)G是非空簡單圖，若G中最大度點互不鄰接，則有：23 1、四色定理(三)、四色與五色定理 1852年，剛畢業(yè)于倫敦大學的格斯里(18311899)發(fā)現(xiàn)：給一張平面地圖正常著色，

11、至少需要4種顏色。這就是著名的4色定理。 格斯里把他的證明通過他弟弟轉(zhuǎn)交給著名數(shù)學家摩爾根，引起摩爾根極大興趣并于當天給數(shù)學家哈密爾頓寫了封相關(guān)信件。但沒有引起哈密爾頓的注意。 直到1878年，在英國數(shù)學會議上，數(shù)學家凱萊才再一次提到4色問題。24 1879年7月，業(yè)余數(shù)學家肯普(1849-1922）在英國自然雜志上宣稱證明了4色定理。肯普是凱萊在劍橋大學的學生。 1890年，英國數(shù)學家希五德發(fā)表文章地圖染色定理，通過構(gòu)造反例，指出了肯普證明中的缺陷。后來，西五德一直研究4色問題60年。 泰特在此期間也研究4色問題，但其證明被托特否定。 希五德文章之后，4色問題研究進程開始走向停滯。 到了20

12、世紀，美國數(shù)學家比爾荷夫提出可約性概念，在此基礎(chǔ)上，德國數(shù)學家Heesch(19061995)認為，可以通過尋找所謂的不可約構(gòu)形來證明4色定理。25 Heesch估計不可約構(gòu)形集合可能包含10000個元素，手工驗證是不太可能。于是他給出了一種可用計算機來驗證的方法。 20世紀70年代，Haken和他的學生Appel著力用計算機方法證明4色定理，借助于Appel在編程方面的深厚功底。他們于1976年6月終于成功解決了尋找不可約構(gòu)形集合中的元素，宣告4色定理的成功證明。數(shù)學家托特在圖論頂級刊物圖論雜志上寫了一首詩： Wolfgang Haken 重重打擊著巨妖 一次！兩次！三次！四次！ 他說：“妖

13、怪已經(jīng)不存在了.”26 2、五色定理 定理4 (希五德) 每個平面圖是5可著色的。 根據(jù)平面圖和其對偶圖的關(guān)系，上面定理等價于每個平面圖是5可頂點正常著色的。 證明：我們對圖的頂點作數(shù)學歸納證明。 當n=1時，結(jié)論顯然。 設(shè)n=k時，結(jié)論成立?？紤]n=k+1的平面圖G。 因G是平面圖，所以(G)5 設(shè)d(u)=(G)5。27 令G1=G u。由歸納假設(shè)，G1是5可頂點正常著色的。設(shè)是G1的5著色方案。 (1) 如果d(u)=(G)5, 顯然可以擴充為G的5正常頂點著色； (2) 如果d(u)=(G) = 5, 分兩種情況討論。 情形1 在下，如果u的鄰接點中，至少有兩個頂點著相同顏色，則容易知

14、道，可以擴充為G的5正常頂點著色； 情形2 在下，設(shè)u的鄰接點中，5個頂點著了5種不同顏色。28 不失一般性，設(shè)(xi)=i (1i5)。x5x4x3x2x1u 設(shè)H (i, j)表示著i和j色的點在G1中的點導出子圖。 如果x1與x3屬于H(1, 3) 的不同分支。則通過交換含x1的分支中的著色順序，可得到G1的新正常點著色方案，使x1與x3著同色，于是由情形1，可以得到G的5正常頂點著色方案；29 設(shè)x1與x3屬于H(1, 3) 的相同分支。x5x4x3x2x1u3131 在上面假設(shè)下，x2與x4必屬于H(2, 4) 的不同分支。否則，將會得到H(1, 3) 與H(2, 4) 的交叉點。因

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

16、C; A7: GT, MA, LA ; A8: LA,GT, S ; A9: AC, S, LA;31 A10: GT, S。 解：把課程模型為圖G的頂點，兩頂點連線當且僅當有某個學生同時選了這兩門課程。GTMAGACLAS選課狀態(tài)圖32 如果我們用同一顏色給同一時段的課程頂點染色，那么，問題轉(zhuǎn)化為在狀態(tài)圖中求對應于點色數(shù)的著色。 (1) 求點色數(shù) 一方面，因圖中含有奇圈(紅色邊), 所以，點色數(shù)至少為3。又因為點LA與該圈上每一個點均鄰接，所以，點色數(shù)至少為4.GTMAGACLAS選課狀態(tài)圖 另一方面，我們用4種色實現(xiàn)了G的正常點著色，所以，圖的點色數(shù)為4.33 (2) 求安排-具體著色GTMAGACLAS選課狀態(tài)圖34 例2 交通燈的相位設(shè)置問題：如圖所示，列出了繁華街道路口處的交通車道L1,L2,L9。在此路口處安置了交通燈。當交通燈處于某個相位時，亮綠燈的車道上的車輛就可以安全通過路口。為了(最終)讓所有的車輛的燈都能夠安全通過