第6章染色理论

1、1返回 结束 许多实际问题可以归结为求图的匹配或者独立集。此外，许多实际问题可以归结为求图的匹配或者独立集。此外，在许多应用中，人们希望知道：在许多应用中，人们希望知道： 一个给定的图，它的边集至少能划分成多少个一个给定的图，它的边集至少能划分成多少个边不交的边边不交的边独立集独立集（匹配）？（匹配）？ 或它的顶点集至少能划分成多少个或它的顶点集至少能划分成多少个点不交的点独立集点不交的点独立集？ 这便是图的这便是图的边染色和顶点染色问题边染色和顶点染色问题。第6章 染色理论2返回 结束点的点的k染色染色 (vertex k-coloring) 设设G是一个无环图。是一个无环图。G的顶点正常的

2、顶点正常k 染色染色 是指是指 k 种颜色种颜色 1, 2, , k 对于对于G的各顶点的一种分配，使得任意的各顶点的一种分配，使得任意两个相邻的顶两个相邻的顶点所染颜色不同点所染颜色不同。换句话说，换句话说，G 的顶点正常的顶点正常k 染色染色 是一个映射是一个映射 : V (G)1,2, k, 使得使得-1(i) 是是独立集独立集 或或 空集空集 (i = 1,2, k) .第1节 点染色3返回 结束v注：注： 设设 是是G 的一个顶点正常的一个顶点正常k 染色。令染色。令 V i =-1(i) = xV (G) | (x) = i ，（，（i = 1,2, k ）。）。 则则 实际上是对

3、顶点集实际上是对顶点集 V(G) 的一种划分：的一种划分： = (V1 , V2 , , Vk )， 其中其中Vi Vj= , Vi =V，且每个，且每个Vi 是独立集或空集是独立集或空集 (i = 1,2,k) 。例：例：第1节 点染色4返回 结束v(点点) k色可染的色可染的(vertex k-colorable) 若存在若存在G 的一种顶点的一种顶点k染色，则称图染色，则称图G 是点是点k 色可染的，有时简色可染的，有时简称为称为 k 色可染的或可色可染的或可k 染色的。染色的。v注：注： 每个图每个图G一定是一定是(G) 色可染的。色可染的。 若图若图G是是k色可染的色可染的, 则对任

4、何正整数则对任何正整数mk, G也也m色可染的。色可染的。v点色数点色数 (chromatic number) 设设G 是无环边的图，称是无环边的图，称 (G)为为G的点色数的点色数(简称简称色色数数)。 (G) = mink |G 是是k 色可染的色可染的v k色图色图(k-chromatic graph) 若若(G) = k ，则称，则称G为为k色图。色图。第1节 点染色5返回 结束v注：注：v（1）若）若(G) = k（即（即G是是k 色图），则色图），则G中任何点中任何点k染色染色 = (V1 , V2 , , Vk )中每个中每个Vi都是非空的独立集。换言之，都是非空的独立集。换言之

5、，G 的的色数是色数是G中点不交的独立集的最小数目。中点不交的独立集的最小数目。v（2）易证：）易证：v (G) = 1 G = KC；v (G) = 2 G是非空二部图；是非空二部图； v (G) = (G) G K ；v（3）(C2n+1 ) = 3 。v（4） (G) 3 G含有奇圈。含有奇圈。v（5）四色定理：对任何平面图）四色定理：对任何平面图G， (G) 4。第1节 点染色6返回 结束v点染色理论的点染色理论的基本问题基本问题： 给定图给定图G，确定，确定 (G)的值。的值。v研究现状研究现状： 对一般情况，给出了对一般情况，给出了 (G)的范围（用的范围（用G的参数表示）；的参数

