欧美精品一二区,性欧美一级,国产免费一区成人漫画,草久久久久,欧美性猛交ⅹxxx乱大交免费,欧美精品另类,香蕉视频免费播放

第62講 平面圖的面著色

上傳人:仙*** 文檔編號(hào):73127314 上傳時(shí)間:2022-04-11 格式:PPT 頁(yè)數(shù):23 大?。?70.02KB
收藏 版權(quán)申訴 舉報(bào) 下載
第62講 平面圖的面著色_第1頁(yè)
第1頁(yè) / 共23頁(yè)
第62講 平面圖的面著色_第2頁(yè)
第2頁(yè) / 共23頁(yè)
第62講 平面圖的面著色_第3頁(yè)
第3頁(yè) / 共23頁(yè)

下載文檔到電腦,查找使用更方便

10 積分

下載資源

還剩頁(yè)未讀,繼續(xù)閱讀

資源描述:

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

1、離散數(shù)學(xué)離散數(shù)學(xué)第第62講講 平面圖的面著色平面圖的面著色第第7章章 幾類特殊的圖幾類特殊的圖7.6 平面圖的面著色平面圖的面著色本講內(nèi)容本講內(nèi)容平面圖的面著色平面圖的面著色1任意無向圖的節(jié)點(diǎn)著色任意無向圖的節(jié)點(diǎn)著色2任意任意無向無向圖的邊著色圖的邊著色37.6 平面圖的面著色平面圖的面著色 “四色猜想四色猜想”(4CC, Four Color Conjecture). 本節(jié)主要內(nèi)容是平面圖的面著色問題本節(jié)主要內(nèi)容是平面圖的面著色問題, ,順便順便介紹任意無向圖的節(jié)點(diǎn)著色以及邊著色等介紹任意無向圖的節(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)不同的顏色, 則稱對(duì)該則稱對(duì)該平面圖的平面圖的面著色面著色(face coloring), 所需顏色的所需顏色的最少種數(shù)稱為面著色數(shù)最少種數(shù)稱為面著色數(shù)(region chromatic number). Remark 任意平面圖均有無限面任意平面圖均有無限面.1c1c1c1c1c1c1c1c2c2c2c2c2c2c2c2c2c3c3c 2.任意任意無向無向圖的節(jié)點(diǎn)著色圖的節(jié)點(diǎn)著色 (1) 任意任意無向無向圖的節(jié)點(diǎn)著色圖的節(jié)點(diǎn)著色 Def 設(shè)設(shè)G是任意無向圖是任意無向圖, 若對(duì)若對(duì)G的每個(gè)

3、節(jié)點(diǎn)涂的每個(gè)節(jié)點(diǎn)涂上一種顏色且相鄰的節(jié)點(diǎn)出現(xiàn)不同的顏色上一種顏色且相鄰的節(jié)點(diǎn)出現(xiàn)不同的顏色,則稱對(duì)該圖的節(jié)點(diǎn)著色則稱對(duì)該圖的節(jié)點(diǎn)著色(vertex coloring), 簡(jiǎn)簡(jiǎn)稱稱著色著色(coloring), 所需顏色的最少種數(shù)稱為所需顏色的最少種數(shù)稱為節(jié)點(diǎn)著色數(shù)節(jié)點(diǎn)著色數(shù), 簡(jiǎn)稱著色數(shù)簡(jiǎn)稱著色數(shù)(chromatic number),記為記為 ).(G.)(nKn1c1c1c1c2c1c1c1c1c1c1c2c2c2c2c2c2c2c2c2c3c3c Theorem 7-13 G無自環(huán)無自環(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)著色與一般無向圖的節(jié)點(diǎn)著平面圖的節(jié)點(diǎn)著色與一般無向圖的節(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. 任意無向圖的邊著色任意無向圖的邊著色 Def 設(shè)設(shè)G是任意無向圖是任意無向圖, 若對(duì)若對(duì)G的每條邊涂上的每條邊涂上一種顏色且相鄰的邊出現(xiàn)不同

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

7、oblem) 任給一群人任給一群人,其中有其中有p個(gè)人彼此認(rèn)識(shí)或有個(gè)人彼此認(rèn)識(shí)或有q個(gè)人彼此不認(rèn)個(gè)人彼此不認(rèn)識(shí)識(shí),這種人群至少多少人這種人群至少多少人? Ramsey問題中的答案記為問題中的答案記為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?

展開閱讀全文
溫馨提示:
1: 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
2: 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3.本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 裝配圖網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

最新文檔

相關(guān)資源

更多
正為您匹配相似的精品文檔
關(guān)于我們 - 網(wǎng)站聲明 - 網(wǎng)站地圖 - 資源地圖 - 友情鏈接 - 網(wǎng)站客服 - 聯(lián)系我們

copyright@ 2023-2025  zhuangpeitu.com 裝配圖網(wǎng)版權(quán)所有   聯(lián)系電話:18123376007

備案號(hào):ICP2024067431號(hào)-1 川公網(wǎng)安備51140202000466號(hào)


本站為文檔C2C交易模式,即用戶上傳的文檔直接被用戶下載,本站只是中間服務(wù)平臺(tái),本站所有文檔下載所得的收益歸上傳人(含作者)所有。裝配圖網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)上載內(nèi)容本身不做任何修改或編輯。若文檔所含內(nèi)容侵犯了您的版權(quán)或隱私,請(qǐng)立即通知裝配圖網(wǎng),我們立即給予刪除!