八图图着色.ppt

8.8 图着色Graph Coloring Dual 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. 8.8 图着色Graph Coloring 例： 8.8 图着色Graph Coloring 例： 8.8 图着色Graph Coloring 设G*是连通平面图G的对偶图，n*,m*,r*和n,m,r分别为G*和G的顶点数，边数和面数，则 n*=r m*=m r*=n 设G*的顶点vi*位于G的面Ri中，则dG*(vi*)=deg(Ri)。 8.8 图着色Graph Coloring DEFINITION 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 Coloring DEFINITION 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. 8.8 图着色Graph Coloring 五色定理(Heawood,1890)：用５种颜色可以给任何简单连通平面图着色。 证明：对结点数v用归纳法??? a)当v＝1，2，3，4，5时显然成立。??? b)设v＝k时成立，现考察v＝k+1 已知必存在结点u，使deg(u)≤5，在图G中删去u，得到G-{u}，由归纳假设知G-{u}可以用5种颜色着色。 8.8 图着色Graph Coloring 将u加入到G-{u}中，若deg(u)5，必可对u正常着色，得到一个最多是五色的图G。 8.8 图着色Graph Coloring 将u加入到G-{u}中，若deg(u)=5。 令H为G-{u}中绿色和蓝色的顶点集合， F为G-{u}中红色和紫色的顶点集合。 8.8 图着色Graph Coloring 若v1与v3属于顶点集H所导出子图的两个不同的连通分支中，将v1所在分图中的蓝色和绿色对调，在u上着绿色。 8.8 图着色Graph Coloring 若v1与v3属于顶点集H所导出子图的同一个连通分支中，那么v2与v4将分别属于结点集F所导出子图的两个不同连通分支中。在包含v2的连通分支中将红色和紫色对调，对u着红色。 8.8 图着色Graph Coloring Example: Try to find a coloring of the graph, including the infinite region. 8.8 图着色Graph Coloring 韦尔奇—鲍威尔（Welch.powell）图着色法： 例：用韦尔奇—鲍威尔法对图着色 （1）将图中结点数依照度数的递减次序进行排列； 上图根据结点度数以递减排列次序为： ５　 ３　 ７　 １ ２ 　４　 ６ 　 ８ (6) (5) (5) (4) (4) (4) (3) (3) （2）对5及与5不相邻的结点1着蓝色； （3）对3和与3不相邻的结点4、8着红色,对7和与7不相邻的结点2、6着黄色，着色完毕。 8.8 图着色Graph Coloring 例：大学中7门考试，以下课程中有公共学生，12；13；14；17；23；24；25；27；34；36；37；45；46；56；57；67；问如何在尽可能少的时间段里安排7门考试并使得没有学生在同一时间里有两门考试。 8.8 图着色Graph Coloring 思考：Kn的色数是多少？ * * G-{u} u G-{u} u v3 v5 v4 v2 v1 G-{u} u v3 v5 v4 v2 v1 G-{u} u v3 v5 v4 v2 v1 G-{u} u v3 v5 v4 v2 v1 8.8 图着色Graph Coloring 3 2 5 4 7 6 1