第四节平面图的着色精选PPT.ppt
第四节平面图的着色第1页，此课件共10页哦12341324第2页，此课件共10页哦定义定义2 2 图的着色图的着色是对该图的每个顶点都指定一种颜色，是对该图的每个顶点都指定一种颜色，使没有两个相邻的顶点指定为相同的颜色。如果这些顶使没有两个相邻的顶点指定为相同的颜色。如果这些顶点选自于一个有点选自于一个有k k种颜色的集合，而不管种颜色的集合，而不管k k种颜色是否都种颜色是否都用到，这样的着色用到，这样的着色称为称为k k着色着色。定义定义3 3 图图G G的色数的色数是着色这个图是着色这个图G G所需要的最少颜色数。记作所需要的最少颜色数。记作(G)(G)。图图G的色素也称为的色素也称为图图G的点色素的点色素.从定义可知从定义可知,对于对于G的任的任何子图何子图H,均有均有x(H)x(G).若若G是是n阶完全图阶完全图,若若G是是n阶完全图阶完全图,则则x(G)=n;若若G是至少有一边的二分图是至少有一边的二分图,则则x(G)=2;若若G是长为奇数的圈是长为奇数的圈,则则x(G)=3.当当x(G)3时时,G的特征的特征至今尚未清楚至今尚未清楚,在下一节在下一节,将给出将给出G的色素的色素x(G)的一个上界的一个上界.第3页，此课件共10页哦定理定理1 1 设设u u和和v v是图是图G G中两个不相邻的顶点中两个不相邻的顶点,则则(G)=min(G)=min(G+u,v),(G+u,v),(G(Gu,v),u,v),其中其中G Gu,vu,v是把是把G G中结点中结点u u与与v v重合成一个新结点，且重合成一个新结点，且G G中分别与中分别与u u与与v v关联的边都与该新结点关联。关联的边都与该新结点关联。证明证明:记记e=u,v,e=u,v,（1 1）设）设x(G)=k,x(G)=k,并考虑并考虑G G的的K K着色着色.假设顶点假设顶点u u与与v v染不同的颜色染不同的颜色,则则G G的的k k着色也是着色也是G+eG+e的的k k着色着色.此时此时x(G+e)x(G+e)k=x(G).k=x(G).现假设顶点现假设顶点u u和和v v的染色相同的染色相同,则则G G的一个的一个k k染色可得到染色可得到G Ge e的一个染色的一个染色.故故(G(Ge)e)k=x(G).k=x(G).又在又在G G的的k k染染色中色中,或者或者u u与与v v染为不同的颜色染为不同的颜色,或者为相同的颜色或者为相同的颜色,故故minmin(G+u,v),(G+u,v),(G(Gu,v)u,v)x(G).x(G).第4页，此课件共10页哦 （2）G是G+e的子图,显然x(G)x(G+e).设(G(Ge)=ke)=k1 1,并把结点并把结点u u和和v v重合所得的新结点记重合所得的新结点记为为y,y,则在则在G Ge e的的k k1 1着色中着色中,把分配给把分配给y y的颜色分配给的颜色分配给G G中中u u和和v(u,vv(u,v不相邻不相邻),),即可得到即可得到G G的一个的一个k k1 1着色着色.故故 x(G)x(G)k1=x(G(Ge)e)所以所以x(G)x(G)minmin(G+e),(G+e),(G(Gu,v).u,v).综（综（1 1）（）（2 2）所述）所述,有有 (G)=min(G)=min(G+u,v),(G+u,v),(G(Gu,v).u,v).四色问题四色问题:连通简单平面图的色素不超过连通简单平面图的色素不超过4.4.四色问题是盖思里于四色问题是盖思里于18521852年提出年提出,后经众多数后经众多数学家尝试证明学家尝试证明,均以失败告终均以失败告终.1976.1976年年,美国数学家美国数学家阿佩尔和黑肯宣布借助用计算机证明阿佩尔和黑肯宣布借助用计算机证明,但时间超过但时间超过了了10001000小时小时,其可靠性仍在置疑之中其可靠性仍在置疑之中.第5页，此课件共10页哦定理定理2 2（五色定理）连通简单平面图（五色定理）连通简单平面图G G的色数为不超过的色数为不超过5.5.证明证明:对图的顶点数对图的顶点数n作归纳作归纳.n 5时时,结论显然结论显然.若若n-1个顶点时结论成立个顶点时结论成立.下证下证有有n个顶点时结论也成立个顶点时结论也成立.由于由于G是平面图是平面图,则则(G)5.故在故在G中至少存在一个顶点中至少存在一个顶点v0,其度数其度数d(v0)5.在图中删去顶点在图中删去顶点v0得图得图G,由归纳假设知由归纳假设知G的色素的色素为为5.然后将然后将v0又加回去又加回去,有两种情况有两种情况:(1)d(v0)5或或d(v0)=5但和但和v0邻接的邻接的5个结点的颜色数个结点的颜色数小于小于5.则则v0极易着色极易着色,只要选择与四周顶点不同的只要选择与四周顶点不同的颜色着色即可颜色着色即可.第6页，此课件共10页哦(2)d(v0)=5且和且和v0邻接着的邻接着的5个结点着的颜色的是个结点着的颜色的是5种颜色种颜色,如下图如下图(a)所示所示.称称G中所有红黄色顶点为中所有红黄色顶点为红黄集红黄集,称称G G中所有黑白色顶点为黑白集中所有黑白色顶点为黑白集.故又有故又有两种可能两种可能.(i)v(i)v1 1和和v v3 3属于红黄集导出子图的两个不同块中属于红黄集导出子图的两个不同块中,如如下图下图(b)(b)所示所示.将将v v1 1所在块的红黄色对调所在块的红黄色对调,并不影并不影响响G G的正常着色的正常着色.然后将然后将v v0 0着上红色着上红色,即的图即的图G G的的正常着色正常着色.蓝v3 黑v4v0黄v3白v2红v1(a)(b)第7页，此课件共10页哦(ii)v(ii)v1 1和和v v3 3属于红黄集导出子图的同一块中属于红黄集导出子图的同一块中,则则v v1 1和和v v3 3之间必有一条属于红黄集的路之间必有一条属于红黄集的路P,PP,P加上结点加上结点v v0 0可可构成圈构成圈C:vC:v0 0v v1 1pvpv3 3v v0 0,如下图如下图所示所示.由于由于C C的存在的存在,将将黑白集分成两个子集黑白集分成两个子集,一个在一个在C C内内,一个在一个在C C外外.于是于是问题转化为问题转化为(i)(i)的类型的类型,对黑白集按对黑白集按(i)(i)型的办法处型的办法处理理,即得图即得图G G的正常着色的正常着色.蓝v3 黑v4v0黄v3白v2红v1(b)(c)(a)第8页，此课件共10页哦例例1 1求下图求下图G G和和H H的色数的色数acfgbedGHa:a:红红,b:,b:蓝蓝,c:,c:绿绿,d:,d:红红,e:e:绿，绿，f:f:蓝蓝,g:g:红红(3色色)第9页，此课件共10页哦例例2.2.由由n(nn(n 3)3)个顶点个顶点v v1 1,v,v2 2,v,vn n以及边以及边vv1 1,v,v2 2,vv2 2,v,v3 3,v,vn-1n-1,v,vn n v vn n,v,v1 1 组成的图称为圈图组成的图称为圈图,记记作作C Cn n,试问圈图的试问圈图的C Cn n的色数是多少。（分的色数是多少。（分n n为奇数，或偶为奇数，或偶数）数）例例3.K3.Kn n和和K Km,nm,n的色数分别是多少？的色数分别是多少？解解:由于由于K Kn n的每两个顶点都相邻的每两个顶点都相邻,而当两个相邻的顶点而当两个相邻的顶点必指定不同的颜色必指定不同的颜色,故故K Kn n的色素为的色素为n.n.K Km,nm,n的色数为的色数为2.2.用一种颜色着色用一种颜色着色m m个顶点个顶点,用另一种用另一种颜色着色颜色着色n n个顶点个顶点.第10页，此课件共10页哦
