7-6 对偶图与着色

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,7-6,对偶图与着色,掌握对偶图的定义，会画图,G,的对偶图,G,*,掌握自对偶图的定义及必要条件。,与平面图有密切关系的一个图论的应用是图形的着色问题，这个问题最早起源于地图的着色，一个地图中相邻国家着以不同颜色，那么最少需用多少种颜色？一百多年前，英国格色里,(Guthrie),提出了用四种颜色即可对地图着色的猜想，,1879,年肯普,(,Kempe,),给出了这个猜想的第一个证明，但到,1890,年希伍德,(,Hewood,),发现肯普证明是错误的，但他指出肯普的方法 虽不能证明地图着色用四种颜色就够了，但可证明用五种颜色就够了，即五色定理成立。,此后四色猜想一直成为数学家感兴趣而未能解决的难题。直到,1976,年美国数学家阿佩尔和黑肯宣布：他们用电子计算机证明了四色猜想是成立的。所以从,1976,年以后就把四色猜想这个名词改成“四色定理”了。为了叙述图形着色的有关定理，下面先介绍对偶图的概念。,一、对偶图,1,、对偶图,定义,7-6.1,对具有面,F,1,F,2,.,F,n,的连通平面图,G=,实施下列步骤所得到的图,G*,称为图,G,的,对偶图,（,dual of graph,）：,如果存在一个图,G,*,=,满足下述条件：,（,a,）在,G,的每一个面,F,i,的内部作一个,G*,的顶点,v,i,*,。,即,对图,G,的任一个面,F,i,内部有且仅有一个结点,v,i,*,V,*,。,(b),若,G,的面,F,i,，,F,j,有公共边,e,k,，,则作,e,k,*,=(v,i,*,，,v,j,*,),，且,e,k,*,与,e,k,相交。,即若,G,中面,F,i,与,F,j,有公共边界,e,k,，,那么过边界的每一边,e,k,作关联,v,i,*,与,v,j,*,的一条边,e,k,*=(v,i,*,v,j,*),。,e,k,*,与,G*,的其它边不相交。,(c),当且仅当,e,k,只是一个面,F,i,的边界时,(,割边,),，,v,i,*,存在一个环,e,*,k,与,e,k,相交。,即当,e,k,为单一面,F,i,的边界而不是与其它面的公共边界时，作,v,i,*,的一条环与,e,k,相交（且仅交于一处）。所作的环不与,G*,的边相交。,则称图,G,*,为,G,的对偶图。,v,*,=r，e,*,=e，r,*,=v,说明：,v,*,=r,，,e,*,=e,，,r,*,=v,。,平面图的对偶图仍满足欧拉定理，且仍是平面图。,例 画出下图的对偶图。,(a)v*=5,e*=8,r*=5,(b)v*=7,e*=13,r*=12,(c)v*=5,e*=6,r*=3,(d)v*=7,e*=12,r*=7,2,、自对偶图,定义,7-6.2,如果图,G,的对偶图,G*,同构于,G,则称,G,是自对偶图。,若图,G,是自对偶的，则,v=v,*,，,e=e,*,，即,r,*,=v=v,*,=r,，,e=e,*,则由欧拉定理,v-e+r=2,得,v-e+v=2,，即,e=2v-2,。,若图,G,是自对偶的，则,e=2v-2,。,由此，,K,4,是自对偶图，,K,3,不是自对偶。,4,个结点，,6,条边,3,个结点，,3,条边,证明：若图,G,是自对偶的，则,e=2v-2,。,二、图的着色,1,、问题的提出,该问题起源于地图的着色问题。,对点的着色就是对图,G,的每个结点指定一种颜色，使得相邻结点的颜色不同，对边着色就是，给每条边指定一种颜色使得相邻的边的颜色不同，给面着色就是给每个面指定一种颜色使得有公共边的两个面有不同的颜色。对边着色和对面着色均可以转化为对结点着色问题。,从对偶图的概念，我们可以看到，对于地图的着色问题，可以归纳为对于平面图的结点的着色问题，因此四色问题可以归结为要证明对于任何一个平面图，一定可以用四种颜色，对它的结点进行着色，使得邻接的结点都有不同的颜色。,2,、图的正常着色：图,G,的正常着色,(,或简称着色,),是指对它的每一个结点指定一种颜色，使得没有两个邻接的结点有同一种颜色。如果图在着色时用了,n,种颜色，我们称,G,为,n-,色的。,3,、色数：对于图,G,着色时，需要的最少颜色数称为,G,的色数，记作,x(G),。,证明一个图的色数为,n,，,首先必须证明用,n,种颜色可以着色该图，其次证明用少于,n,种颜色不能着色该图。,4,、对点着色的鲍威尔方法：,第一步：对每个结点按度数递减次序进行排列,(,相同度数的结点次序可随意,),第二步：用第一种颜色对第一个结点着色，并按次序对与前面着色点不相邻的每一点着同样的颜色。,第三步：用第二种颜色对未着色的点重复第二步，用第三种颜色继续这种做法，直到全部点均着了色为止。,5,、定理,7-6.1,：对于完全图,K,n,有,(K,n,)=n,。,证明：因为完全图的每一个结点与其他各个结点都邻接，故,n,个结点的着色数不能少于,n,，又,n,个结点的着色数至多为,n,，故,(K,n,)=n,。,6,、定理,7-6.2,：连通平面图,G=,至少有三个结点，则必有一点,uV,使得,deg(u)5,。,证明：设,|V|=v,，,|E|=e,，若,G,的每个结点均有,v,deg(u)6,，,deg(,v,i,)=2|E|=,2e,i=1,则有,2e6v,，即,e3v3v-6,，,与定理矛盾。,7,、定理,7-6.3,：,(,五色定理,),任意平面图最多是,5-,色的。,证明思路：对结点个数,v,采用归纳法,(1)归纳基础：图,G,的结点数为,v=1,2,，,3,，,4,，,5,时，结论成立。,(2),归纳假设：设,G,有,k,个结点时结论成立。即,G,是,最多可,5-,着色的,。,(3),归纳推理：需要证明,G,有,k+1,个结点时结论仍成立。,先在,G,中删去度数小于,5,的结点,u,根据归纳假设，所得的图,G-u,有,k,个结点,结论成立。然后考虑在,G-u,中加上一个结点的情况。若加入的结点满足,deg(u)5,，,则可以对,u,正常着色。若加入的结点满足,deg(u)=5,，,则与它邻接的,5,个结点可以用,4,种颜色着色。分两中情况证明：,.,对调,v,1,v,3,两个结点的颜色后，给着,v,1,的颜色。,.,对调,v,2,v,4,两个结点的颜色后，给着,v,2,的颜色。,自从四色猜想提出后，一百多年来，一直成为数学上的著名难题，它吸引许许多多的人，为之而作出大量辛劳，也得到很多重要结果，但长久未能得到解决。直到,1976,年,6,月，由美国伊利诺斯大学两名数学家爱普尔,(K.I.Apple),、,黑肯,(,W.Haken,),在考西,(J.Koch),帮助下借助于电子计算机，用了一百多亿次逻辑判断，花了,1200,多机时才证明四色猜想是成立的，从此宣告，四色猜想成为四色定理。现将它叙述如下：,相应地有下面的定理。,9,、定理：对于任何地图,M,，,M,是四着色的，,即,(M)4,。,8,、四色定理：平面图的色数不超过,4,。,