《如何学习图论》PPT课件

《如何学习图论》PPT课件

ID:45320622

大小:413.00 KB

页数:17页

时间:2019-11-11

《如何学习图论》PPT课件_第1页
《如何学习图论》PPT课件_第2页
《如何学习图论》PPT课件_第3页
《如何学习图论》PPT课件_第4页
《如何学习图论》PPT课件_第5页
资源描述:

《《如何学习图论》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*和

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

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

4、)设v=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图着色Graph

5、Coloring若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:Trytofin

6、dacoloringofthegraph,includingtheinfiniteregion.12韦尔奇—鲍威尔(Welch.powell)图着色法:例:用韦尔奇—鲍威尔法对图着色(1)将图中结点数依照度数的递减次序进行排列;上图根据结点度数以递减排列次序为:5 3 7 12 4 6 8(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的色数是多少?17

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。