




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)
文檔簡介
1、1,圖的著色,一、圖的邊著色,二、圖的頂點著色,主要內(nèi)容,2,現(xiàn)實生活中很多問題,可以模型為所謂的邊著色問題來處理。例如排課表問題。,(一)、邊著色,排課表問題:設(shè)有m位教師,n個班級,其中教師xi要給班級yj上pij節(jié)課。求如何在最少節(jié)次排完所有課。,建模:令X=x1,x2,xm, Y=y1,y2,yn,xi與yj間連pij條邊,得偶圖G=(X, Y).,于是,問題轉(zhuǎn)化為如何在G中將邊集E劃分為互不相交的p個匹配,且使得p最小。,如果每個匹配中的邊用同一種顏色染色,不同匹配中的邊用不同顏色染色,則問題轉(zhuǎn)化為在G中給每條邊染色,相鄰邊染不同色,至少需要的顏色數(shù)。,3,這就需要我們研究所謂的邊著
2、色問題。,定義1 設(shè)G是圖,對G的邊進(jìn)行染色,若相鄰邊染不同顏色,則稱對G進(jìn)行正常邊著色;,如果能用k中顏色對圖G進(jìn)行正常邊著色,稱G是k邊可著色的。,定義2 設(shè)G是圖,對G進(jìn)行正常邊著色需要的最少顏色數(shù),稱為G的邊色數(shù),記為:,4,注:對圖的正常邊著色,實際上是對G的邊集合的一種劃分,使得每個劃分塊是G的一個邊獨立集(無環(huán)時是匹配);圖的邊色數(shù)對應(yīng)的是圖的最少獨立集劃分?jǐn)?shù)。,因此,圖的邊著色,本質(zhì)上是對應(yīng)實際問題中的“劃分”問題或“分類”問題。,5,(二)、幾類特殊圖的邊色數(shù),1、偶圖的邊色數(shù),定理1,證明:設(shè),又設(shè)=n。設(shè)顏色集合設(shè)為0,1,2,n-1, 是Km,n的一種n著色方案,滿足:
3、,6,我們證明:上面的著色是正常邊著色。,對K m, n中任意的兩條鄰接邊xiyj和xiyk。若,則:i+ j ( mod n)=i +k ( mod n),得到j(luò)=k,矛盾!,所以,上面著色是正常著色。所以:,又顯然 ,所以,,例1 用最少的顏色數(shù)對K3,4正常邊著色。,7,定理2 (哥尼,1916)若G是偶圖,則,8,定理3 (維津定理,1964) 若G是單圖,則:,注: 根據(jù)這個定理, 如果我們要證明某一個圖的邊染色數(shù)是, 只要我們找到了一種染色方式用的色數(shù)是就可以了。 如果要證明是 +1, 我們只需要證明用色不能正常染色。一般用反證法, 假設(shè)能用 染色, 得到矛盾。,9,注: (1)
4、根據(jù)維津定理,單圖可以按邊色數(shù)分成兩類圖,一是色數(shù)等于(G)的單圖,二是色數(shù)等于(G)+1的單圖。,(2) 維津(Vizing) : 1937年出生于烏克蘭的基輔。1954年開始在托木斯克大學(xué)學(xué)習(xí)數(shù)學(xué),1959年大學(xué)畢業(yè)保送到莫斯科斯特克羅夫研究所攻讀博士學(xué)位,研究函數(shù)逼近論。但這不是他的興趣所在,因此沒有獲得學(xué)位。1966年在季科夫的指導(dǎo)下獲得博士學(xué)位。和大多數(shù)數(shù)學(xué)家一樣,維津在音樂方面具有一定才能。,10,維津在攻讀博士學(xué)位期間,發(fā)現(xiàn)并證明了上面的維津定理。他當(dāng)時把論文投向一家非常著名的雜志,但由于審稿人認(rèn)為問題本身沒有意義而遭到拒絕。后來在另外一家地方雜志發(fā)表時,定理早已出名。,維津認(rèn)為
5、:一名數(shù)學(xué)家應(yīng)該不斷研究與發(fā)現(xiàn)新結(jié)果,然后讓時間來檢驗其重要性。,11,定理 設(shè)G是單圖。若點數(shù)n=2k+1且邊數(shù)mk,則:,證明:若不然,由維津定理,,設(shè)是G的(G)正常邊著色方案,對于G的每個色組來說,包含的邊數(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ù)。,解:一方面,彼得森圖中去掉任意一個1因子后,剩下兩個5點圈,所以,不能進(jìn)行1因子分解,所以:,另
6、一方面:G的最大度數(shù) =3, 所以:,14,例6 (1) 設(shè)G=(X, Y)是一個最大度為的偶圖,求證,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ù)上面的過程,可得到G2,這樣不斷下去,最終得到包含G的正則偶圖G*。,(2) 由(1) 對于任意最大度為的
7、偶圖G,均存在G的正則母圖G*。又由于正則偶圖存在1因子分解,所以,G*可以劃分為個1因子,從而其邊色數(shù)為。這樣G的邊色數(shù)也為。,16,(二) 圖的頂點著色,17,定義1 設(shè)G是一個圖,對G的每個頂點著色,使得相鄰頂點著不同顏色,稱為對G的正常頂點著色;,如果用k種顏色可以對G進(jìn)行正常頂點著色,稱G可k正常頂點著色;,對圖G正常頂點著色需要的最少顏色數(shù),稱為圖G的點色數(shù)。圖G的點色數(shù)用 表示。,例1 說明下圖的點色數(shù)是4。,下列命題成立:,G是有邊的兩分圖的充要條件是=2 G是無邊圖的充要條件是=1 G是完全圖的充要條件是=|V(G)| (輪)=3 (輪的頂點數(shù)是奇數(shù)); 4(否則),定理:對
8、任意的圖G 均有,頂點著色,定理:設(shè)G是連通圖。假定G既不是完全圖又不是奇圈,則,一個著色算法:Welsh-Powell算法,頂點著色,(1)將圖G的節(jié)點按度數(shù)遞減排列; (2)對第一個節(jié)點及其不鄰接的節(jié)點著第一個顏色; (3)對常未著色的第一個及其不鄰接的節(jié)點著第二個顏色;續(xù)行此法, 直到全部節(jié)點著色完為止。,用Welsh-Powell算法對下例中的點著色,結(jié)果如下圖所示。,頂點著色,22,1、四色定理,(三)、四色與五色定理,1852年,剛畢業(yè)于倫敦大學(xué)的格斯里(18311899)發(fā)現(xiàn):給一張平面地圖正常著色,至少需要4種顏色。這就是著名的4色定理。,格斯里把他的證明通過他弟弟轉(zhuǎn)交給著名數(shù)
9、學(xué)家摩爾根,引起摩爾根極大興趣并于當(dāng)天給數(shù)學(xué)家哈密爾頓寫了封相關(guān)信件。但沒有引起哈密爾頓的注意。,直到1878年,在英國數(shù)學(xué)會議上,數(shù)學(xué)家凱萊才再一次提到4色問題。,23,1879年7月,業(yè)余數(shù)學(xué)家肯普(1849-1922)在英國自然雜志上宣稱證明了4色定理。肯普是凱萊在劍橋大學(xué)的學(xué)生。,1890年,英國數(shù)學(xué)家希五德發(fā)表文章地圖染色定理,通過構(gòu)造反例,指出了肯普證明中的缺陷。后來,西五德一直研究4色問題60年。,泰特在此期間也研究4色問題,但其證明被托特否定。,希五德文章之后,4色問題研究進(jìn)程開始走向停滯。,到了20世紀(jì),美國數(shù)學(xué)家比爾荷夫提出可約性概念,在此基礎(chǔ)上,德國數(shù)學(xué)家Heesch(1
10、9061995)認(rèn)為,可以通過尋找所謂的不可約構(gòu)形來證明4色定理。,24,Heesch估計不可約構(gòu)形集合可能包含10000個元素,手工驗證是不太可能。于是他給出了一種可用計算機來驗證的方法。,20世紀(jì)70年代,Haken和他的學(xué)生Appel著力用計算機方法證明4色定理,借助于Appel在編程方面的深厚功底。他們于1976年6月終于成功解決了尋找不可約構(gòu)形集合中的元素,宣告4色定理的成功證明。數(shù)學(xué)家托特在圖論頂級刊物圖論雜志上寫了一首詩:,Wolfgang Haken,重重打擊著巨妖,一次!兩次!三次!四次!,他說:“妖怪已經(jīng)不存在了.”,25,2、五色定理,定理4 (希五德) 每個平面圖是5可
11、著色的。,根據(jù)平面圖和其對偶圖的關(guān)系,上面定理等價于每個平面圖是5可頂點正常著色的。,證明:我們對圖的頂點作數(shù)學(xué)歸納證明。 (不做要求),當(dāng)n=1時,結(jié)論顯然。,設(shè)n=k時,結(jié)論成立??紤]n=k+1的平面圖G。,因G是平面圖,所以(G)5,設(shè)d(u)=(G)5。,26,令G1=G u。由歸納假設(shè),G1是5可頂點正常著色的。設(shè)是G1的5著色方案。,(1) 如果d(u)=(G)5, 顯然可以擴充為G的5正常頂點著色;,(2) 如果d(u)=(G) = 5, 分兩種情況討論。,情形1 在下,如果u的鄰接點中,至少有兩個頂點著相同顏色,則容易知道,可以擴充為G的5正常頂點著色;,情形2 在下,設(shè)u的鄰接點中,5個頂點著了5種不同顏色。,27,不失一般性,設(shè)(xi)=i (1i5)。,設(shè)H (i, j)表示著i和j色的點在G1中的點導(dǎo)出子圖。,如果x1與x3屬于H(1, 3
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 智慧醫(yī)療與智能設(shè)備的設(shè)計思維研究
- 智慧城市的產(chǎn)業(yè)布局與經(jīng)濟分析
- 企業(yè)健康管理-糖尿病防控新路徑
- 商業(yè)教育中的心理學(xué)技巧
- 商場工裝知識培訓(xùn)課件
- 全球鈾礦資源儲備與2025年核能產(chǎn)業(yè)可持續(xù)發(fā)展戰(zhàn)略分析報告
- 公交優(yōu)先發(fā)展戰(zhàn)略下2025年城市交通擁堵治理的擁堵路段調(diào)整策略報告
- Chitosan-Cy7-MW-7000-生命科學(xué)試劑-MCE
- 2024-2025學(xué)年安徽省阜陽市太和縣化學(xué)九年級第一學(xué)期期末經(jīng)典模擬試題含解析
- 西南交通大學(xué)希望學(xué)院《傳統(tǒng)及現(xiàn)代手工藝制作》2023-2024學(xué)年第一學(xué)期期末試卷
- 加油站安全生產(chǎn)隱患排查治理制度
- 千川投手培訓(xùn)課件
- 佛山市2024-2025高一下期末-物理試卷
- 浙江省杭州市2024-2025學(xué)年高二下學(xué)期6月期末教學(xué)質(zhì)量檢測物理試題(含答案)
- 建設(shè)工程(更新)融資投資立項項目可行性研究報告(非常詳細(xì))
- 變電站集控系統(tǒng)管理制度
- 2025年廣東省高考語文試卷(含標(biāo)準(zhǔn)答案)
- 傳感器與檢測技術(shù)(周杏鵬)全套教案課件
- 中國熱射病診斷與治療指南(2025版)
- 2025年下半年佛山市南海區(qū)建筑工程質(zhì)量檢測站招考編外工作人員易考易錯模擬試題(共500題)試卷后附參考答案
- GB/T 45610-2025煤矸石回填塌陷區(qū)復(fù)墾技術(shù)規(guī)程
評論
0/150
提交評論