Remove ads

圖着色問題(英語:Graph Coloring Problem,簡稱GCP),又稱着色問題,是最著名的NP-完全問題之一[1]

給定一個無向圖,其中頂點集合,為邊集合,圖着色問題即為將分為個顏色組,每個組形成一個獨立集,即其中沒有相鄰的頂點。其優化版本是希望獲得最小的值。[2]

Remove ads

圖色數

有兩個相關的術語:

  1. 色數(chromatic number),也被稱為頂點色數(vertex chromatic number),指將一張圖上的每個頂點染色,使得相鄰的兩個點顏色不同,最小需要的顏色數。最小染色數用表示。
  2. 邊色數英語Edge chromatic number(edge chromatic number):指將一張圖上的每條染色,使有公共頂點的邊顏色不同,最少需要的顏色數叫邊色數,用表示。
Remove ads

和圖中其他對象的關係

色數和團數(clique number)

(clique)是一個圖中兩兩相鄰的頂點構成的集合。最大團是一個圖中頂點最多的團,它的頂點數被稱為團數,記為滿足如下關係:

色數和獨立數(independence number)

獨立集(independent set)是一個圖中兩兩不相鄰的頂點所構成的集合。最大獨立集是一個圖中頂點最多的獨立集,它的定點數被稱為獨立數,記為滿足如下關係:

Remove ads

色多項式

Thumb
全部非同構三階圖和它們的色多項式。空圖 E3(紅)可以進行1-着色;其他圖不可以。綠色的圖用3種顏色有12種染色方法

色多項式用於計算給定數量的顏色下對某圖進行塗色的可行方式數。例如,考慮有3個頂點的完全圖 ,若只使用兩種顏色,根本無法被著色;若使用三種顏色,則有 種方式進行著色;若使用四種顏色,則有 個有效著色方案。因此,對於 ,有效著色數量的表格將從以下內容開始:

更多信息 可使用之顏色數, 有效著色方法數 ...
可使用之顏色數 1 2 3 4
有效著色方法數 0 0 6 24
关闭

色多項式是一個函數,記錄將一個圖 G 進行 t-着色的方法數,記作 。正如其名所述, 是一個關於 t 的多項式。回到上面 的例子,事實上,

顯而易見的,色多項式 比圖色數蘊涵更多的資訊,更精確的說, 是色多項式最小的非零解正整數,即

下表給出了部分圖的色多項式:

部分圖的色多項式
三角形 K3
完全圖 Kn
n個頂點的
Cn
佩特森圖
Remove ads

重要定理

參見


參考來源

Wikiwand in your browser!

Seamless Wikipedia browsing. On steroids.

Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.

Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.

Remove ads