グラフ彩色

グラフ彩色（英: Graph coloring）とは、グラフの何らかの要素に、ある制約条件を満たすように色を割り当てることである。最も単純なものは、隣接する頂点同士が同じ色にならないように全頂点に彩色する問題である。これを頂点彩色という。同様に辺彩色は、隣接する辺同士が同じ色にならないように全辺を彩色する問題、面彩色は、平面グラフの辺で囲まれた各領域（面）を隣接する面同士が同じ色にならないように彩色する問題である。

概要

頂点彩色が出発点であり、他の彩色問題は頂点彩色に変換可能である。例えば、辺彩色問題は、そのグラフをライングラフに変換したときの頂点彩色と同じであり、面彩色は平面グラフの双対グラフの頂点彩色と同じである。しかし、頂点彩色以外の問題もそのままの形で研究されている。これは、見通しの良さのためでもあり、頂点彩色以外の形式で研究が進んでいるためでもある。
彩色という表現を使うようになったのは、地図を国ごとに彩色する問題が起源である。地図の彩色問題は、平面グラフの面彩色問題に他ならない。また平面グラフの双対性により、頂点彩色問題とも等価であり、あらゆるグラフの問題として一般化できる。数学やコンピュータでは、非負または正の小さい整数を「色」を表現する値として使うことが多い。一般に、任意の有限集合を「色集合」として使うことができる。彩色問題の性質は色数には依存するが、個々の色をどう表すかは関係しない。
グラフ彩色はグラフのラベル付けとは異なる。ラベル付けは数で表される「ラベル」を頂点や辺に割り当てるものである。グラフ彩色問題では、色（を表す数）は任意のマーカーであり、隣接性や結合性に関わる状態を表す。グラフのラベル付け問題では、ラベル（を表す数）は計算可能な値であり、ラベル付けの際の定義で示される何らかの数値的条件を満たす必要がある。
グラフ彩色問題は理論的にも意味があるが、実用的な応用も多い。古典的問題以外にも、色の割り当て方や色自体に異なる制約を加えた問題もある。広く知られているパズルである数独もグラフ彩色問題の変形である。グラフ彩色は研究が盛んな分野のひとつである。

歴史

グラフ彩色は、地図の色分けの形で始まったものであり、当初はほとんど平面グラフだけを対象としていた。イングランドの地図をカウンティごとに色分けしようとしたフランシス・ガスリーは、4色あればどの境界線も両側が同じ色になることがないよう色分けできることに気づき、四色定理を主張した。ガスリーの兄弟がこの問題を数学の先生だったユニヴァーシティ・カレッジ・ロンドンのオーガスタス・ド・モルガンに提示してみたところ、彼は1852年にウィリアム・ローワン・ハミルトンへの手紙でこの問題に言及した。1879年、ロンドン数学会の会合でアーサー・ケイリーがこの問題を提示した。同年、アルフレッド・ケンプがその証明をしたとする論文を発表し、その後10年ほどはこの問題は証明済みとみなされていた。この業績によってケンプは王立協会フェローに選ばれ、後にロンドン数学会の会長に就任している。
1890年、パーシー・ヘイウッドはケンプの証明が間違っていることを指摘した。ケンプの証明は地図の塗りわけに「五色」あれば十分であることを示したに過ぎなかった。その後約1世紀に渡って四色定理を証明すべく様々な努力がなされ、とうとう1976年にケネス・アッペルとヴォルフガング・ハーケンが証明した。驚くべきことに、その証明の考え方はヘイウッドやケンプの考え方に沿ったもので、途中の数十年間の様々な努力は無視されている。四色定理の証明では初めて大規模にコンピュータを利用したことも注目に値する。
1912年、彩色問題を研究する過程でジョージ・デビット・バーコフが彩色多項式を導入。これをW・T・タットがタット多項式として一般化し、代数的グラフ理論の重要な構成要素となっている。ケンプは1879年の時点で既に平面グラフ以外のグラフ一般にも言及しており、グラフ彩色のより高次のグラフへの一般化は20世紀初頭から続々となされていった。
1960年、クロード・ベルジュはグラフ彩色についての新たな予想である「強パーフェクトグラフ予想」を定式化した。これは、クロード・シャノンの情報理論の概念であるグラフのゼロエラー容量が発想の元になっている。この予想は40年間証明されなかったが、2002年にChudnovsky、Robertson、Seymour、Thomasが証明し、「強パーフェクトグラフ定理」となった。
1970年ごろから、グラフ彩色についてのアルゴリズムの研究が盛んになってきた。彩色数問題は1972年にリチャード・カープが提案した21のNP完全問題の1つになっており、ほぼ同じころにバックトラッキングや Zykov (1949) の削除・縮約の繰り返し (deletion-contraction recurrence) などに基づいた指数関数時間の様々なアルゴリズムが開発された。グラフ彩色の応用の1つとしてコンパイラにおけるレジスタ割り付けがあり、1981年に登場した。

