第62講 平面圖的面著色

《第62講 平面圖的面著色》由會員分享，可在線閱讀，更多相關(guān)《第62講 平面圖的面著色（23頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、離散數(shù)學(xué)離散數(shù)學(xué)第第62講講 平面圖的面著色平面圖的面著色第第7章章 幾類特殊的圖幾類特殊的圖7.6 平面圖的面著色平面圖的面著色本講內(nèi)容本講內(nèi)容平面圖的面著色平面圖的面著色1任意無向圖的節(jié)點著色任意無向圖的節(jié)點著色2任意任意無向無向圖的邊著色圖的邊著色37.6 平面圖的面著色平面圖的面著色 “四色猜想四色猜想”(4CC, Four Color Conjecture). 本節(jié)主要內(nèi)容是平面圖的面著色問題本節(jié)主要內(nèi)容是平面圖的面著色問題, ,順便順便介紹任意無向圖的節(jié)點著色以及邊著色等介紹任意無向圖的節(jié)點著色以及邊著色等有關(guān)內(nèi)容有關(guān)內(nèi)容. . 1. 平面圖的面著色平面圖的面著色 Def 設(shè)設(shè)G是

2、平面圖是平面圖, 若對若對G的每個面涂上一種的每個面涂上一種顏色且相鄰的面出現(xiàn)不同的顏色顏色且相鄰的面出現(xiàn)不同的顏色, 則稱對該則稱對該平面圖的平面圖的面著色面著色(face coloring), 所需顏色的所需顏色的最少種數(shù)稱為面著色數(shù)最少種數(shù)稱為面著色數(shù)(region chromatic number). Remark 任意平面圖均有無限面任意平面圖均有無限面.1c1c1c1c1c1c1c1c2c2c2c2c2c2c2c2c2c3c3c 2.任意任意無向無向圖的節(jié)點著色圖的節(jié)點著色 (1) 任意任意無向無向圖的節(jié)點著色圖的節(jié)點著色 Def 設(shè)設(shè)G是任意無向圖是任意無向圖, 若對若對G的每個

3、節(jié)點涂的每個節(jié)點涂上一種顏色且相鄰的節(jié)點出現(xiàn)不同的顏色上一種顏色且相鄰的節(jié)點出現(xiàn)不同的顏色,則稱對該圖的節(jié)點著色則稱對該圖的節(jié)點著色(vertex coloring), 簡簡稱稱著色著色(coloring), 所需顏色的最少種數(shù)稱為所需顏色的最少種數(shù)稱為節(jié)點著色數(shù)節(jié)點著色數(shù), 簡稱著色數(shù)簡稱著色數(shù)(chromatic number),記為記為 ).(G.)(nKn1c1c1c1c2c1c1c1c1c1c1c2c2c2c2c2c2c2c2c2c3c3c Theorem 7-13 G無自環(huán)無自環(huán), 則則 可以利用韋爾奇可以利用韋爾奇 鮑威爾鮑威爾(Welch Powell)算法算法對圖的節(jié)點著色對

4、圖的節(jié)點著色, 進(jìn)而求出的上界進(jìn)而求出的上界. 1)()(GG Step 1 將節(jié)點按度數(shù)從大到小的順序排列將節(jié)點按度數(shù)從大到小的順序排列. Step 2 用第一種顏色對第一個節(jié)點著色用第一種顏色對第一個節(jié)點著色,并并且按照其余未著色節(jié)點順序且按照其余未著色節(jié)點順序, 對不鄰接的每對不鄰接的每一個節(jié)點著上同樣的顏色一個節(jié)點著上同樣的顏色. Step 3 用第二種顏色對尚未著色的節(jié)點重用第二種顏色對尚未著色的節(jié)點重復(fù)復(fù)Step 2, 繼續(xù)下去繼續(xù)下去, 直到所有的點都著色為直到所有的點都著色為止止. 例例8-191v2v3v4v5v6v7v8v86421735,vvvvvvvv23231321,

5、cccccccc1v2v3v4v5v6v7v8v3)(G (2) 平面圖的節(jié)點著色平面圖的節(jié)點著色 平面圖的節(jié)點著色與一般無向圖的節(jié)點著平面圖的節(jié)點著色與一般無向圖的節(jié)點著色是相同的色是相同的. 平面圖的面著色平面圖的面著色,可以轉(zhuǎn)換為其可以轉(zhuǎn)換為其對偶圖對偶圖(也是平面圖也是平面圖)的節(jié)點著色的節(jié)點著色. Theorem 7-14(五色定理五色定理) 設(shè)設(shè)G是簡單平面圖是簡單平面圖,則則 Hint 對對G的節(jié)點個數(shù)的節(jié)點個數(shù)n歸納歸納. 5)(G 3. 任意無向圖的邊著色任意無向圖的邊著色 Def 設(shè)設(shè)G是任意無向圖是任意無向圖, 若對若對G的每條邊涂上的每條邊涂上一種顏色且相鄰的邊出現(xiàn)不同

6、的顏色一種顏色且相鄰的邊出現(xiàn)不同的顏色, 則稱則稱對該圖的對該圖的邊著色邊著色(edge coloring), 所需顏色的所需顏色的最少種數(shù)稱為邊著色數(shù)最少種數(shù)稱為邊著色數(shù)(edge-chromatic number). 圖中的圖中的兩條邊相鄰兩條邊相鄰是指它們有公共的節(jié)點是指它們有公共的節(jié)點. 1c1c1c1c1c1c1c1c1c1c2c2c2c2c2c2c3c3c3c2c2c3c3c3c3c4c4c4c4c3c5c5c6c6c4c 最后對與最后對與Ramsey理論密切相關(guān)的圖的邊理論密切相關(guān)的圖的邊“涂色涂色”的問題進(jìn)行簡單說明的問題進(jìn)行簡單說明. Ramsey問題問題(Ramsey pr

7、oblem) 任給一群人任給一群人,其中有其中有p個人彼此認(rèn)識或有個人彼此認(rèn)識或有q個人彼此不認(rèn)個人彼此不認(rèn)識識,這種人群至少多少人這種人群至少多少人? Ramsey問題中的答案記為問題中的答案記為R(p, q). 例例7-20 證明證明: 任意任意6個人中個人中, 有有3個人彼此認(rèn)個人彼此認(rèn)識或有識或有3個人彼此不認(rèn)識個人彼此不認(rèn)識. R(3, 3) = 6(1930). 其他其他Ramsey數(shù)數(shù)?v1v2v3v R(3, 4) = 9, R(3, 5) = 14, R(4, 4) = 18 (1955). R(3, 6) = 18 (1964, 1966). R(3, 7) = 23 (1968). R(3, 9) = 36 (1982). R(3, 8) = 28 (1992). R(4, 5) = 25 (1993). 43R(5, 5) 49(1989, 1995) http:/ Last accessed 14 June, 2013.小結(jié)與作業(yè)小結(jié)與作業(yè)平面圖的面著色平面圖的面著色任意圖的節(jié)點著色任意圖的節(jié)點著色任意圖的邊著色任意圖的邊著色習(xí)題習(xí)題7.6 1, 3, 9作業(yè)作業(yè)Any Questions?