第62講 平面圖的面著色

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

1、離散數(shù)學離散數(shù)學第第62講講 平面圖的面著色平面圖的面著色第第7章章 幾類特殊的圖幾類特殊的圖7.6 平面圖的面著色平面圖的面著色本講內容本講內容平面圖的面著色平面圖的面著色1任意無向圖的節(jié)點著色任意無向圖的節(jié)點著色2任意任意無向無向圖的邊著色圖的邊著色37.6 平面圖的面著色平面圖的面著色 “四色猜想四色猜想”(4CC, Four Color Conjecture). 本節(jié)主要內容是平面圖的面著色問題本節(jié)主要內容是平面圖的面著色問題, ,順便順便介紹任意無向圖的節(jié)點著色以及邊著色等介紹任意無向圖的節(jié)點著色以及邊著色等有關內容有關內容. . 1. 平面圖的面著色平面圖的面著色 Def 設設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 設設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é)點著色, 進而求出的上界進而求出的上界. 1)()(GG Step 1 將節(jié)點按度數(shù)從大到小的順序排列將節(jié)點按度數(shù)從大到小的順序排列. Step 2 用第一種顏色對第一個節(jié)點著色用第一種顏色對第一個節(jié)點著色,并并且按照其余未著色節(jié)點順序且按照其余未著色節(jié)點順序, 對不鄰接的每對不鄰接的每一個節(jié)點著上同樣的顏色一個節(jié)點著上同樣的顏色. Step 3 用第二種顏色對尚未著色的節(jié)點重用第二種顏色對尚未著色的節(jié)點重復復Step 2, 繼續(xù)下去繼續(xù)下去, 直到所有的點都著色為直到所有的點都著色為止止. 例例8-191v2v3v4v5v6v7v8v86421735,vvvvvvvv23231321,

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

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

7、oblem) 任給一群人任給一群人,其中有其中有p個人彼此認識或有個人彼此認識或有q個人彼此不認個人彼此不認識識,這種人群至少多少人這種人群至少多少人? Ramsey問題中的答案記為問題中的答案記為R(p, q). 例例7-20 證明證明: 任意任意6個人中個人中, 有有3個人彼此認個人彼此認識或有識或有3個人彼此不認識個人彼此不認識. 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.小結與作業(yè)小結與作業(yè)平面圖的面著色平面圖的面著色任意圖的節(jié)點著色任意圖的節(jié)點著色任意圖的邊著色任意圖的邊著色習題習題7.6 1, 3, 9作業(yè)作業(yè)Any Questions?