頂点彩色

単にグラフの彩色(coloring)と言った場合、「頂点彩色」を意味することが多い。また、隣接する頂点が同じ色にならないよう彩色すること、すなわち最適彩色を意味する。隣接する頂点とは、同じ辺と接している頂点である。ある頂点から同じ頂点へ戻る辺（ループ）が存在する場合、頂点彩色問題は決して最適解を持たないので、以下ではループがないグラフのみを扱う。
頂点のラベルを「色」で表すのは地図の塗りわけに起源がある。「赤」や「青」といったラベルは色数が小さい場合のみ使われ、一般にはラベルとして整数 {1,2,3,...} を使う。
最大 k 色を使った彩色を k-彩色と言う。グラフ G の彩色に必要な最小の色数を彩色数(chromatic number)と呼び χ(G) で表す。例えば、n 個の頂点からなる完全グラフ（あらゆる頂点間に辺があるグラフ） の彩色数は、 である。k-彩色できるグラフをk-彩色可能(k-colorable)といい、そのkがそのグラフの彩色数であるとき、k-彩色的(k-chromatic)という。同じ色が割り当てられた頂点の部分集合を「色クラス」と呼び、色クラス同士は独立集合となっている。したがって、k-彩色することは、頂点集合を k 個の独立部分集合に分割するのと等価であり、k-部 (k-partite) グラフや k-彩色可能といった用語も同じ意味を持つ。

辺彩色

グラフの辺彩色とは、グラフの辺を彩色するもので、1つの頂点に接合するそれぞれの辺が常に別々の色になるように最適彩色する。k色を使った辺彩色を「k-辺彩色」と呼び、辺集合をk個のマッチングに分割する問題と等価である。グラフ G の辺彩色に必要な最小の色数を彩色指数 (chromatic index) または辺彩色数 (edge chromatic number) と呼び、χ′(G) で表す。テイト彩色 (Tait coloring) とは、立方体グラフ（3-正則グラフ）の3-辺彩色を意味する。四色定理は、3-正則で辺が交差しない平面グラフをテイト彩色できることと等価である。

未解決の問題

単位距離だけ離れている任意の2つの点が同じ色にならないように平面を彩色する問題 (Hadwiger–Nelson problem) は未解決だが、その彩色数は5、6、7のいずれかだということまでは判明している。その他のグラフの彩色数に関する未解決問題としては、Hadwiger予想(en)がある。これは、彩色数 k のグラフはマイナーとして頂点 k 個の完全グラフを含む、という予想である。また、Erdős–Faber–Lovász予想(en)は、k-クリークが互いに高々1つの頂点を共有する形でk個連結されたグラフはk-彩色的だ、というものである。Albertson予想(en)は、k-彩色的グラフの中で完全グラフが最も交差数が小さい、というものである。
BirkhoffとLewisは四色問題を攻略する手段として彩色多項式を導入し、平面グラフ G の彩色多項式  は  の領域でゼロにならないという予想を立てた。そのような彩色多項式が  の領域でゼロにならないことと、 であることは判明しているが、彼らの予想自体は未解決である。任意の2つのグラフの彩色多項式が同一かどうかの判定や、ある多項式が彩色多項式かどうかの判定も未解決の問題である。

多項式時間

あるグラフが2色で彩色可能かどうかを決定する問題は、そのグラフが2部グラフかどうかの決定問題と等価であり、幅優先探索を使って多項式時間で解ける。より一般化すれば、パーフェクトグラフの彩色数と具体的な彩色は半正定値計画法を使って多項式時間で計算できる。森、弦グラフ、閉路グラフ、車輪グラフ、梯子グラフといった種類のグラフは彩色多項式がわかっているので、多項式時間での評価が可能である。

