左图着色所需的最少颜 色数为4，因此它是4-色 的
5ቤተ መጻሕፍቲ ባይዱ
4、Welch Powell着色法
至今还没有找出一个简单的方法以确定某个图G是否是n-色 的。但可以用Welch Powell方法对图G实施着色，步骤如下：
（1）将图G的所有结点按度数递减的次序排列(度数相同的结 点次序随意); （2）用第一种颜色对度数最大的结点着色，并按排列次序， 依次对与前面已着色点不相邻的结点着上同色； （3）用第二种颜色对结点序列中未着色结点按步骤(2)着色； 用第三种颜色继续如法着色，…，直到所有结点全部着色为止。
2
2、对偶图的概念（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的对偶图。
7
5、四色定理
定理1 x(Kn)=n，Kn是有n个结点的完全图。
证：因完全图Kn的每个结点与其它的n-1个结点都邻接，所以每个 结点必须着不同的颜色，才能使邻接结点有不同的颜色，故Kn的 着色数不少于n。又因n个结点的着色数至多为n, 因而x(Kn)=n。 定理2 任意平面图最多是5-色的。
（证明略） 定理3（四色定理）任意平面图最多是4-色的
第7-6讲 对偶图与着色
1. 着色问题 2. 对偶图的概念 3. 正常着色 4. Welch Powell着色法 5.四色定理 6. 课堂练习 7. 第7-6讲 作业
1
1、着色问题
与平面图密切相关的一个问题是图形的着色。它起源于地 图的着色，即让一张地图上相邻的国家着以不同的颜色，最 少要用多少种颜色？ 100多年前，英国人Guthrie提出了用四种颜色就可以实现 对地图的着色。 直到1976年，美国伊利诺斯州立大学教师K.Appel和 W.Haken借助于大型电子计算机，花费1200多机时，分析了 2000多个图，包含几百万种情况，宣称四色猜想成立。但由 于程序冗长而复杂，使一些人还想重新证明。
例：对右图着色。
解：结点排序：HCFABGDE 用红色对H及不相邻的结点A着色； 用蓝色对C及不相邻的结点E、G着色； 用黄色对F及不相邻的结点B、D着色；
6
4、Welch Powell着色法(续)
不用Welch Powell方法对图随意实施着色，可能要多用颜色。 前例x(G)=3,下面对图随意着色： 用第一色对A及不相邻的结点D着同色； 用第二色对B及不相邻的结点E着同色； 用第三色对C及不相邻的结点G着同色； 用第四色对F着色； 用第五色对H着色。
9
第7-6讲 作业
P321 1
10
对偶图显然是相互的。G*是G 的对偶图，则G*也是G的对偶 图。特别是连通平面图的对偶 图也是平面图。
3
2、对偶图的概念（2）
定义2 图G的对偶图G* 同构于G，则称图G是自对偶图。
自对偶图的例子：
4
3、正常着色
由对偶图的概念，可以将地图的着色转化为对平面图结点 的着色。因而四色问题归结为证明对任何一个平面图，可用四 种颜色对其结点实施着色，使邻接的结点有不同的颜色。 图G的正常着色(简称“着色”)指对G的每个结点指定一种 颜色，使邻接的结点具有不同的颜色。如果图G着色用了n种 颜色，则称图G是n-色的。图G着色所需的最少颜色数称为G的 着色数，记作x(G)。
8
6、课堂练习
练习 六人在一起，或者三人互相认识，或者三人彼此不认识。 解：将6个人分别用平面上A、 B、C、 D、E、F六 点表示。从任一人出发，该人与其它五人或认识， 或不认识，如两人认识，则相应两点用红线相连， 否则，用蓝线相连。不失一般性，考虑从A开始， 与其它五点可以有五条线相连。那么五条线中必有 3条会着上相同的颜色。假定AB、AC、AD为兰色， 如果此时 BC 、 CD 、 BD 中有一条边为蓝色，则可 构成一个蓝色三角形，因而六人中有三人不认识； 如果此时 BC 、 CD 、 BD 全为红色，则 B 、 C 、 D 彼 此认识，因而六人中有三人认识。