第62講 平面圖的面著色

《第62講 平面圖的面著色》由會(huì)員分享，可在線(xiàn)閱讀，更多相關(guān)《第62講 平面圖的面著色（23頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

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

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

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

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

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

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

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