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