平面图_精品文档.pptVIP

3.对G着色方法:(介绍韦尔奇.鲍威尔法Welch.Powell)具体步骤:(1)将图中所有点按度数大小递减排列(此排序可能不唯一,因为可能有些结点的度数相同).(2)用第一种颜色对第一个点(度数最大的点)着色,并且按排列顺序对与前面着色点不相邻的每个点着上同样的颜色.(3)用第二种颜色对尚未着色的点重复步骤。(4)用第三种颜色继续这种做法,直到所有的点全部着上色为止.例1.用WelchPowell法对下图着色.解:a)根据递减次序排列各点v5,v3,v7,v1,v2,v4,v6,v8b)对v5点和与它不相邻的v1点着第一种颜色.c)第二种颜色对v3着色,并对不相邻点v4,v8也着第二种颜色.d)对点v7和与它不相邻的点v2,v6着第三种颜色.∵G不可能是2—颜色的(∵G中有v1,v2,v3互相邻接.)∴x(G)=3.五.应用举例安排期末考试(学分制),不能使一个学生在同一个时间参加两门课的考试.设有七门课程,分别记作A,B,C,D,E,F,G.如果两门课程有共同的学生在读,就在两门课程之间连一直线.得到图:结点度数递减排序:B,C,D,G,A,E,F对图正常着色后,标有同一种颜色的课,可以同时考试.安排考试日程:周一:A周二:B,F周三:C,E周四:D,GG?F?E??C?B?D?A定理:对任意图G,有x(G)≦?+1,其中?为G中顶点的最大度.证明:用归纳法.设|V(G)|=n,显然,当n=1时,??0,x(G)=1,定理成立.假设定理对顶点个数?n-1时成立.设v是G的任一顶点,由归纳假设,x(G-v)??1+1.其中?1为G-v中顶点的最大度.自然?1??.∴x(G-v)??+1.用?+1种颜色对G-v着色.设与v邻接的顶点是vi1,vi2,…,vik用c1,c2,…,ck分别表示顶点vi1,vi2,…,vik所着的颜色,∵k??,故从?+1种颜色中必然可以找到一种颜色ck+1(ck+1?cj,j=1,2,…,k).对v着颜色ck+,得到G的正常这色,所以定理成立.五色定理:每个平面图都是5顶点可着色的.证:设G=V,E是平面图,对|V|=n归纳.n=1,2,3,4,5时定理显然成立.假设n=k时成立,则当n=k+1时,∵G是平面图,∴δ?5.即存在u,使d(u)?5.由归纳假设G-{u}是5顶点可着色的,设(V1,V2,V3,V4,V5)是G-{u}的一个正常的5顶点着色,若d(u)5,则与u邻接的点数?4.显然可对u着色,而得到G的一个正常的5顶点着色.若d(u)=5,设与u邻接的点v1,v2,v3,v4,v5,且不妨设vi?Vi(i=1,2,3,4,5),用Gij表示由Vi?Vj导出的子图,即Gij=G[Vi?Vj](i?j).①若?vi,vj,使vi与vj属于Gij的两个不同的连通分支,则在vi所在分支中交换颜色i和j,得到G-u的一个新的正常5着色,其中只有四种颜色分配给u的邻点(无颜色i),此时只需给u着以颜色i即可.②对?i?j,vi,vj属于Gij的同一个连通分支,设Pij是Gij中的vi—vj路,并将圈uv1P13v3u记为C.∵C分隔v2和v4(即v2?intC,v4?extC).由Jordan曲线定理知,路P24必然与C相遇于某一点.∵G是平图,这个点必然是顶点,但这是不可能的.因为P24的顶点只有颜色2和4,而C的顶点不具有这两种颜色.矛盾.面着色k面着色:k种颜色给平面图G的所有面的一个分配.正常的面着色:若被一条边分隔的两个面分配以不同的颜色.k面可着色:若G有一个正常的k面着色.面色数x*(G)=使G是k面可着色的最小k值,显然x*(G)=x(G*).可以证明:每个平面图都是k顶点可着色的?每个平面图都是k面可着色的.四色问题:每个平面图是4面可着色的.8-7平面图PlaneGraph在实际应用中,如高速公路设计、印刷电路设计,都要求线路不交叉,这就是平面图,一个图能否画在一个平面上,且任何边都不交叉,这就是图的平面化问题.这个问题在近些年来,特别是大规模集成电路的发展进一步促进了对平面图的研究.1.定义设G是无向图,如果能将G的所有结点和边都画在一个平