new-圖著色.ppt

1、1,圖的著色,一、圖的邊著色,二、圖的頂點著色,主要內(nèi)容,2,現(xiàn)實生活中很多問題，可以模型為所謂的邊著色問題來處理。例如排課表問題。,(一)、邊著色,排課表問題：設(shè)有m位教師，n個班級，其中教師xi要給班級yj上pij節(jié)課。求如何在最少節(jié)次排完所有課。,建模：令X=x1,x2,xm, Y=y1,y2,yn,xi與yj間連pij條邊，得偶圖G=(X, Y).,于是，問題轉(zhuǎn)化為如何在G中將邊集E劃分為互不相交的p個匹配，且使得p最小。,如果每個匹配中的邊用同一種顏色染色，不同匹配中的邊用不同顏色染色，則問題轉(zhuǎn)化為在G中給每條邊染色，相鄰邊染不同色，至少需要的顏色數(shù)。,3,這就需要我們研究所謂的邊著

2、色問題。,定義1 設(shè)G是圖，對G的邊進(jìn)行染色，若相鄰邊染不同顏色，則稱對G進(jìn)行正常邊著色；,如果能用k中顏色對圖G進(jìn)行正常邊著色，稱G是k邊可著色的。,定義2 設(shè)G是圖，對G進(jìn)行正常邊著色需要的最少顏色數(shù)，稱為G的邊色數(shù)，記為：,4,注：對圖的正常邊著色，實際上是對G的邊集合的一種劃分，使得每個劃分塊是G的一個邊獨立集(無環(huán)時是匹配);圖的邊色數(shù)對應(yīng)的是圖的最少獨立集劃分?jǐn)?shù)。,因此，圖的邊著色，本質(zhì)上是對應(yīng)實際問題中的“劃分”問題或“分類”問題。,5,(二)、幾類特殊圖的邊色數(shù),1、偶圖的邊色數(shù),定理1,證明：設(shè),又設(shè)=n。設(shè)顏色集合設(shè)為0，1，2，n-1, 是Km,n的一種n著色方案，滿足：

3、,6,我們證明：上面的著色是正常邊著色。,對K m, n中任意的兩條鄰接邊xiyj和xiyk。若,則：i+ j ( mod n)=i +k ( mod n),得到j(luò)=k，矛盾！,所以，上面著色是正常著色。所以：,又顯然 ，所以，,例1 用最少的顏色數(shù)對K3,4正常邊著色。,7,定理2 (哥尼，1916)若G是偶圖，則,8,定理3 (維津定理，1964) 若G是單圖，則：,注： 根據(jù)這個定理， 如果我們要證明某一個圖的邊染色數(shù)是， 只要我們找到了一種染色方式用的色數(shù)是就可以了。 如果要證明是 +1， 我們只需要證明用色不能正常染色。一般用反證法， 假設(shè)能用 染色， 得到矛盾。,9,注: (1)

4、根據(jù)維津定理，單圖可以按邊色數(shù)分成兩類圖，一是色數(shù)等于(G)的單圖，二是色數(shù)等于(G)+1的單圖。,(2) 維津(Vizing) : 1937年出生于烏克蘭的基輔。1954年開始在托木斯克大學(xué)學(xué)習(xí)數(shù)學(xué)，1959年大學(xué)畢業(yè)保送到莫斯科斯特克羅夫研究所攻讀博士學(xué)位，研究函數(shù)逼近論。但這不是他的興趣所在，因此沒有獲得學(xué)位。1966年在季科夫的指導(dǎo)下獲得博士學(xué)位。和大多數(shù)數(shù)學(xué)家一樣，維津在音樂方面具有一定才能。,10,維津在攻讀博士學(xué)位期間，發(fā)現(xiàn)并證明了上面的維津定理。他當(dāng)時把論文投向一家非常著名的雜志，但由于審稿人認(rèn)為問題本身沒有意義而遭到拒絕。后來在另外一家地方雜志發(fā)表時，定理早已出名。,維津認(rèn)為

5、：一名數(shù)學(xué)家應(yīng)該不斷研究與發(fā)現(xiàn)新結(jié)果，然后讓時間來檢驗其重要性。,11,定理 設(shè)G是單圖。若點數(shù)n=2k+1且邊數(shù)mk,則：,證明：若不然，由維津定理，,設(shè)是G的(G)正常邊著色方案，對于G的每個色組來說，包含的邊數(shù)至多(n-1)/2=k。這樣： ，與條件矛盾。,例3 確定下圖的邊色數(shù)。,解：由定理5：,12,定理6 設(shè)G是奇數(shù)階正則單圖,若0,則：,證明：設(shè)n=2k+1。因G是正則單圖，且0，所以：,例4 設(shè)n=2k+1,k0。求,由定理5：,解：由定理6知：,13,例5 求出彼得森圖的邊色數(shù)。,解：一方面，彼得森圖中去掉任意一個1因子后，剩下兩個5點圈，所以，不能進(jìn)行1因子分解，所以：,另

