資源描述：
《《如何學(xué)習(xí)圖論》PPT課件.ppt》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、8.8圖著色GraphColoringDualgraph(對偶圖)Eachregionofthemapisrepresentedbyavertex.Edgesconnecttwoverticesiftheregionsrepresentedbytheseverticeshaveacommonborder.18.8圖著色GraphColoring例：28.8圖著色GraphColoring例：38.8圖著色GraphColoring設(shè)G*是連通平面圖G的對偶圖，n*,m*,r*和n,m,r分別為G*和G
2、的頂點數(shù)，邊數(shù)和面數(shù)，則n*=rm*=mr*=n設(shè)G*的頂點vi*位于G的面Ri中，則dG*(vi*)=deg(Ri)。48.8圖著色GraphColoringDEFINITIONAcoloring(著色)ofasimplegraphistheassignmentofacolortoeachvertexofthegraphsothatnotwoadjacentverticesareassignedthesamecolor.58.8圖著色GraphColoringDEFINITIONThechromat
3、icnumber(色數(shù))ofagraphistheleastnumberofcolorsneededforacoloringofthisgraph,denotedby四色定理THEFOURCOLORTHEOREMThechromaticnumberofaplanargraphisnogreaterthanfour.68.8圖著色GraphColoring五色定理(Heawood,1890)：用５種顏色可以給任何簡單連通平面圖著色。證明：對結(jié)點數(shù)v用歸納法a)當(dāng)v＝1，2，3，4，5時顯然成立。b)設(shè)v
4、＝k時成立，現(xiàn)考察v＝k+1已知必存在結(jié)點u，使deg(u)≤5，在圖G中刪去u，得到G-{u}，由歸納假設(shè)知G-{u}可以用5種顏色著色。78.8圖著色GraphColoring將u加入到G-{u}中，若deg(u)<5，必可對u正常著色，得到一個最多是五色的圖G。G-{u}u88.8圖著色GraphColoring將u加入到G-{u}中，若deg(u)=5。令H為G-{u}中綠色和藍(lán)色的頂點集合，F(xiàn)為G-{u}中紅色和紫色的頂點集合。G-{u}uv3v5v4v2v198.8圖著色GraphColo
5、ring若v1與v3屬于頂點集H所導(dǎo)出子圖的兩個不同的連通分支中，將v1所在分圖中的藍(lán)色和綠色對調(diào)，在u上著綠色。G-{u}uv3v5v4v2v1G-{u}uv3v5v4v2v1108.8圖著色GraphColoring若v1與v3屬于頂點集H所導(dǎo)出子圖的同一個連通分支中，那么v2與v4將分別屬于結(jié)點集F所導(dǎo)出子圖的兩個不同連通分支中。在包含v2的連通分支中將紅色和紫色對調(diào)，對u著紅色。G-{u}uv3v5v4v2v1118.8圖著色GraphColoringExample:Trytofindacol
6、oringofthegraph,includingtheinfiniteregion.12韋爾奇—鮑威爾（Welch.powell）圖著色法：例：用韋爾奇—鮑威爾法對圖著色（1）將圖中結(jié)點數(shù)依照度數(shù)的遞減次序進(jìn)行排列；上圖根據(jù)結(jié)點度數(shù)以遞減排列次序為：５?。场。贰。保病。础。丁。?6)(5)(5)(4)(4)(4)(3)(3)8.8圖著色GraphColoring13（2）對5及與5不相鄰的結(jié)點1著藍(lán)色；（3）對3和與3不相鄰的結(jié)點4、8著紅色,對7和與7不相鄰的結(jié)點2、6著黃色，著色完畢。8.8圖著
7、色GraphColoring148.8圖著色GraphColoring15例：大學(xué)中7門考試，以下課程中有公共學(xué)生，12；13；14；17；23；24；25；27；34；36；37；45；46；56；57；67；問如何在盡可能少的時間段里安排7門考試并使得沒有學(xué)生在同一時間里有兩門考試。3254761時間段課程1122，633，544，78.8圖著色GraphColoring168.8圖著色GraphColoring思考：Kn的色數(shù)是多少？17
