第八章图图着色优秀PPT.ppt

《第八章图图着色优秀PPT.ppt》由会员分享，可在线阅读，更多相关《第八章图图着色优秀PPT.ppt（17页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第八章图图着色1第一页，本课件共有17页8.8 图着色图着色Graph Coloringw例：例：第二页，本课件共有17页8.8 图着色图着色Graph Coloringw例：例：第三页，本课件共有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)。第四页，本课件共有17页8.8 图着色图着色Graph Color

2、ingDEFINITION 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.第五页，本课件共有17页8.8 图着色图着色Graph ColoringDEFINITION The chromatic number(色数色数)of a graph is the least number of colors needed for a colorin

3、g of this graph,denoted by 四色定理四色定理THE FOUR COLOR THEOREM The chromatic number of a planar graph is no greater than four.第六页，本课件共有17页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种颜色着种颜色着色。色。第七页，本课件共有17页8.8 图着色图着色Graph Coloringw将将u加入到加入到G-u中，若中，若deg(u)5，必可对，必可对u正常着色，得到一个最多是五色的图正常着色，得到一个最多是五色的图G。G-uu第八页，本课件共有17页8.8 图着色图着色Graph Coloringw将将u加入到加入到G-u中，若中，若deg(u)=5。令令H为为G-u中绿色和蓝色的顶点集合，中绿色和蓝色的顶点集合，F为为G-u中红色和紫色的顶点集合

5、。中红色和紫色的顶点集合。G-uuv3v5v4v2v1第九页，本课件共有17页8.8 图着色图着色Graph Coloringw若若v v1 1与与v v3 3属于顶点集属于顶点集H H所导出子图的两个所导出子图的两个不同的连通分支中，将不同的连通分支中，将v v1 1所在分图中的所在分图中的蓝色和绿色对调，在蓝色和绿色对调，在u u上着绿色。上着绿色。G-uuv3v5v4v2v1G-uuv3v5v4v2v1第十页，本课件共有17页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第十一页，本课件共有17页8.8 图着色图着色Graph ColoringwExample:Try to find a coloring of the graph,including the infinite region.第十二页，本课件共有17页韦尔奇韦尔奇鲍威尔鲍威尔（Welch.powell）图着色法：）图着色法

7、：例：用韦尔奇例：用韦尔奇鲍威尔法对图着色鲍威尔法对图着色（1）将图中结点数依照度数的递减次序进行排列；）将图中结点数依照度数的递减次序进行排列；上图根据结点度数以递减排列次序为：上图根据结点度数以递减排列次序为：(6)(5)(5)(4)(4)(4)(3)(3)8.8 图着色图着色Graph Coloring第十三页，本课件共有17页（2）对）对5及及与与5不相邻的结点不相邻的结点1着蓝色；着蓝色；（3）对对3和和与与3不不相相邻邻的的结结点点4、8着着红红色色,对对7和和与与7不相邻的结点不相邻的结点2、6着黄色，着色完毕。着黄色，着色完毕。8.8 图着色图着色Graph Coloring第

8、十四页，本课件共有17页8.8 图着色图着色Graph Coloring第十五页，本课件共有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第十六页，本课件共有17页8.8 图着色图着色Graph Coloringw思考：思考：Kn的色数是多少？的色数是多少？第十七页，本课件共有17页