圖着色問題
維基百科,自由的 encyclopedia
圖着色問題(英語:Graph Coloring Problem,簡稱GCP),又稱着色問題,是最著名的NP-完全問題之一[1]。
![]() | 此條目可參照英語維基百科相應條目來擴充。 |
給定一個無向圖,其中
為頂點集合,
為邊集合,圖着色問題即為將
分為
個顏色組,每個組形成一個獨立集,即其中沒有相鄰的頂點。其優化版本是希望獲得最小的
值。[2]
圖色數
有兩個相關的術語:
- 圖色數(英語:chromatic number),也被稱為頂點色數(vertex chromatic number),指將一張圖上的每個頂點染色,使得相鄰的兩個點顏色不同,最小需要的顏色數。最小染色數用
或
表示。
- 邊色數(英語:Edge chromatic number)(edge chromatic number):指將一張圖上的每條邊染色,使有公共頂點的邊顏色不同,最少需要的顏色數叫邊色數,用
表示。
和圖中其他對象的關係
色數和團數(clique number)
團(英語:clique)是一個圖中兩兩相鄰的頂點構成的集合。最大團是一個圖中頂點最多的團,它的頂點數被稱為的團數,記為
。
和
滿足如下關係:
色數和獨立數(independence number)
獨立集(英語:independent set)是一個圖中兩兩不相鄰的頂點所構成的集合。最大獨立集是一個圖中頂點最多的獨立集,它的定點數被稱為的獨立數,記為
。
和
滿足如下關係:
色多項式
![](http://upload.wikimedia.org/wikipedia/commons/thumb/b/b6/Chromatic_polynomial_of_all_3-vertex_graphs.png/320px-Chromatic_polynomial_of_all_3-vertex_graphs.png)
主條目:色多項式
色多項式用於計算給定數量的顏色下對某圖進行塗色的可行方式數。例如,考慮有3個頂點的完全圖 ,若只使用兩種顏色,
根本無法被著色;若使用三種顏色,則有
種方式進行著色;若使用四種顏色,則有
個有效著色方案。因此,對於
,有效著色數量的表格將從以下內容開始:
More information 可使用之顏色數, 有效著色方法數 ...
可使用之顏色數 | 1 | 2 | 3 | 4 | … |
---|---|---|---|---|---|
有效著色方法數 | 0 | 0 | 6 | 24 | … |
Close
色多項式是一個函數,記錄將一個圖 G 進行 t-着色的方法數,記作 。正如其名所述,
是一個關於 t 的多項式。回到上面
的例子,事實上,
。
顯而易見的,色多項式 比圖色數蘊涵更多的資訊,更精確的說,
是色多項式最小的非零解正整數,即
下表給出了部分圖的色多項式:
三角形 K3 | |
完全圖 Kn | |
n個頂點的樹 | |
環 Cn | |
佩特森圖 |
重要定理
參見
- NP-complete問題列表
- 幾乎完備(Almost complete(英語:Almost complete))問題與弱完備(weakly complete(英語:weakly complete))問題
- ASR-complete
- Ladner理論
- NP困難
- P/NP問題
參考來源
- 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).