跳转到内容

图着色问题

维基百科,自由的百科全书

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

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

图色数

[编辑]

有两个相关的术语:

  1. 色数(chromatic number),也被称为顶点色数(vertex chromatic number),指将一张图上的每个顶点染色,使得相邻的两个点颜色不同,最小需要的颜色数。最小染色数用表示。
  2. 边色数英语Edge chromatic number(edge 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).