正確なアルゴリズム

k-彩色の判定を力まかせ探索で行う場合、n 個の頂点に k 色を割り当てる  の組み合わせを全て試し、制約をみたしているか調べる。彩色数や彩色多項式を計算する場合、力まかせ探索では  の全ての k について同じ作業をすることになり、小さいグラフ以外では現実的でない。
動的計画法と最大独立集合の数の制約を利用するとk-彩色可能性の判定は時間および空間計算量  で行える。包除原理と高速ゼータ変換のためのYatesのアルゴリズムを使えば、k-彩色可能性の判定は任意のkについて  の時間で行える。3-彩色可能性および4-彩色可能性の判定についてはさらに高速なアルゴリズムが知られており、それぞれ  および  の時間で判定できる。

貪欲彩色

貪欲法では、頂点に所定の順序 ,…, を設定し、 に対して ,…, までの隣接する頂点で使っていない色を設定し、それまでに使ったどの色の頂点とも隣接している場合は、新たな色を設定する。結果は頂点をどう順序付けするかに依存し、彩色数  による最適彩色を導き出す順序付けも存在することがある。しかし、順序付けによってはもっと悪い結果になる。例えば頂点が n 個の crown graph は2-彩色的だが、貪欲彩色では  色を必要とすることがある。
頂点を次数が小さくなる順序でソートすれば、貪欲彩色で使う最大色数は  となり、最悪でもそのグラフの最大次数より1つだけ大きい色数になる。このヒューリスティックを Welsh–Powell アルゴリズムとも呼ぶ。他にも、アルゴリズム実行中に動的に頂点の順序を決定していくヒューリスティックもあり、最も多くの異なる色と隣接している頂点を次の頂点として選ぶという方法もある。他にも様々なヒューリスティクスを採用したアルゴリズムがあり、これらを総称して逐次彩色 (sequential coloring) アルゴリズムと呼ぶこともある。

並列アルゴリズムと分散アルゴリズム

グラフ彩色の分散アルゴリズムは、グラフの「対称性の破れ」の問題と密接に関連する。対称グラフでは、決定的分散アルゴリズムでは最適彩色を見つけることができない。対称性の破れを見つけるには何らかの予備的情報を必要とする。一般的な前提条件として、n 個の各頂点に {1, 2, ..., n} の一意の識別子を付与した状態、つまりそれぞれが別々の色に彩色された状態を初期状態とする。したがって、なすべきことは n 色を例えば Δ + 1 色にまで減らしていくことである。
貪欲法を単純に分散アルゴリズム化して(Δ + 1)-彩色を求めるアルゴリズムは、最悪の場合 Θ(n) 回の通信を必要とし、情報をネットワークの一端から全体に伝播させる必要があることもある。ただし、最大次数 Δ が小さければ、もっと高速なアルゴリズムも存在する。
単純で興味深い例として n-閉路グラフがある。Richard Cole と Uzi Vishkinによれば、1回の同期通信ステップで色数を n から O(log n) に減らす分散アルゴリズムが存在する。これを繰り返すとn-閉路グラフの3-彩色を O(log* n) の通信ステップで得ることができる（各頂点には一意の識別子が付与されていることが前提）。
反復対数関数 log* は成長が非常にゆっくりとしていて、ほぼ定数とみなせる。そこで Cole と Vishkin の成果から、n-閉路の3-彩色を求める定数時間の分散アルゴリズムはあるのかという問題が提起される。Linial (1992) によれば、そのようなアルゴリズムは存在しない。決定的分散アルゴリズムはn-閉路をn-彩色から3-彩色に減らすのに Ω(log* n)の通信ステップを必要とする。
ColeとVishkinの技法は任意の次数の制限されたグラフに適用可能である。その場合の計算時間は poly(Δ) + O(log* n) となる。(Δ + 1)-彩色の既知の最高速アルゴリズムとしては、Leonid Barenboim と Michael Elkin のものがある。その計算時間は O(Δ) + log*(n)/2 であり、Linialの下限によれば 1/2 という係数はこれ以上改善できないので n に対して最適なアルゴリズムということになる。
辺彩色の分散アルゴリズムも研究されてきた。Panconesi & Rizzi (2001) では、(2Δ − 1)-辺彩色を O(Δ + log* n) の時間で可能なアルゴリズムが示されている。Linial (1992) による分散頂点彩色の下限は、辺彩色問題についても同様に成り立つ。

