二部圖與染色

1、圖著色四色定理k-(點,面,邊)著色, k-(點,面,邊)色圖, 點色數(shù)(G), 面色數(shù)*(G), 邊色數(shù)(G)五色定理1四色問題(Four Color Problem)1852, Francis Guthrie, 注意到英格蘭地圖可以用4種顏色染色, 使得相鄰區(qū)域(有一段公共邊界,不只是有一個公共點)有不同顏色; 他問其弟 Frederick 是否任意地圖都有此性質(zhì)? Frederick Guthrie DeMorgan Hamilton. 1878, Cayley, 提交倫敦數(shù)學會.2四色問題(Four Color Problem)3四色問題(Four Color Problem)1879

2、, Kempe, 第一次“證明”1880, Tait, 另一個“證明” 1890, Heawood 發(fā)現(xiàn)Kempe證明的錯誤1891, Petersen發(fā)現(xiàn)Tait證明的漏洞(Tait猜想)1946, Tutte發(fā)現(xiàn)Tait證明的錯誤(Tait猜想反例)4四色問題(Four Color Problem)1913, Birkhoff, 一個大貢獻1922, Franklin, 證明不超過22個區(qū)域的地圖四色猜想成立1950,不超過35個區(qū)域1960,不超過39個區(qū)域其他人取得其他形式進展:1974,52區(qū)域5四色問題(Four Color Problem)1936-50,Heesch,最終解決問

3、題的兩個要素: 10000個情形,100年約化(reducibility), 放電(discharging). 1972-76, Appel, Haken, 1482個情形, IBM360, 1200小時, 論文139頁+400頁程序, conjectureagnogramstheorem6四色問題(Four Color Problem)7四色定理的意義“四色問題”的被證明僅解決了一個歷時100多年的難題，而且成為數(shù)學史上一系列新思維的起點。在“四色問題”的研究過程中，不少新的數(shù)學理論隨之產(chǎn)生，也發(fā)展了很多數(shù)學計算技巧。如將地圖的著色問題化為圖論問題，豐富了圖論的內(nèi)容。不僅如此，“四色問題”在

4、有效地設(shè)計航空班機日程表，設(shè)計計算機的編碼程序上都起到了推動作用。8著色的應(yīng)用意義在有沖突的情況下分配資源時：有n項工作（或課程），有些工作需要同樣的人員或設(shè)備不能同時進行（或有同一人選課），問需要幾天才能完成所有的工作（如何安排教室、課程）？9著色(coloring)著色: 給圖的某類元素(點,邊,面)中每個指定1種顏色,使得相鄰元素有不同顏色(點)著色,邊著色,面著色: X=V(無環(huán)),E,R相鄰: V,有邊相連,(x,y)E; E,有公共端點, (x,y),(y,z); R,有公共邊界10著色(例)11著色(coloring)用顏色集C給X中頂點（邊、面）著色: f:XC,xy( x,y

5、Xx與y相鄰 f(x)f(y) ) 若|C|=k( 如C=1,2,k ), 則稱k-可著色（ k-可邊著色、 k-可面著色）。12色數(shù)(chromatic number)k-色圖: 可k-著色,但不可(k-1)-著色色數(shù): 著色所需最少顏色數(shù)點色數(shù)(G), 邊色數(shù)(G), 面色數(shù)*(G)例: (G)=2, (G)=4, *(G)=3 13二部圖設(shè)無向圖 G=，若能將V劃分成V1和V2，使得G中的每條邊的兩個端點都是一個屬于V1，另一個屬于V2，則稱G為二部圖（二分圖，偶圖），稱V1和V2為互補頂點子集，常記為 .完全二部圖： V1中的每個頂點均與V2中的所有頂點相鄰。Kr,s14二部圖判定n(

6、n=2)階無向圖G是二部圖當且僅當G中無奇圈當且僅當G是2-可著色 。15點色數(shù)性質(zhì)(G)=1 G是零圖 (Kn)=n(G)=2 G是非零圖二部圖G是2-可著色 G是二部圖 G無奇圈(Cn)= 2, n偶數(shù) (Wn)= 3, n奇數(shù) 3, n奇數(shù) 4, n偶數(shù)16(G)上界定理18.7: (G) (G)+1證明: vV(G), G(v)= u | (u,v)E(G) , |G(v)|(G), 給G(v)中頂點著色至多需要(G)種顏色, 所以至少還剩一種顏色可用來給v著色. #17(G)上界定理18.8(Brooks): 若G連通非完全圖Kn (n3)非奇圈, 則(G) (G). #說明:n=1

7、G=K1, n=2: 連通G=K2 (Kn)=n= (G)+118例(Petersen圖)例: Petersen圖=3.解1: 由Brooks定理, =3. 又圖中有奇圈, 3. 所以=3. #解2: 存在如下3-著色, =3. 又圖中有奇圈, 3. 所以=3. #19應(yīng)用示例1某大學計算機專業(yè)三年級有5門選修課，其中課程1與2， 1與3， 1與4， 2與4， 2與5， 3與4， 3與5均有人同時選修，問安排這5門課考試至少需要幾個時間段？123451234520面著色與對偶圖點著色定理9: 地圖G可k-面著色 對偶圖G*可k-著色. 定理9: 連通無環(huán)平面圖G可k-面著色 對偶圖G*可k-著

8、色. 研究平面圖面著色研究平面圖點著色21五色定理定理 (Heawood,1890): 任何平面圖都可5-著色v1v2v3v4v5u22定理17.12定理17.12: 設(shè)G是簡單平面圖,則(G)5. 證明: n 3n-6, 與 m3n-6 矛盾.23邊著色邊色數(shù): (G)定理11(Vizing): G是簡單圖,則(G) (G) (G)+1. #G=是二部圖, 則(G)=(G)n1時, (Kn)= n, n為奇數(shù) n-1, n為偶數(shù)24應(yīng)用示例2某一天內(nèi)有n個教師給m個班上課.每個教師在同課時只能給一個班上課. (1) 這一天內(nèi)至少排多少節(jié)課? (2) 不增加節(jié)數(shù)情況下至少需要幾個教室? (3)

9、 若n=4,m=5. 教師是t1,t2,t3,t4, 班是c1, c2,c3,c4,c5. 已知t1給c1,c2,c3上2節(jié),1節(jié),1節(jié)課, t2給c2,c3各上1節(jié)課, t3給c2,c3,c4各上1節(jié)課, t4給c4,c5上1節(jié),2節(jié)課. 求最省教室的課表.25應(yīng)用示例2(解)解: 令G=, T=t1,t2,tm, C=c1,c2,cn, E=(ti,cj)| ti給cj上一節(jié)課. 給G進行邊著色, 同色邊代表的教學可以同時進行, 所以顏色數(shù)就是節(jié)數(shù), 同色邊數(shù)就是教室數(shù). (1) k=(G)=(G)時, 節(jié)數(shù)最少. (2) min max k1,k2,k, 教室數(shù)最少. 其中ki是著顏色i的邊數(shù). (“平衡”著色)26應(yīng)用示例2(解,續(xù))解: (續(xù)) (3) 已知條件得出下圖G, T=t1,t2,t4, C=c1,c2,c5