图着色问题
此条目可参照[[:en:Module:Wikidata第969行Lua错误：attempt to index field 'wikibase' (a nil value) |英语维基百科]]相应条目来扩充。 |
图着色问题（英语：Graph Coloring Problem，简称GCP），又称着色问题，是最著名的NP-完全问题之一[1]。
给定一个无向图<math>G=(V, E)</math>，其中<math>V</math>为顶点集合，<math>E</math>为边集合，图着色问题即为将<math>V</math>分为<math>K</math>个颜色组，每个组形成一个独立集，即其中没有相邻的顶点。其优化版本是希望获得最小的<math>K</math>值。[2]
图色数[编辑]
有两个相关的术语：
- 图色数（chromatic number），也被称为顶点色数（vertex chromatic number），指将一张图上的每个顶点染色，使得相邻的两个点颜色不同，最小需要的颜色数。最小染色数用<math>\chi(G)</math>或<math>\gamma(G)</math>表示。
- 边色数（edge chromatic number）：指将一张图上的每条边染色，使有公共顶点的边颜色不同，最少需要的颜色数叫边色数，用<math>\chi'(G)</math>表示。
和图中其他对象的关系[编辑]
色数和团数（clique number）
团（clique）是一个图中两两相邻的顶点构成的集合。最大团是一个图中顶点最多的团，它的顶点数被称为<math>G</math>的团数，记为<math>\omega(G)</math>。<math>\omega(G)</math>和<math>\chi(G)</math>满足如下关系：
<math>\chi(G)\geq\omega(G)</math>
色数和独立数（independence number）
独立集（independent set）是一个图中两两不相邻的顶点所构成的集合。最大独立集是一个图中顶点最多的独立集，它的定点数被称为<math>G</math>的独立数，记为<math>\alpha(G)</math>。<math>\alpha(G)</math>和<math>\chi(G)</math>满足如下关系：
<math> \frac{n}{\alpha(G)} \leq \chi(G) \leq n - \alpha(G) + 1 </math>
色多项式[编辑]
色多项式用于计算给定数量的颜色下对某图进行涂色的可行方式数。例如，考虑有3个顶点的完全图 <math>K_3</math>，若只使用两种颜色，<math>K_3</math>根本无法被着色；若使用三种颜色，则有 <math>3!=6</math> 种方式进行着色；若使用四种颜色，则有 <math>P^4_3=24</math> 个有效着色方案。因此，对于 <math>K_3</math>，有效着色数量的表格将从以下内容开始：
| 可使用之颜色数 | 1 | 2 | 3 | 4 | ... |
|---|---|---|---|---|---|
| 有效着色方法数 | 0 | 0 | 6 | 24 | ... |
色多项式是一个函数，记录将一个图 G 进行 t-着色的方法数，记作 <math>P(G,t)</math>。正如其名所述，<math>P(G,t)</math> 是一个关于 t 的多项式。回到上面 <math>K_3</math> 的例子，事实上，<math>P(K_3,t)=t(t-1)(t-2)</math>。
显而易见的，色多项式 <math>P(G,t)</math> 比图色数蕴涵更多的资讯，更精确的说，<math>\chi(G)</math> 是色多项式最小的非零解正整数，即
<math>\chi (G)=\min\{ k\,\colon\,P(G,k) > 0 \}.</math>
下表给出了部分图的色多项式：
| 三角形 K3 | <math>t(t-1)(t-2)</math> |
| 完全图 Kn | <math>t(t-1)(t-2) \cdots (t-(n-1))</math> |
| n个顶点的树 | <math>t(t-1)^{n-1}</math> |
| 环 Cn | <math>(t-1)^n+(-1)^n(t-1)</math> |
| 佩特森图 | <math>t(t-1)(t-2)(t^7-12t^6+67t^5-230t^4+529t^3-814t^2+775t-352)</math> |
重要定理[编辑]
参见[编辑]
参考来源[编辑]
- ^ 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）.