离散数学第七章第六节

第7-6讲对偶图与着色1.着色问题2.对偶图的概念3.正常着色4.WelchPowell着色法5.四色定理6.课堂练习7.第7-6讲作业11、着色问题与平面图密切相关的一个问题是图形的着色。它起源于地图的着色，即让一张地图上相邻的国家着以不同的颜色，最少要用多少种颜色？

100多年前，英国人Guthrie提出了用四种颜色就可以实现对地图的着色。直到1976年，美国伊利诺斯州立大学教师K.Appel和W.Haken借助于大型电子计算机，花费1200多机时，分析了2000多个图，包含几百万种情况，宣称四色猜想成立。但由于程序冗长而复杂，使一些人还想重新证明。22、对偶图的概念（1）定义1给定平面图G=<V,E>，设它有n个面F1，F2，…，Fn。若图G*

=<V*,E*>满足下列条件：(1)对图G任意一个面Fi，其内部有且仅有一个结点vi*属于V*；(2)对图G任意两个面Fi、Fj的公共边界ek有且仅有一条边ek*属于E*，使ek*=（vi*，vj*），且ek*与ek相交；(3)当且仅当ek只是一个面Fi的边界时，vi*有一个环ek*与ek相交。则称图G*是图G的对偶图。对偶图显然是相互的。G*是G的对偶图，则G*也是G的对偶图。特别是连通平面图的对偶图也是平面图。32、对偶图的概念（2）定义2图G的对偶图G*

同构于G，则称图G是自对偶图。自对偶图的例子：43、正常着色

由对偶图的概念，可以将地图的着色转化为对平面图结点的着色。因而四色问题归结为证明对任何一个平面图，可用四种颜色对其结点实施着色，使邻接的结点有不同的颜色。图G的正常着色(简称“着色”)指对G的每个结点指定一种颜色，使邻接的结点具有不同的颜色。如果图G着色用了n种颜色，则称图G是n-色的。图G着色所需的最少颜色数称为G的着色数，记作x(G)。左图着色所需的最少颜色数为4，因此它是4-色的54、WelchPowell着色法至今还没有找出一个简单的方法以确定某个图G是否是n-色的。但可以用WelchPowell方法对图G实施着色，步骤如下：（1）将图G的所有结点按度数递减的次序排列(度数相同的结点次序随意);（2）用第一种颜色对度数最大的结点着色，并按排列次序，依次对与前面已着色点不相邻的结点着上同色；（3）用第二种颜色对结点序列中未着色结点按步骤(2)着色；用第三种颜色继续如法着色，…，直到所有结点全部着色为止。例：对右图着色。解：结点排序：HCFABGDE用红色对H及不相邻的结点A着色；用蓝色对C及不相邻的结点E、G着色；用黄色对F及不相邻的结点B、D着色；64、WelchPowell着色法(续)不用WelchPowell方法对图随意实施着色，可能要多用颜色。前例x(G)=3,下面对图随意着色：用第一色对A及不相邻的结点D着同色；用第二色对B及不相邻的结点E着同色；用第三色对C及不相邻的结点G着同色；用第四色对F着色；用第五色对H着色。75、四色定理定理1x(Kn)=n，Kn是有n个结点的完全图。证：因完全图Kn的每个结点与其它的n-1个结点都邻接，所以每个结点必须着不同的颜色，才能使邻接结点有不同的颜色，故Kn的着色数不少于n。又因n个结点的着色数至多为n,因而x(Kn)=n。定理2任意平面图最多是5-色的。（证明略）

定理3（四色定理）任意平面图最多是4-色的86、课堂练习练习六人在一起，或者三人互相认识，或者三人彼此不认识。解：将6个人分别用平面上A、B、C、D、E、F六点表示。从任一人出发，该人与其它五人或认识，或不认识，如两人认识，则相应两点用红线相连，否则，用蓝线相连。不失一般性，考虑从A开始，与其它五点可以有五条线相连。那么五条线中必有3条会着上相同的颜色。假定AB、AC、AD为兰色，如果此时BC、CD、BD中有一条边为蓝色