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

《圖論課件--圖的頂點(diǎn)著色》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

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

2、學(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,AC;A7:GT,MA,LA;A8:LA,GT,S;A9:AC,S,LA;3A10:GT,S。把課程模型為圖G的頂點(diǎn)，兩頂點(diǎn)連線當(dāng)且僅當(dāng)有某個(gè)學(xué)生同時(shí)選了這兩門課程。GTMAGACLAS選課狀態(tài)圖4如果我們用同一顏色給同一時(shí)段的課程頂點(diǎn)染色，那么，問題轉(zhuǎn)化為在狀態(tài)圖中求所謂的點(diǎn)色數(shù)問題。GTMAGACLAS選課狀態(tài)圖5定義1設(shè)G是一個(gè)圖，對(duì)G的每個(gè)頂點(diǎn)著色，使得相鄰頂點(diǎn)

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

4、數(shù)種顏色對(duì)圖G正常著色，稱為對(duì)圖G的最優(yōu)點(diǎn)著色。定義2色數(shù)為k的圖稱為k色圖。(二)、圖的點(diǎn)色數(shù)的幾個(gè)結(jié)論定理1對(duì)任意的圖G，有：分析：事實(shí)上，定理結(jié)論容易想到，因?yàn)槿我庖粋€(gè)頂點(diǎn)度數(shù)至多為Δ，因此，正常著色過程中，其鄰點(diǎn)最多用去Δ種顏色，所以，至少還有一種色可供該點(diǎn)正常著色使用。8證明：我們對(duì)頂點(diǎn)數(shù)作數(shù)學(xué)歸納證明。當(dāng)n=1時(shí)，結(jié)論顯然成立。設(shè)對(duì)頂點(diǎn)數(shù)少于n的圖來說，定理結(jié)論成立?？紤]一般的n階圖G。任取v∈V(G),令G1=G-v，由歸納假設(shè)：設(shè)п是G1的一種Δ(G)+1正常點(diǎn)著色方案，因?yàn)関的鄰點(diǎn)在п下至多用去Δ(G)

5、種色，所以給v染上其鄰點(diǎn)沒有用過的色，就把п擴(kuò)充成了G的Δ(G)+1著色方案。對(duì)于G來說，可以給出其Δ(G)+1正常點(diǎn)著色算法。9G的Δ(G)+1正常點(diǎn)著色算法設(shè)G=(V,E),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,5｝11v5v4v3v2v1v6v5(2)v4

6、(1)v3(3)v2(2)v1(1)v6(4)12v5v4v3v2v1v6注:(1)不能通過上面算法求出色數(shù)，例如，根據(jù)上面算法，我們求出了一個(gè)4色方案，但G是3色圖：(2)Welsh—Powell稍微對(duì)上面算法做了一個(gè)修改，著色時(shí)按所謂最大度優(yōu)先策略，即使用上面算法時(shí)，按頂點(diǎn)度數(shù)由大到小的次序著色。這樣的著色方案起到了對(duì)上面算法的一個(gè)改進(jìn)作用。13對(duì)于簡(jiǎn)單圖G來說，數(shù)學(xué)家布魯克斯(Brooks)給出了一個(gè)對(duì)定理1的色數(shù)改進(jìn)界。這就是下面著名的布魯克斯定理。定理2(布魯克斯，1941)若G是連通的單圖，并且它既不是奇圈，

7、又不是完全圖，則：數(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)單非正則連通單圖來說，結(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)著色的；若

8、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)單圖，且不是完全圖或奇