图着色问题
(重定向自色数)
此條目可参照英語維基百科相應條目来扩充。 |
图着色问题(英語:Graph Coloring Problem,簡稱GCP),又称着色问题,是最著名的NP-完全问题之一[1]。
给定一个无向图,其中为顶点集合,为边集合,图着色问题即为将分为个颜色组,每个组形成一个独立集,即其中没有相邻的顶点。其优化版本是希望获得最小的值。[2]
图色数编辑
有两个相关的术语:
和图中其他对象的关系编辑
色数和团数(clique number)
团(英語:clique)是一个图中两两相邻的顶点构成的集合。最大团是一个图中顶点最多的团,它的定点数被称为 的团数,记为 。 和 满足如下关系:
色数和独立数(independence number)
独立集(英語:independent set)是一个图中两两不相邻的顶点所构成的集合。最大独立集是一个图中顶点最多的独立集,它的定点数被称为 的独立数,记为 。 和 满足如下关系:
色多项式编辑
色多项式(英語:chromatic polynomial)是将一个图G进行t-着色的方法数,记作P(G, t)。P(G, t)是关于t的多项式,假设G的阶数为n,则P(G, t)满足如下性质:
首项系数为1;
n-1次项系数等于-|E(G)|;
0次项系数等于0;
各项系数正负交替;
一次项系数不为零当且仅当G连通。
色多项式包含了G是否能进行t-着色的信息,即可以根据色多项式确定G的色数。二者具有如下关系:
下表给出了部分图的色多项式:
三角形 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).