图着色问题
外观
此条目可参照英语维基百科相应条目来扩充。 |
图着色问题(英语:Graph Coloring Problem,简称GCP),又称着色问题,是最著名的NP-完全问题之一[1]。
给定一个无向图,其中为顶点集合,为边集合,图着色问题即为将分为个颜色组,每个组形成一个独立集,即其中没有相邻的顶点。其优化版本是希望获得最小的值。[2]
图色数
[编辑]有两个相关的术语:
- 图色数(chromatic number),也被称为顶点色数(vertex chromatic number),指将一张图上的每个顶点染色,使得相邻的两个点颜色不同,最小需要的颜色数。最小染色数用或表示。
- 边色数(edge chromatic number):指将一张图上的每条边染色,使有公共顶点的边颜色不同,最少需要的颜色数叫边色数,用表示。
和图中其他对象的关系
[编辑]色数和团数(clique number)
团(clique)是一个图中两两相邻的顶点构成的集合。最大团是一个图中顶点最多的团,它的顶点数被称为的团数,记为。和满足如下关系:
色数和独立数(independence number)
独立集(independent set)是一个图中两两不相邻的顶点所构成的集合。最大独立集是一个图中顶点最多的独立集,它的定点数被称为的独立数,记为。和满足如下关系:
色多项式
[编辑]色多项式用于计算给定数量的颜色下对某图进行涂色的可行方式数。例如,考虑有3个顶点的完全图 ,若只使用两种颜色,根本无法被著色;若使用三种颜色,则有 种方式进行著色;若使用四种颜色,则有 个有效著色方案。因此,对于 ,有效著色数量的表格将从以下内容开始:
可使用之颜色数 | 1 | 2 | 3 | 4 | … |
---|---|---|---|---|---|
有效著色方法数 | 0 | 0 | 6 | 24 | … |
色多项式是一个函数,记录将一个图 G 进行 t-着色的方法数,记作 。正如其名所述, 是一个关于 t 的多项式。回到上面 的例子,事实上,。
显而易见的,色多项式 比图色数蕴涵更多的资讯,更精确的说, 是色多项式最小的非零解正整数,即
下表给出了部分图的色多项式:
三角形 K3 | |
完全图 Kn | |
n个顶点的树 | |
环 Cn | |
佩特森图 |
重要定理
[编辑]参见
[编辑]
参考来源
[编辑]- ^ 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).
- ^ 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).