6、表示）； 对某些特殊图类，确定出了对某些特殊图类，确定出了 (G)的确切值。的确切值。第1节 点染色7返回 结束v定理定理 6.1.2 (Brooks，1941) 设设G 是连通的简单图，且是连通的简单图，且G 既不是奇圈又不是完全图，则既不是奇圈又不是完全图，则 (G) (G)。v例：例：求求Peterson 图的色数。图的色数。 解：因解：因 Peterson 图图G含有奇圈，故不是二部图，因而含有奇圈，故不是二部图，因而 (G) 3；另一方面，；另一方面， G既不是奇圈又不是完全图，且既不是奇圈又不是完全图，且(G) = 3, 故故 (G) (G) = 3。因此，。因此， (G) = 3

7、。第1节 点染色8返回 结束边的边的k染色染色 (edge k-coloring) 非空无环图非空无环图G 的边的边k 染色是指染色是指k 种颜色种颜色 1, 2, , k 对对E(G)中元中元素的一种分配，使得相邻两条边所染颜色不同。素的一种分配，使得相邻两条边所染颜色不同。换句话说，换句话说，G 中边的中边的k 染色是映射染色是映射 : E(G)1,2, k，使得对每个使得对每个 i ( i = 1,2, k ), 1 (i) 是匹配或者空集。是匹配或者空集。v注：注：若令若令 Ei =1 (i) = eE(G) |(e)= i , (i =1,2, k) , 则则G 的一个边的一个边k

8、染色可看成是染色可看成是边集边集E的一种划分的一种划分 = (E1 , E2 , , Ek )，其中每个，其中每个Ei 是匹配或空集。是匹配或空集。例：例：第2节 边染色9返回 结束边边k色可染的色可染的 (edge k-colorable) 若存在若存在 G 的一种边正常的一种边正常k 染色，则称染色，则称G 是边是边k色可染的。色可染的。v注：注：（1）每个无环非空图的边必）每个无环非空图的边必 色可染。色可染。（2）若）若G是边是边k 色可染的，则对任意色可染的，则对任意l k , G也是也是l 色可染的。色可染的。v边色数边色数 (edge chromatic number) 正整数正

9、整数 (G) = mink | G 是边是边k色可染的色可染的称为称为G 的边色数。的边色数。第2节 边染色10返回 结束v注：注：v（1）若）若 (G)k ，则，则G 中边的任何中边的任何k 染色染色= (E1 , E2 , , Ek ) 中每个中每个Ei 都是非空的匹配都是非空的匹配。v（2）G的边色数的边色数 (G)是是G中中边不交匹配的最小数目边不交匹配的最小数目。v（3） (K2n) = 2n 1= (K2n ) （因完全图（因完全图 K2n 有有2n-1 个边不交个边不交的匹配）的匹配）v（4） (G) (G)。（设。（设d(v) = (G)，则与，则与v关联的关联的(G)条边至条

10、边至少需少需(G)种色才能正常染色）。种色才能正常染色）。v（5）设）设 G是二部图，则是二部图，则 （G) = (G)。第2节 边染色11返回 结束v定理定理 6.2 (Vizing 定理，定理，1964) 设设G 是无环非空简单图，则是无环非空简单图，则 (G) (G) (G) +1。v注：注：v（1）对于有重边的图）对于有重边的图G，设，设 (G)表示表示G 中边的最大重数中边的最大重数，Vizing 实际上证明了一个更一般的结论：实际上证明了一个更一般的结论：(G)(G)(G)+(G)。v（2）Vizing 定理提出了一个分类问题：使定理提出了一个分类问题：使(G) = (G) 的简单图称的简单图称为为第一类图第一类图，使，使(G) = (G) +1的简单图的简单图G称为称为第二类图第二类图。v（3）二部图和）二部图和K2n 都是第一类图；而都是第一类图；而C2n+1 和和K2n+1 是第二类图。是第二类图。v（4）一般情况下，什么样的图属于第一类图，什么样的图属于第）一般情况下，什么样的图属于第一类图，什么样的图属于第二类图的问题尚未解决。二类图的问题尚未解决。v（5）第二类图较稀少：在）第二类图较稀少：在6 的的143个连通简单图中仅有