《如何学习图论》PPT课件.ppt

《《如何学习图论》PPT课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、8.8图着色GraphColoringDualgraph(对偶图)Eachregionofthemapisrepresentedbyavertex.Edgesconnecttwoverticesiftheregionsrepresentedbytheseverticeshaveacommonborder.18.8图着色GraphColoring例：28.8图着色GraphColoring例：38.8图着色GraphColoring设G*是连通平面图G的对偶图，n*,m*,r*和n,m,r分别为G*和G

2、的顶点数，边数和面数，则n*=rm*=mr*=n设G*的顶点vi*位于G的面Ri中，则dG*(vi*)=deg(Ri)。48.8图着色GraphColoringDEFINITIONAcoloring(着色)ofasimplegraphistheassignmentofacolortoeachvertexofthegraphsothatnotwoadjacentverticesareassignedthesamecolor.58.8图着色GraphColoringDEFINITIONThechromat

3、icnumber(色数)ofagraphistheleastnumberofcolorsneededforacoloringofthisgraph,denotedby四色定理THEFOURCOLORTHEOREMThechromaticnumberofaplanargraphisnogreaterthanfour.68.8图着色GraphColoring五色定理(Heawood,1890)：用５种颜色可以给任何简单连通平面图着色。证明：对结点数v用归纳法a)当v＝1，2，3，4，5时显然成立。b)设v

4、＝k时成立，现考察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为G-{u}中红色和紫色的顶点集合。G-{u}uv3v5v4v2v198.8图着色GraphColo

5、ring若v1与v3属于顶点集H所导出子图的两个不同的连通分支中，将v1所在分图中的蓝色和绿色对调，在u上着绿色。G-{u}uv3v5v4v2v1G-{u}uv3v5v4v2v1108.8图着色GraphColoring若v1与v3属于顶点集H所导出子图的同一个连通分支中，那么v2与v4将分别属于结点集F所导出子图的两个不同连通分支中。在包含v2的连通分支中将红色和紫色对调，对u着红色。G-{u}uv3v5v4v2v1118.8图着色GraphColoringExample:Trytofindacol

6、oringofthegraph,includingtheinfiniteregion.12韦尔奇—鲍威尔（Welch.powell）图着色法：例：用韦尔奇—鲍威尔法对图着色（1）将图中结点数依照度数的递减次序进行排列；上图根据结点度数以递减排列次序为：５　３　７　１２　４　６　８(6)(5)(5)(4)(4)(4)(3)(3)8.8图着色GraphColoring13（2）对5及与5不相邻的结点1着蓝色；（3）对3和与3不相邻的结点4、8着红色,对7和与7不相邻的结点2、6着黄色，着色完毕。8.8图着

7、色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的色数是多少？17