《如何学习图论.ppt》由会员分享，可在线阅读，更多相关《如何学习图论.ppt（17页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、8.8 图着色图着色Graph ColoringDual graph(对偶图对偶图)Each region of the map is represented by a vertex.Edges connect two vertices if the regions represented by these vertices have a common border.18.8 图着色图着色Graph Coloring例：例：28.8 图着色图着色Graph Coloring例：例：38.8 图着色图着色Graph Coloring设设 G*是是 连连 通通 平平 面面 图图 G的的 对对 偶偶
2、 图图，n*,m*,r*和和n,m,r分分别别为为G*和和G的的顶顶点数，边数和面数，则点数，边数和面数，则1.n*=r2.m*=m3.r*=n4.设设G*的的顶顶点点vi*位位于于G的的面面Ri中中，则则dG*(vi*)=deg(Ri)。48.8 图着色图着色Graph 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 sam
3、e color.58.8 图着色图着色Graph ColoringDEFINITION The chromatic number(色数色数)of a graph is the least number of colors needed for a coloring of this graph,denoted by 四色定理四色定理THE FOUR COLOR THEOREM The chromatic number of a planar graph is no greater than four.68.8 图着色图着色Graph Coloring五色定理五色定理(Heawood,1890)：
4、用：用种颜色种颜色可以给可以给任何任何简单连通平面图简单连通平面图着色。着色。证明：对结点数证明：对结点数v用归纳法用归纳法a)当当v1，2，3，4，5时显然成立。时显然成立。b)设设vk时成立，现考察时成立，现考察vk+1已知必存在结点已知必存在结点u，使，使deg(u)5，在图，在图G中中删去删去u，得到，得到G-u，由归纳假设知，由归纳假设知G-u可以可以用用5种颜色着色。种颜色着色。78.8 图着色图着色Graph Coloring将将u加入到加入到G-u中，若中，若deg(u)5，必可对，必可对u正常着色，得到一个最多是五色的图正常着色，得到一个最多是五色的图G。G-uu88.8 图
5、着色图着色Graph Coloring将将u加入到加入到G-u中，若中，若deg(u)=5。令令H为为G-u中绿色和蓝色的顶点集合，中绿色和蓝色的顶点集合，F为为G-u中红色和紫色的顶点集合。中红色和紫色的顶点集合。G-uuv3v5v4v2v198.8 图着色图着色Graph Coloring若若v v1 1与与v v3 3属于顶点集属于顶点集H H所导出子图的两个所导出子图的两个不同的连通分支中，将不同的连通分支中，将v v1 1所在分图中的所在分图中的蓝色和绿色对调，在蓝色和绿色对调，在u u上着绿色。上着绿色。G-uuv3v5v4v2v1G-uuv3v5v4v2v1108.8 图着色图着
6、色Graph Coloring若若v v1 1与与v v3 3属于顶点集属于顶点集H H所导出子图的同一个连所导出子图的同一个连通分支中，那么通分支中，那么v v2 2与与v v4 4将分别属于结点集将分别属于结点集F F所所导出子图的两个不同连通分支中。在包含导出子图的两个不同连通分支中。在包含v v2 2的连通分支中将红色和紫色对调，对的连通分支中将红色和紫色对调，对u u着红色着红色。G-uuv3v5v4v2v1118.8 图着色图着色Graph ColoringExample:Try to find a coloring of the graph,including the infin
7、ite region.12韦尔奇韦尔奇鲍威尔鲍威尔（Welch.powell）图着色法：）图着色法：例：用韦尔奇例：用韦尔奇鲍威尔法对图着色鲍威尔法对图着色（1）将将图图中中结结点点数数依依照照度度数数的的递递减减次次序序进进行行排排列；列；上图根据结点度数以递减排列次序为：上图根据结点度数以递减排列次序为：(6)(5)(5)(4)(4)(4)(3)(3)8.8 图着色图着色Graph Coloring13（2）对）对5及及与与5不相邻的结点不相邻的结点1着蓝色；着蓝色；（3）对对3和和与与3不不相相邻邻的的结结点点4、8着着红红色色,对对7和和与与7不相邻的结点不相邻的结点2、6着黄色，着黄
8、色，着色完毕。着色完毕。8.8 图着色图着色Graph Coloring148.8 图着色图着色Graph Coloring15例例：大大学学中中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 Coloring168.8 图着色图着色Graph Coloring思考：思考：Kn的色数是多少？的色数是多少？17