圖論課件圖的頂點(diǎn)著色

1、 圖論及其應(yīng)用1本次課主要內(nèi)容(一)、相關(guān)概念(二)、圖的點(diǎn)色數(shù)的幾個(gè)結(jié)論(三)、四色與五色定理圖的頂點(diǎn)著色(四)、頂點(diǎn)著色的應(yīng)用2 跟圖的邊著色問(wèn)題一樣，生活中的很多問(wèn)題，也可以模型為所謂的圖的頂點(diǎn)著色問(wèn)題來(lái)處理。例如課程安排問(wèn)題。(一)、相關(guān)概念 課程安排問(wèn)題：某大學(xué)數(shù)學(xué)系要為這個(gè)夏季安排課程表。所要開(kāi)設(shè)的課程為：圖論(GT), 統(tǒng)計(jì)學(xué)(S),線性代數(shù)(LA), 高等微積分(AC), 幾何學(xué)(G), 和近世代數(shù)(MA)?，F(xiàn)有10名學(xué)生(如下所示)需要選修這些課程。根據(jù)這些信息，確定開(kāi)設(shè)這些課程所需要的最少時(shí)間段數(shù)，使得學(xué)生選課不會(huì)發(fā)生沖突。(學(xué)生用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的頂點(diǎn)，兩頂點(diǎn)連線當(dāng)且僅當(dāng)有某個(gè)學(xué)生同時(shí)選了這兩門(mén)課程。GTMAGACLAS選課狀態(tài)圖4 如果我們用同一顏色給同一時(shí)段的課程頂點(diǎn)染色，那么，問(wèn)題轉(zhuǎn)化為在狀態(tài)圖中求所謂的點(diǎn)色數(shù)問(wèn)題。GTMAGACLAS選課狀態(tài)圖5 定義1 設(shè)G是一個(gè)圖，對(duì)G的每個(gè)頂點(diǎn)著色，使得相鄰頂點(diǎn)著不同顏色，稱為對(duì)G的正常頂點(diǎn)著色； 如果用k種顏色可

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

4、 定理1 對(duì)任意的圖G，有： 分析：事實(shí)上，定理結(jié)論容易想到，因?yàn)槿我庖粋€(gè)頂點(diǎn)度數(shù)至多為，因此，正常著色過(guò)程中，其鄰點(diǎn)最多用去種顏色，所以，至少還有一種色可供該點(diǎn)正常著色使用。8 證明：我們對(duì)頂點(diǎn)數(shù)作數(shù)學(xué)歸納證明。 當(dāng)n=1時(shí)，結(jié)論顯然成立。 設(shè)對(duì)頂點(diǎn)數(shù)少于n的圖來(lái)說(shuō)，定理結(jié)論成立。考慮一般的n階圖G。 任取v V(G), 令G1=G-v， 由歸納假設(shè)： 設(shè)是G1的一種(G)+1正常點(diǎn)著色方案，因?yàn)関的鄰點(diǎn)在下至多用去(G)種色，所以給v染上其鄰點(diǎn)沒(méi)有用過(guò)的色，就把擴(kuò)充成了G的(G)+1著色方案。 對(duì)于G來(lái)說(shuō)，可以給出其(G)+1正常點(diǎn)著色算法。9G的(G)+1正常點(diǎn)著色算法 設(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正常點(diǎn)著色。v5v4v3v2v1v6 解：色集C=1, 2, 3, 4, 511v5v4v3v2v1v6v5(2)v4(1)v3(3)v2(2)v1(1)v6(4)12v5v4v3v2v1v6 注: (1)不能通過(guò)上面算法求出色數(shù)，例如，根據(jù)上面算法，我們求出了一個(gè)4色方案，但G是3色圖： (2) WelshPowell稍微對(duì)上面算法做了一個(gè)修改，著色時(shí)按所謂

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

7、通單圖來(lái)說(shuō)，結(jié)論成立。假設(shè)G是階數(shù)為n的非正則連通單圖。 設(shè)u是G中頂點(diǎn)，且d(u)=，考慮G1=G-u 若G1是正則單圖，則(G1)=(G)-1。于是G1是可(G)頂點(diǎn)正常著色的，從而，G是可(G)正常頂點(diǎn)著色的； 若G1是非正則單圖，則由數(shù)學(xué)歸納，G1是可(G)頂點(diǎn)正常著色的，從而，G是可(G)正常頂點(diǎn)著色的。 (2) 容易證明：若G是1連通單圖，最大度是，則15 (3) (G)3 若不然，結(jié)合(2), G為圈。因G不是奇圈，所以定理結(jié)論顯然成立。 所以，下面只需證明：假設(shè)G是正則的，2連通的，最大度3的簡(jiǎn)單圖，且不是完全圖或奇圈，有： 分兩步完成證明。 1) 在上面條件下，我們證明：G中

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

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

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

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

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

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

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

15、此，可以擴(kuò)充為G的5正常頂點(diǎn)著色。30(四)、頂點(diǎn)著色的應(yīng)用 圖的正常頂點(diǎn)著色對(duì)應(yīng)的實(shí)際問(wèn)題是“劃分”問(wèn)題。 例1 課程安排問(wèn)題：某大學(xué)數(shù)學(xué)系要為這個(gè)夏季安排課程表。所要開(kāi)設(shè)的課程為：圖論(GT), 統(tǒng)計(jì)學(xué)(S),線性代數(shù)(LA), 高等微積分(AC), 幾何學(xué)(G), 和近世代數(shù)(MA)?，F(xiàn)有10名學(xué)生(如下所示)需要選修這些課程。根據(jù)這些信息，確定開(kāi)設(shè)這些課程所需要的最少時(shí)間段數(shù)，使得學(xué)生選課不會(huì)發(fā)生沖突。(學(xué)生用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的頂點(diǎn)，兩頂點(diǎn)連線當(dāng)且僅當(dāng)有某個(gè)學(xué)生同時(shí)選了這兩門(mén)課程。GTMAGACLAS選課狀態(tài)圖32 如果我們用同一顏色給同一時(shí)段的課程頂點(diǎn)染色，那么，問(wèn)題轉(zhuǎn)化為在狀態(tài)圖中求對(duì)應(yīng)于點(diǎn)色數(shù)的著色。 (1) 求點(diǎn)色數(shù) 一方面，因圖中含有奇圈(紅色邊), 所以，點(diǎn)色數(shù)至少為3。又因?yàn)辄c(diǎn)LA與該圈上每一個(gè)點(diǎn)均鄰接，所以，點(diǎn)色數(shù)至少為4.GTMAGACLAS選課狀態(tài)圖 另一方面，我們用4種色實(shí)現(xiàn)了G的正常點(diǎn)著色，所以，圖的點(diǎn)色數(shù)為4.33 (2) 求安排-具體著色GTMAGACLAS選課狀態(tài)圖34 例2 交通燈的相位設(shè)置問(wèn)題：如圖所示，列出了繁華街道路口處的交通車道L1,L2,L9。在此路口處安置了交通燈。當(dāng)交通燈處于某個(gè)相位時(shí)，亮綠燈的車道上的車輛就可以安全通過(guò)路口。為了(最終)讓所有的車輛的燈都能夠安全通過(guò)