第八章图图着色.ppt

第八章图图着色1第一页，共十七页，2022年，8月28日 8.8 图着色Graph Coloring例：第二页，共十七页，2022年，8月28日 8.8 图着色Graph Coloring例：第三页，共十七页，2022年，8月28日 8.8 图着色Graph Coloring设G*是连通平面图G的对偶图，n*,m*,r*和n,m,r分别为G*和G的顶点数，边数和面数，则n*=rm*=mr*=n设G*的顶点vi*位于G的面Ri中，则dG*(vi*)=deg(Ri)。第四页，共十七页，2022年，8月28日 8.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 same color. 第五页，共十七页，2022年，8月28日 8.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.第六页，共十七页，2022年，8月28日 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种颜色着色。第七页，共十七页，2022年，8月28日 8.8 图着色Graph Coloring将u加入到G-{u}中，若deg(u)5，必可对u正常着色，得到一个最多是五色的图G。G-{u}u第八页，共十七页，2022年，8月28日 8.8 图着色Graph Coloring将u加入到G-{u}中，若deg(u)=5。令H为G-{u}中绿色和蓝色的顶点集合，F为G-{u}中红色和紫色的顶点集合。G-{u}uv3v5v4v2v1第九页，共十七页，2022年，8月28日 8.8 图着色Graph Coloring若v1与v3属于顶点集H所导出子图的两个不同的连通分支中，将v1所在分图中的蓝色和绿色对调，在u上着绿色。 G-{u}uv3v5v4v2v1G-{u}uv3v5v4v2v1第十页，共十七页，2022年，8月28日 8.8 图着色Graph Coloring若v1与v3属于顶点集H所导出子图的同一个连通分支中，那么v2与v4将分别属于结点集F所导出子图的两个不同连通分支中。在包含v2的连通分支中将红色和紫色对调，对u着红色。 G-{u}uv3v5v4v2v1第十一页，共十七页，2022年，8月28日 8.8 图着色Graph ColoringExample: Try to find a coloring of the graph, including the infinite region.第十二页，共十七页，2022年，8月28日 韦尔奇—鲍威尔（Welch.powell）图着色法：例：用韦尔奇—鲍威尔法对图着色（1）将图中结点数依照度数的递减次序进行排列； 上图根据结点度数以递减排列次序为：５　 ３　 ７　 １ ２ 　４　 ６ 　 ８(6) (5) (5) (4) (4) (4) (3) (3)8.8 图着色Graph Coloring第十三页，共十七页，2022年，8月28日 （2）对5及与5不相邻的结点1着蓝色；（3）对3和与3不相邻的结点4、8着红色,对7和与7不相邻的结点2、6着黄色，着色完毕。 8.8 图着色Graph Coloring第十四页，共十七页，2022年，8月28日 8.8 图着色Graph Coloring第十五页，共十七页，2022年，8月28日 例：大学中7门考试，以下课程中有公共学生，12；13；14；17；23；24；25；27；34；36；37；45；46；56；57；67；问如何在尽可能少的时间段里安排7门考试并使得没有学生