《平面图的着色》PPT课件

《《平面图的着色》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四节平面图的着色定义1设G是无孤立结点的连通的平面图，且G有K个面F1，F2，…Fk(包括外部面).则按下列过程作G的对偶图G.（1）在G的每个面内设置一个结点vi(1ik)。（2）过Fi与Fj的每一条公共边ek作一条仅作一条边{vi,vj}与ek相交。（3）当且仅当ek只是Fi的边界时，vi恰有一自回路与ek相交。这样所得的图G*称为图G的对偶图.若G*与G同构,称G是自对偶的.如下图G的对偶图为图中虚线.12341324定义2图的着色是对该图的每个顶点都指定一种颜色，使没有两个相邻的顶点指定为相同的颜色。如果这些顶点选自于一个有k种颜色的集合，而不管k种颜色是否都用到，这样

2、的着色称为k着色。定义3图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)的一个上界.定理1设u和v是图G中两个不相邻的顶点,则(G)=min{(G+{u,v}),(G•{u,v})},其中G•{u,v}是把G中结点u与v重合成一个新结点，且G中分别与u与v关联的边都与该新结点关联。证明:

3、记e={u,v},（1）设x(G)=k,并考虑G的K着色.假设顶点u与v染不同的颜色,则G的k着色也是G+e的k着色.此时x(G+e)k=x(G).现假设顶点u和v的染色相同,则G的一个k染色可得到G•e的一个染色.故(G•e)k=x(G).又在G的k染色中,或者u与v染为不同的颜色,或者为相同的颜色,故min{(G+{u,v}),(G•{u,v})}x(G).（2）G是G+e的子图,显然x(G)x(G+e).设(G•e)=k1,并把结点u和v重合所得的新结点记为y,则在G•e的k1着色中,把分配给y的颜色分配给G中u和v(u,v不相邻),即可得到G的一个k1着色.故x

4、(G)k1=x(G•e)所以x(G)min{(G+e),(G•{u,v})}.综（1）（2）所述,有(G)=min{(G+{u,v}),(G•{u,v})}.四色问题:连通简单平面图的色素不超过4.四色问题是盖思里于1852年提出,后经众多数学家尝试证明,均以失败告终.1976年,美国数学家阿佩尔和黑肯宣布借助用计算机证明,但时间超过了1000小时,其可靠性仍在置疑之中.定理2（五色定理）连通简单平面图G的色数为不超过5.证明:对图的顶点数n作归纳.n5时,结论显然.若n-1个顶点时结论成立.下证有n个顶点时结论也成立.由于G是平面图,则(G)5.故在G中至少存在一

5、个顶点v0,其度数d(v0)5.在图中删去顶点v0得图G’,由归纳假设知G’的色素为5.然后将v0又加回去,有两种情况:(1)d(v0)<5或d(v0)=5但和v0邻接的5个结点的颜色数小于5.则v0极易着色,只要选择与四周顶点不同的颜色着色即可.(2)d(v0)=5且和v0邻接着的5个结点着的颜色的是5种颜色,如下图(a)所示.称G’中所有红黄色顶点为红黄集,称G’中所有黑白色顶点为黑白集.故又有两种可能.(i)v1和v3属于红黄集导出子图的两个不同块中,如下图(b)所示.将v1所在块的红黄色对调,并不影响G’的正常着色.然后将v0着上红色,即的图G的正常着色.蓝v3黑v4v0黄v

6、3白v2红v1(a)(b)(ii)v1和v3属于红黄集导出子图的同一块中,则v1和v3之间必有一条属于红黄集的路P,P加上结点v0可构成圈C:v0v1pv3v0,如下图©所示.由于C的存在,将黑白集分成两个子集,一个在C内,一个在C外.于是问题转化为(i)的类型,对黑白集按(i)型的办法处理,即得图G的正常着色.蓝v3黑v4v0黄v3白v2红v1(b)(c)(a)例1求下图G和H的色数acfgbedGHa:红,b:蓝,c:绿,d:红,e:绿，f:蓝,g:红(3色)例2.由n(n3)个顶点v1,v2,…,vn以及边{v1,v2},{v2,v3},…,{vn-1,vn}{vn,v1}组成

7、的图称为圈图,记作Cn,试问圈图的Cn的色数是多少。（分n为奇数，或偶数）例3.Kn和Km,n的色数分别是多少？解:由于Kn的每两个顶点都相邻,而当两个相邻的顶点必指定不同的颜色,故Kn的色素为n.Km,n的色数为2.用一种颜色着色m个顶点,用另一种颜色着色n个顶点.