查看“︁图着色问题”︁的源代码

{{expand english}}

'''图着色问题'''（{{lang-en|Graph Coloring Problem}}，簡稱{{lang|en|'''GCP'''}}），又称'''着色问题'''，是最著名的[[NP-完全]]问题之一<ref>{{lang|en|{{cite book|author1=Michael R. Garey|author2=D. S. Johnson|title=Computers and Intractability: A Guide to the Theory of NP-Completeness|date=1979-01-15|publisher=W. H. Freeman|isbn=978-0716710455|pages=125|url=https://books.google.com/books?id=fjxGAQAAIAAJ|accessdate=2015-09-21|archive-date=2016-05-29|archive-url=https://web.archive.org/web/20160529221524/https://books.google.com/books?id=fjxGAQAAIAAJ|dead-url=no}}}}</ref>。

给定一个无向图<math>G=(V, E)</math>，其中<math>V</math>为[[顶点 (图论)|顶点]]集合，<math>E</math>为边集合，图着色问题即为将<math>V</math>分为<math>K</math>个颜色组，每个组形成一个[[独立集]]，即其中没有相邻的[[顶点 (图论)|顶点]]。其优化版本是希望获得最小的<math>K</math>值。<ref>{{lang|en|{{cite book|author1=Michael Molloy|author2=Bruce Reed|title=Graph Colouring and the Probabilistic Method|publisher=Springer Science & Business Media|isbn=9783540421399|pages=3|edition=illustrated|year=2002|url=https://books.google.com/books?id=GH9udeCZ758C|accessdate=2015-09-22|archive-date=2016-05-28|archive-url=https://web.archive.org/web/20160528014341/https://books.google.com/books?id=GH9udeCZ758C|dead-url=no}}}}</ref>

== 图色数 ==
有两个相关的术语：

# 图'''色数'''（chromatic number），也被称为'''顶点色数'''（vertex chromatic number），指将一张图上的每个[[顶点 (图论)|顶点]]染色，使得相邻的两个点颜色不同，最小需要的颜色数。最小染色数用<math>\chi(G)</math>或<math>\gamma(G)</math>表示。
# {{le|边色数|Edge chromatic number}}（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>

==色多项式==
[[File:Chromatic polynomial of all 3-vertex graphs.png|thumb|200px|全部非同构三阶图和它们的色多项式。空图 ''E''<sub>3</sub>(红)可以进行1-着色；其他图不可以。绿色的图用3种颜色有12种染色方法 ]]{{Main|色多項式}}

'''色多項式'''用於計算給定數量的顏色下對某圖進行塗色的可行方式數。例如，考慮有3個頂點的完全圖 <math>K_3</math>，若只使用兩種顏色，<math>K_3</math>根本無法被著色；若使用三種顏色，則有 <math>3!=6</math> 種方式進行著色；若使用四種顏色，則有 <math>P^4_3=24</math> 個有效著色方案。因此，對於 <math>K_3</math>，有效著色數量的表格將從以下內容開始：
{| class="wikitable" style="background:white; text-align:right;"
!可使用之顏色數
|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>

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

{| class="wikitable" style="background:white;"
|+部分图的色多项式
|-
| 三角形 ''K''<sub>3</sub> || <math>t(t-1)(t-2)</math>
|-
| [[完全图]] ''K''<sub>''n''</sub> || <math>t(t-1)(t-2) \cdots (t-(n-1))</math>
|-
| ''n''个顶点的[[树 (图论)|树]] || <math>t(t-1)^{n-1}</math>
|-
| [[环 (图论)|环]] ''C''<sub>''n''</sub>|| <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>
|}

== 重要定理 ==

* [[五色定理]]
* [[四色定理]]
* [[Vizing定理]]
* [[布鲁克定理]]
* Konig定理（关于[[二分图]]）
* Hadwiger猜想
* [[拉姆齐定理]]
*[[色数]]

== 参见 ==
* [[NP-complete問題列表]]
* [[幾乎完備]]（{{tsl|en|Almost complete|Almost complete}}）問題與[[弱完備]]（{{tsl|en|weakly complete|weakly complete}}）問題
* [[ASR-complete]]
* [[Ladner理論]]
* [[NP困难]]
* [[P/NP问题]]


== 參考來源 ==
{{reflist}}

[[Category:图染色]]
[[Category:NP完全问题]]