メッセージをやり取りしない分散アルゴリズム

メッセージのやり取りをしない分散アルゴリズム (decentralized algorithm) もある。最適彩色が存在するグラフについて、効率的にそれを求めるアルゴリズムが存在する。この場合、各頂点は隣接する頂点が自分と同じ色かどうかをメッセージをやり取りせずに確認できることを前提とする。例えば無線のチャンネル割り当てなどでは、他の通信機が同じチャンネルを使っているかどうかは容易に検出可能なので、この前提は穏当である。そのような情報があれば、学習するオートマトンが確実なグラフ彩色を見出すのに十分である。

計算量

グラフ彩色は困難である。k = 1 および k = 2 以外の k について「与えられたグラフがk-彩色可能か」という決定問題はNP完全問題である。彩色数を求める問題はNP困難である。彩色可能性を問う決定問題は次数が最大4の平面グラフであってもNP完全である。
既知の最良の近似アルゴリズムはオーダー O(n(log n)⁻³(log log n)²) の近似精度で彩色数を計算する。あらゆる ε > 0 について、n¹⁻ε 以内に彩色数を近似することはNP困難である。
3-彩色可能なグラフを4色で彩色する問題もNP困難であり、k-彩色可能なグラフを k 色で彩色する問題も k が十分大きければNP困難である。
彩色多項式の係数を求める問題は#P困難である。実際 k = 1 または k = 2 以外の任意の有理数 k について  を求める計算も#P困難である。NP = RP でない限り、k = 2 以外の k ≥ 1.5 の有理数 k について彩色多項式を評価する多項式時間の近似アルゴリズムは存在しない。
辺彩色については、Vizingの証明の結果から最大 Δ+1 色で彩色するアルゴリズムが得られている。しかし、2つの候補値から辺彩色数を決定する問題はNP完全である。近似アルゴリズムの場合、Vizingの辺彩色数を求めるアルゴリズムの近似度は4/3であり、任意の ε > 0 について(4/3 − ε )-近似アルゴリズムは存在しない（P=NPでない限り）。これらは近似アルゴリズムについての最も古い論文である（近似度という記法は明確には使っていない）。

スケジューリング

頂点彩色は各種スケジューリング問題のモデルとなる。最も単純化したスケジューリング問題は、一連の仕事を時間割にひとつずつ（ある時間には1つの仕事だけをするように）あてはめていくものである。個々の仕事にはリソースの競合など同時に実施できない制約条件がある。これをグラフで表すと、個々の仕事が頂点、競合する仕事を結ぶ線が辺となる。このグラフの彩色数を求める問題は、全部の仕事が終わるまでにかかる時間を最小にすることと等価である。
スケジューリング問題の詳細がそのグラフの構造を定義する。例えば航空機の運航スケジューリングの場合、インターバルグラフで表せば効率的に彩色問題として解ける。無線局の帯域幅割り当ての場合、単位円グラフで表せばよい。

レジスタ割り付け

コンピュータプログラムのコンパイラは、あるプログラミング言語から別の言語への翻訳を行う。その結果生成されるコードの実効効率を向上させるため、レジスタ割り付けというコンパイラ最適化技法が使われる。これは、プログラムで頻繁に使う値を高速なレジスタに保持し続けるようにするものである。理想的には演算に使用する値が常にレジスタに存在することが望ましい。
典型的な技法として、この問題をグラフ彩色問題にモデル化する。コンパイラは頂点をレジスタ（変数）とし、辺を同時に必要とされるレジスタ同士を結ぶように配した干渉グラフを構築する。このグラフがk色で彩色可能なら、k個のレジスタに割り付け可能である。

その他

グラフ彩色問題は、パターンマッチングなど様々な応用が見つかっている。
数独というパズルも、81個の頂点を持つグラフの9-彩色問題とみなすことができる。