グラフ彩色：概念と応用

グラフ彩色

グラフ彩色は、隣接する2つの頂点が同じ色を共有しないように頂点に色（またはラベル）を割り当てます。必要な最小色数が彩色数χ(G)です。

貪欲彩色アルゴリズム

1. 頂点を順序付ける
2. 各頂点に、既に色付けされた隣接ノードで使用されていない最小の色を割り当てる

彩色数

• 木: χ = 2（常に二部グラフ）
• サイクル: χ = 2（偶数長）または3（奇数長）
• 完全グラフK_n: χ = n
• 平面グラフ: χ ≤ 4（四色定理）

NP完全性

一般的なグラフの正確な彩色数の決定はNP困難です。貪欲アルゴリズムは上界を与えますが、常に最適な彩色とは限りません。

応用

1. 地図彩色 — 隣接する領域が異なる色になるように色を塗る
2. レジスタ割り当て — コンパイラが変数をCPUレジスタに割り当て
3. スケジューリング — 競合する試験や会議に異なる時間枠を割り当て
4. 周波数割り当て — 範囲が重複する無線タワーに異なる周波数を割り当て