new-圖著色.ppt

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

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

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

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

5、：一名數(shù)學(xué)家應(yīng)該不斷研究與發(fā)現(xiàn)新結(jié)果，然后讓時(shí)間來(lái)檢驗(yàn)其重要性。,11,定理 設(shè)G是單圖。若點(diǎn)數(shù)n=2k+1且邊數(shù)mk,則：,證明：若不然，由維津定理，,設(shè)是G的(G)正常邊著色方案，對(duì)于G的每個(gè)色組來(lái)說(shuō)，包含的邊數(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ù)。,解：一方面，彼得森圖中去掉任意一個(gè)1因子后，剩下兩個(gè)5點(diǎn)圈，所以，不能進(jìn)行1因子分解，所以：,另

6、一方面：G的最大度數(shù) =3， 所以：,14,例6 (1) 設(shè)G=(X, Y)是一個(gè)最大度為的偶圖，求證，G是某個(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ù)上面的過(guò)程，可得到G2,這樣不斷下去，最終得到包含G的正則偶圖G*。,(2) 由(1) 對(duì)于任意最大度為的

7、偶圖G,均存在G的正則母圖G*。又由于正則偶圖存在1因子分解，所以，G*可以劃分為個(gè)1因子，從而其邊色數(shù)為。這樣G的邊色數(shù)也為。,16,（二） 圖的頂點(diǎn)著色,17,定義1 設(shè)G是一個(gè)圖，對(duì)G的每個(gè)頂點(diǎn)著色，使得相鄰頂點(diǎn)著不同顏色，稱為對(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 說(shuō)明下圖的點(diǎn)色數(shù)是4。,下列命題成立：,G是有邊的兩分圖的充要條件是=2 G是無(wú)邊圖的充要條件是=1 G是完全圖的充要條件是=|V(G)| (輪）=3 （輪的頂點(diǎn)數(shù)是奇數(shù)）； 4（否則）,定理:對(duì)

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

9、學(xué)家摩爾根，引起摩爾根極大興趣并于當(dāng)天給數(shù)學(xué)家哈密爾頓寫(xiě)了封相關(guān)信件。但沒(méi)有引起哈密爾頓的注意。,直到1878年，在英國(guó)數(shù)學(xué)會(huì)議上，數(shù)學(xué)家凱萊才再一次提到4色問(wèn)題。,23,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世紀(jì)，美國(guó)數(shù)學(xué)家比爾荷夫提出可約性概念，在此基礎(chǔ)上，德國(guó)數(shù)學(xué)家Heesch(1

10、9061995)認(rèn)為，可以通過(guò)尋找所謂的不可約構(gòu)形來(lái)證明4色定理。,24,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ō)：“妖怪已經(jīng)不存在了.”,25,2、五色定理,定理4 (希五德) 每個(gè)平面圖是5可

11、著色的。,根據(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。,26,令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)著相同顏色，則容易知道，可以擴(kuò)充為G的5正常頂點(diǎn)著色；,情形2 在下，設(shè)u的鄰接點(diǎn)中，5個(gè)頂點(diǎn)著了5種不同顏色。,27,不失一般性，設(shè)(xi)=i (1i5)。,設(shè)H (i, j)表示著i和j色的點(diǎn)在G1中的點(diǎn)導(dǎo)出子圖。,如果x1與x3屬于H(1, 3