6、一方面：G的最大度數(shù) =3， 所以：,14,例6 (1) 設(shè)G=(X, Y)是一個最大度為的偶圖，求證，G是某個正則偶圖 G*的子圖。,(2) 用(1) 證明：偶圖的邊色數(shù)等于其最大度。,證明 (1) 按如下方式構(gòu)造G*。,如果G不是正則偶圖，先將G按下圖所示方式構(gòu)造成為G1,15,G (1)與G (2)分別是G的拷貝。,紅色 邊表示xi與xi(yi與yi)之間的一條連線，要求是d(xi)(d(yi),這樣得到的新偶圖就是G1。,如果G1是正則偶圖，則G*=G1,否則，在G1的基礎(chǔ)上，重復(fù)上面的過程，可得到G2,這樣不斷下去，最終得到包含G的正則偶圖G*。,(2) 由(1) 對于任意最大度為的

7、偶圖G,均存在G的正則母圖G*。又由于正則偶圖存在1因子分解，所以，G*可以劃分為個1因子，從而其邊色數(shù)為。這樣G的邊色數(shù)也為。,16,（二） 圖的頂點著色,17,定義1 設(shè)G是一個圖，對G的每個頂點著色，使得相鄰頂點著不同顏色，稱為對G的正常頂點著色；,如果用k種顏色可以對G進(jìn)行正常頂點著色，稱G可k正常頂點著色；,對圖G正常頂點著色需要的最少顏色數(shù)，稱為圖G的點色數(shù)。圖G的點色數(shù)用 表示。,例1 說明下圖的點色數(shù)是4。,下列命題成立：,G是有邊的兩分圖的充要條件是=2 G是無邊圖的充要條件是=1 G是完全圖的充要條件是=|V(G)| (輪）=3 （輪的頂點數(shù)是奇數(shù)）； 4（否則）,定理:對

8、任意的圖G 均有,頂點著色,定理:設(shè)G是連通圖。假定G既不是完全圖又不是奇圈，則,一個著色算法:Welsh-Powell算法,頂點著色,（1）將圖G的節(jié)點按度數(shù)遞減排列； （2）對第一個節(jié)點及其不鄰接的節(jié)點著第一個顏色； （3）對常未著色的第一個及其不鄰接的節(jié)點著第二個顏色；續(xù)行此法， 直到全部節(jié)點著色完為止。,用Welsh-Powell算法對下例中的點著色，結(jié)果如下圖所示。,頂點著色,22,1、四色定理,(三)、四色與五色定理,1852年，剛畢業(yè)于倫敦大學(xué)的格斯里(18311899)發(fā)現(xiàn)：給一張平面地圖正常著色，至少需要4種顏色。這就是著名的4色定理。,格斯里把他的證明通過他弟弟轉(zhuǎn)交給著名數(shù)

9、學(xué)家摩爾根，引起摩爾根極大興趣并于當(dāng)天給數(shù)學(xué)家哈密爾頓寫了封相關(guān)信件。但沒有引起哈密爾頓的注意。,直到1878年，在英國數(shù)學(xué)會議上，數(shù)學(xué)家凱萊才再一次提到4色問題。,23,1879年7月，業(yè)余數(shù)學(xué)家肯普(1849-1922）在英國自然雜志上宣稱證明了4色定理。肯普是凱萊在劍橋大學(xué)的學(xué)生。,1890年，英國數(shù)學(xué)家希五德發(fā)表文章地圖染色定理，通過構(gòu)造反例，指出了肯普證明中的缺陷。后來，西五德一直研究4色問題60年。,泰特在此期間也研究4色問題，但其證明被托特否定。,希五德文章之后，4色問題研究進(jìn)程開始走向停滯。,到了20世紀(jì)，美國數(shù)學(xué)家比爾荷夫提出可約性概念，在此基礎(chǔ)上，德國數(shù)學(xué)家Heesch(1

10、9061995)認(rèn)為，可以通過尋找所謂的不可約構(gòu)形來證明4色定理。,24,Heesch估計不可約構(gòu)形集合可能包含10000個元素，手工驗證是不太可能。于是他給出了一種可用計算機來驗證的方法。,20世紀(jì)70年代，Haken和他的學(xué)生Appel著力用計算機方法證明4色定理，借助于Appel在編程方面的深厚功底。他們于1976年6月終于成功解決了尋找不可約構(gòu)形集合中的元素，宣告4色定理的成功證明。數(shù)學(xué)家托特在圖論頂級刊物圖論雜志上寫了一首詩：,Wolfgang Haken,重重打擊著巨妖,一次！兩次！三次！四次！,他說：“妖怪已經(jīng)不存在了.”,25,2、五色定理,定理4 (希五德) 每個平面圖是5可

11、著色的。,根據(jù)平面圖和其對偶圖的關(guān)系，上面定理等價于每個平面圖是5可頂點正常著色的。,證明：我們對圖的頂點作數(shù)學(xué)歸納證明。 （不做要求）,當(dāng)n=1時，結(jié)論顯然。,設(shè)n=k時，結(jié)論成立?？紤]n=k+1的平面圖G。,因G是平面圖，所以(G)5,設(shè)d(u)=(G)5。,26,令G1=G u。由歸納假設(shè)，G1是5可頂點正常著色的。設(shè)是G1的5著色方案。,(1) 如果d(u)=(G)5, 顯然可以擴充為G的5正常頂點著色；,(2) 如果d(u)=(G) = 5, 分兩種情況討論。,情形1 在下，如果u的鄰接點中，至少有兩個頂點著相同顏色，則容易知道，可以擴充為G的5正常頂點著色；,情形2 在下，設(shè)u的鄰接點中，5個頂點著了5種不同顏色。,27,不失一般性，設(shè)(xi)=i (1i5)。,設(shè)H (i, j)表示著i和j色的點在G1中的點導(dǎo)出子圖。,如果x1與x3屬于H(1, 3