# グラフ彩色 ## 定義 グラフ `G` の**彩色(coloring)**とは、各頂点に色を割り当てて、隣接する頂点同士が必ず異なる色を持つようにすることをいう(この性質を満たす色割当を valid coloring と呼ぶ)。`k` 色以下で彩色できるグラフを **`k`-彩色可能(`k`-colorable)** といい、彩色に必要な色数の最小値を**彩色数(chromatic number)`χ(G)`** と呼ぶ。したがって `G` が `k`-彩色可能であることと `χ(G) ≤ k` は同値である。試験の時間割編成(同じ学生が受講する2科目間に辺を張ったグラフの彩色)、無線局への周波数割り当て、プログラムのレジスタ割り当て、地図の塗り分けなどが典型的な応用として挙げられる。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 11 Simple Graphs]] §11.7.1) いくつかの基本的な彩色数の値・上界が知られている。偶数長の閉路は2-彩色可能(`χ(C_even)=2`)、奇数長の閉路は3色を要する(`χ(C_odd)=3`)、完全グラフ `K_n` は `χ(K_n)=n`。空でないグラフが二部グラフであることと `χ(G)=2` であることは同値である。最大次数が `k` 以下のグラフは常に `(k+1)`-彩色可能である(頂点数に関する帰納法で証明される)が、この上界は達成される場合(`K_{k+1}` を部分グラフに含む場合)もあれば、星グラフのように大きく下回る場合もある。単純グラフに限ると、「奇閉路を持つ」「2-彩色不可能である」「奇閉歩道を持つ」の3命題は互いに同値であり、この事実により2-彩色可能性の判定は一般の `k`-彩色可能性判定より容易になる。一般の `k`(`k≥3`)に対する `k`-彩色可能性の判定は、多項式時間アルゴリズムが知られていない古典的な計算困難問題であり、3-彩色可能性判定は充足可能性問題(SAT)と同程度に困難であることが、色を強制する「色頂点(color-vertex)」と NOT/OR/XOR ゲートを模したガジェットグラフによる帰着で示される。平面グラフに限っても3-彩色可能性判定の困難さは変わらないことが、平面的な「交差ガジェット(cross-over gadget)」によって示される。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 11 Simple Graphs]] §11.7.2〜§11.7.3, 演習11.38〜11.42) 平面グラフ(第12章)に限ると、彩色数の上界は劇的に小さくなる。すべての平面グラフは5-彩色可能である(Theorem 12.6.4。4色定理そのものの完全証明は本書では扱わない)。証明は頂点数に関する強帰納法で、次数5以下の頂点が平面グラフに必ず存在すること(オイラーの公式の系である辺数上界 e≤3v−6 から従う)と、平面グラフの隣接2頂点の併合が平面性を保つこと(Lemma 12.6.2)を組み合わせる。次数5未満の頂点はその頂点を除いた帰納法の仮定でそのまま彩色でき、次数ちょうど5の頂点は、隣接する5頂点のうち非隣接な2頂点を併合して頂点数を1つ減らし、帰納法の仮定で彩色したうえで元のグラフに引き戻すことで、5色未満しか使わない隣接頂点の彩色として復元できる。任意の単純グラフに対する一般の`k`-彩色可能性判定困難性(§11.7.3)とは対照的に、平面グラフに限定した5-彩色可能性はこの構成的な強帰納法により多項式時間で実際に彩色を求められる。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 12 Planar Graphs]] §12.6) ## 横断的知見 - 第11章は一般の単純グラフに対する`k`-彩色可能性判定(`k≥3`)が計算困難(3-彩色可能性はSATと同程度に困難で、平面グラフに限っても交差ガジェットにより困難さが変わらない)であることを示す一方、第12章は平面グラフという同じ制約下でも「5色で足りるかどうか」という(`k`を固定した)問いに限れば強帰納法による構成的証明が存在し、計算困難性の議論とは別の扱いになることを示す。すなわち平面グラフの制約は「色数を固定すれば判定・構成が容易になる(5-彩色)」ことと「色数を最小化する判定は依然困難である(3-彩色可能性判定)」ことの両方を同時に成り立たせており、`k`-彩色可能性の計算困難性は色数`k`の選び方に強く依存する非単調な現象であることが2章を突き合わせて初めて分かる。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 11 Simple Graphs]], [[@2015__MIT__Mathematics for Computer Science - Chapter 12 Planar Graphs]] §12.6) - 第11章の「最大次数`k`のグラフは`(k+1)`-彩色可能」という一般的な上界を平面グラフに素朴に当てはめると、平面グラフの最大次数は無制限になりうるため有用な上界を与えない。第12章はこの限界を、最大次数ではなく「最小次数が5以下の頂点が必ず存在する」という平面グラフ固有の性質(オイラーの公式由来)に置き換えることで回避しており、平面性という追加の構造情報が、次数だけに基づく一般論の限界をどう補うかを示す好例になっている。(Source: [[@2015__MIT__Mathematics for Computer Science - Chapter 11 Simple Graphs]] §11.7.2, [[@2015__MIT__Mathematics for Computer Science - Chapter 12 Planar Graphs]] §12.6) ## 未解決の問い - 5-彩色定理から4色定理へ強化する証明技法(放電法など)は第12章でも触れられておらず、未解決のまま残る。 - 3-彩色可能性とSATの計算量的な同等性(NP完全性)は本章では「SATと同程度に困難」という形でのみ述べられ、NP完全性の正式な定義・証明枠組みは本書のどの章で扱われるか未確認。 - Akamai のサーバー更新事例(65,000ノードを8色で彩色)について、実際にどの彩色アルゴリズム(貪欲法か近似アルゴリズムか)が使われたかは本章からは分からない。 ## 関連 - 概念: [[単純グラフ]] / [[マッチング]] / [[平面グラフ]] / [[オイラーの公式]] - 実体: [[Akamai]] - source: [[@2015__MIT__Mathematics for Computer Science - Chapter 11 Simple Graphs]] / [[@2015__MIT__Mathematics for Computer Science - Chapter 12 Planar Graphs]] ## 出典 - Eric Lehman, F. Thomson Leighton, Albert R. Meyer, *Mathematics for Computer Science*, revised 2015-05-18, Chapter 11. - Eric Lehman, F. Thomson Leighton, Albert R. Meyer, *Mathematics for Computer Science*, revised 2015-05-18, Chapter 12.