第八章图图着色优秀课件.ppt
第八章图图着色1第1页，本讲稿共17页8.8 图着色图着色Graph Coloringw例：例：第2页，本讲稿共17页8.8 图着色图着色Graph Coloringw例：例：第3页，本讲稿共17页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)。第4页，本讲稿共17页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.第5页，本讲稿共17页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.第6页，本讲稿共17页8.8 图着色图着色Graph Coloringw五色定理五色定理(Heawood,1890)：用：用种颜色种颜色可以给任何可以给任何简单连通平面图简单连通平面图着色。着色。证明：对结点数证明：对结点数v用归纳法用归纳法a)当当v1，2，3，4，5时显然成立。时显然成立。b)设设vk时成立，现考察时成立，现考察vk+1已知必存在结点已知必存在结点u，使，使deg(u)5，在图，在图G中删中删去去u，得到，得到G-u，由归纳假设知，由归纳假设知G-u可以用可以用5种种颜色着色。颜色着色。第7页，本讲稿共17页8.8 图着色图着色Graph Coloringw将将u加入到加入到G-u中，若中，若deg(u)5，必可对，必可对u正常着色，得到一个最多是五色的图正常着色，得到一个最多是五色的图G。G-uu第8页，本讲稿共17页8.8 图着色图着色Graph Coloringw将将u加入到加入到G-u中，若中，若deg(u)=5。令令H为为G-u中绿色和蓝色的顶点集合，中绿色和蓝色的顶点集合，F为为G-u中红色和紫色的顶点集合。中红色和紫色的顶点集合。G-uuv3v5v4v2v1第9页，本讲稿共17页8.8 图着色图着色Graph Coloringw若若v v1 1与与v v3 3属于顶点集属于顶点集H H所导出子图的两个所导出子图的两个不同的连通分支中，将不同的连通分支中，将v v1 1所在分图中的所在分图中的蓝色和绿色对调，在蓝色和绿色对调，在u u上着绿色。上着绿色。G-uuv3v5v4v2v1G-uuv3v5v4v2v1第10页，本讲稿共17页8.8 图着色图着色Graph Coloringw若若v v1 1与与v v3 3属于顶点集属于顶点集H H所导出子图的同一个连通分支所导出子图的同一个连通分支中，那么中，那么v v2 2与与v v4 4将分别属于结点集将分别属于结点集F F所导出子图的所导出子图的两个不同连通分支中。在包含两个不同连通分支中。在包含v v2 2的连通分支中将的连通分支中将红色和紫色对调，对红色和紫色对调，对u u着红色着红色。G-uuv3v5v4v2v1第11页，本讲稿共17页8.8 图着色图着色Graph ColoringwExample:Try to find a coloring of the graph,including the infinite region.第12页，本讲稿共17页韦尔奇韦尔奇鲍威尔鲍威尔（Welch.powell）图着色法：）图着色法：例：用韦尔奇例：用韦尔奇鲍威尔法对图着色鲍威尔法对图着色（1）将图中结点数依照度数的递减次序进行排列；）将图中结点数依照度数的递减次序进行排列；上图根据结点度数以递减排列次序为：上图根据结点度数以递减排列次序为：(6)(5)(5)(4)(4)(4)(3)(3)8.8 图着色图着色Graph Coloring第13页，本讲稿共17页（2）对）对5及及与与5不相邻的结点不相邻的结点1着蓝色；着蓝色；（3）对对3和和与与3不不相相邻邻的的结结点点4、8着着红红色色,对对7和和与与7不不相邻的结点相邻的结点2、6着黄色，着色完毕。着黄色，着色完毕。8.8 图着色图着色Graph Coloring第14页，本讲稿共17页8.8 图着色图着色Graph Coloring第15页，本讲稿共17页例例：大大学学中中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第16页，本讲稿共17页8.8 图着色图着色Graph Coloringw思考：思考：Kn的色数是多少？的色数是多少？第17页，本讲稿共17页
