图着色问题

图着色问题(英语: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种染色方法

色多项式(英语:chromatic polynomial)是将一个图G进行t-着色的方法数,记作P(Gt)。P(Gt)是关于t的多项式,假设G的阶数为n,则P(Gt)满足如下性质:

首项系数为1;

n-1次项系数等于-|E(G)|;

0次项系数等于0;

各项系数正负交替;

一次项系数不为零当且仅当G连通。

色多项式包含了G是否能进行t-着色的信息,即可以根据色多项式确定G的色数。二者具有如下关系:

 

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

部分图的色多项式
三角形 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).