《第八章图图着色精选文档.ppt》由会员分享，可在线阅读，更多相关《第八章图图着色精选文档.ppt（17页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第八章图图着色1本讲稿第一页，共十七页8.8 图着色图着色Graph Coloringw例：例：本讲稿第二页，共十七页8.8 图着色图着色Graph Coloringw例：例：本讲稿第三页，共十七页8.8 图着色图着色Graph Coloring设设 G*是是 连连 通通 平平 面面 图图 G的的 对对 偶偶 图图，n*,m*,r*和和n,m,r分分别别为为G*和和G的的顶顶点数，边数和面数，则点数，边数和面数，则1.n*=r2.m*=m3.r*=n4.设设G*的的顶顶点点vi*位位于于G的的面面Ri中中，则则dG*(vi*)=deg(Ri)。本讲稿第四页，共十七页8.8 图着色图着色Grap
2、h ColoringDEFINITION A coloring(着色着色)of a simple graph is the assignment of a color to each vertex of the graph so that no two adjacent vertices are assigned the same color.本讲稿第五页，共十七页8.8 图着色图着色Graph ColoringDEFINITION The chromatic number(色数色数)of a graph is the least number of colors needed for a c
3、oloring of this graph,denoted by 四色定理四色定理THE FOUR COLOR THEOREM The chromatic number of a planar graph is no greater than four.本讲稿第六页，共十七页8.8 图着色图着色Graph Coloringw五色定理五色定理(Heawood,1890)：用：用种颜色种颜色可以给任何可以给任何简简单连通平面图单连通平面图着色。着色。证明：对结点数证明：对结点数v用归纳法用归纳法a)当当v1，2，3，4，5时显然成立。时显然成立。b)设设vk时成立，现考察时成立，现考察vk+1已知
4、必存在结点已知必存在结点u，使，使deg(u)5，在图，在图G中删去中删去u，得到，得到G-u，由归纳假设知，由归纳假设知G-u可以用可以用5种颜色着种颜色着色。色。本讲稿第七页，共十七页8.8 图着色图着色Graph Coloringw将将u加入到加入到G-u中，若中，若deg(u)5，必可对，必可对u正常着色，得到一个最多是五色的图正常着色，得到一个最多是五色的图G。G-uu本讲稿第八页，共十七页8.8 图着色图着色Graph Coloringw将将u加入到加入到G-u中，若中，若deg(u)=5。令令H为为G-u中绿色和蓝色的顶点集合，中绿色和蓝色的顶点集合，F为为G-u中红色和紫色的顶
5、点集合。中红色和紫色的顶点集合。G-uuv3v5v4v2v1本讲稿第九页，共十七页8.8 图着色图着色Graph Coloringw若若v v1 1与与v v3 3属于顶点集属于顶点集H H所导出子图的两个所导出子图的两个不同的连通分支中，将不同的连通分支中，将v v1 1所在分图中的所在分图中的蓝色和绿色对调，在蓝色和绿色对调，在u u上着绿色。上着绿色。G-uuv3v5v4v2v1G-uuv3v5v4v2v1本讲稿第十页，共十七页8.8 图着色图着色Graph Coloringw若若v v1 1与与v v3 3属于顶点集属于顶点集H H所导出子图的同一个连通分支所导出子图的同一个连通分支中
6、，那么中，那么v v2 2与与v v4 4将分别属于结点集将分别属于结点集F F所导出子图所导出子图的两个不同连通分支中。在包含的两个不同连通分支中。在包含v v2 2的连通分支的连通分支中将红色和紫色对调，对中将红色和紫色对调，对u u着红色着红色。G-uuv3v5v4v2v1本讲稿第十一页，共十七页8.8 图着色图着色Graph ColoringwExample:Try to find a coloring of the graph,including the infinite region.本讲稿第十二页，共十七页韦尔奇韦尔奇鲍威尔鲍威尔（Welch.powell）图着色法：）图着色法：
7、例：用韦尔奇例：用韦尔奇鲍威尔法对图着色鲍威尔法对图着色（1）将图中结点数依照度数的递减次序进行排列；）将图中结点数依照度数的递减次序进行排列；上图根据结点度数以递减排列次序为：上图根据结点度数以递减排列次序为：(6)(5)(5)(4)(4)(4)(3)(3)8.8 图着色图着色Graph Coloring本讲稿第十三页，共十七页（2）对）对5及及与与5不相邻的结点不相邻的结点1着蓝色；着蓝色；（3）对对3和和与与3不不相相邻邻的的结结点点4、8着着红红色色,对对7和和与与7不不相邻的结点相邻的结点2、6着黄色，着色完毕。着黄色，着色完毕。8.8 图着色图着色Graph Coloring本讲稿
8、第十四页，共十七页8.8 图着色图着色Graph Coloring本讲稿第十五页，共十七页例例：大大学学中中7门门考考试试，以以下下课课程程中中有有公公共共学学生生，12；13；14；17；23；24；25；27；34；36；37；45；46；56；57；67；问问如如何何在在尽尽可可能能少少的的时时间间段段里里安安排排7门考试并使得没有学生在同一时间里有两门考试。门考试并使得没有学生在同一时间里有两门考试。3254761时间段时间段课程课程1122，633，544，78.8 图着色图着色Graph Coloring本讲稿第十六页，共十七页8.8 图着色图着色Graph Coloringw思考：思考：Kn的色数是多少？的色数是多少？本讲稿第十七页，共十七页