图着色问题(英语:Graph Coloring Problem,简称GCP),又称着色问题,是最著名的NP-完全问题之一[1]

给定一个无向图,其中顶点集合,为边集合,图着色问题即为将分为个颜色组,每个组形成一个独立集,即其中没有相邻的顶点。其优化版本是希望获得最小的值。[2]

图色数 编辑

有两个相关的术语:

  1. 色数(英语:chromatic number),也被称为顶点色数vertex chromatic number),指将一张图上的每个顶点染色,使得相邻的两个点颜色不同,最小需要的颜色数。最小染色数用  表示。
  2. 边色数英语Edge chromatic numberedge chromatic number):指将一张图上的每条染色,使有公共顶点的边颜色不同,最少需要的颜色数叫边色数,用 表示。

和图中其他对象的关系 编辑

色数和团数(clique number)

(英语:clique)是一个图中两两相邻的顶点构成的集合。最大团是一个图中顶点最多的团,它的顶点数被称为 团数,记为   满足如下关系:

 

色数和独立数(independence number)

独立集(英语:independent set)是一个图中两两不相邻的顶点所构成的集合。最大独立集是一个图中顶点最多的独立集,它的定点数被称为 独立数,记为   满足如下关系:

 

色多项式 编辑

 
全部非同构三阶图和它们的色多项式。空图 E3(红)可以进行1-着色;其他图不可以。绿色的图用3种颜色有12种染色方法

色多项式用于计算给定数量的颜色下对某图进行涂色的可行方式数。例如,考虑有3个顶点的完全图  ,若只使用两种颜色, 根本无法被着色;若使用三种颜色,则有   种方式进行着色;若使用四种颜色,则有   个有效着色方案。因此,对于  ,有效着色数量的表格将从以下内容开始:

可使用之颜色数 1 2 3 4
有效着色方法数 0 0 6 24

色多项式是一个函数,记录将一个图 G 进行 t-着色的方法数,记作  。正如其名所述,  是一个关于 t 的多项式。回到上面   的例子,事实上, 

显而易见的,色多项式   比图色数蕴涵更多的资讯,更精确的说,  是色多项式最小的非零解正整数,即

 

下表给出了部分图的色多项式:

部分图的色多项式
三角形 K3  
完全图 Kn  
n个顶点的  
Cn  
佩特森图  

重要定理 编辑

参见 编辑


参考来源 编辑

  1. ^ Michael R. Garey; D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman. 1979-01-15: 125 [2015-09-21]. ISBN 978-0716710455. (原始内容存档于2016-05-29). 
  2. ^ Michael Molloy; Bruce Reed. Graph Colouring and the Probabilistic Method illustrated. Springer Science & Business Media. 2002: 3 [2015-09-22]. ISBN 9783540421399. (原始内容存档于2016-05-28).