グラフ彩色とは？わかりやすく解説

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

概要

頂点彩色が出発点であり、他の彩色問題は頂点彩色に変換可能である。例えば、辺彩色問題は、そのグラフをライングラフに変換したときの頂点彩色と同じであり、面彩色は平面グラフの双対グラフの頂点彩色と同じである。しかし、頂点彩色以外の問題もそのままの形で研究されている。これは、見通しの良さのためでもあり、頂点彩色以外の形式で研究が進んでいるためでもある。

彩色という表現を使うようになったのは、地図を国ごとに彩色する問題が起源である。地図の彩色問題は、平面グラフの面彩色問題に他ならない。また平面グラフの双対性により、頂点彩色問題とも等価であり、あらゆるグラフの問題として一般化できる。数学やコンピュータでは、非負または正の小さい整数を「色」を表現する値として使うことが多い。一般に、任意の有限集合を「色集合」として使うことができる。彩色問題の性質は色数には依存するが、個々の色をどう表すかは関係しない。

グラフ彩色はグラフのラベル付けとは異なる。ラベル付けは数で表される「ラベル」を頂点や辺に割り当てるものである。グラフ彩色問題では、色（を表す数）は任意のマーカーであり、隣接性や結合性に関わる状態を表す。グラフのラベル付け問題では、ラベル（を表す数）は計算可能な値であり、ラベル付けの際の定義で示される何らかの数値的条件を満たす必要がある。

グラフ彩色問題は理論的にも意味があるが、実用的な応用も多い。古典的問題以外にも、色の割り当て方や色自体に異なる制約を加えた問題もある。広く知られているパズルである数独もグラフ彩色問題の変形である。グラフ彩色は研究が盛んな分野のひとつである。

歴史

→「四色定理 § 歴史」も参照

グラフ彩色は、地図の色分けの形で始まったものであり、当初はほとんど平面グラフだけを対象としていた。イングランドの地図をカウンティごとに色分けしようとしたフランシス・ガスリーは、4色あればどの境界線も両側が同じ色になることがないよう色分けできることに気づき、四色定理を主張した。ガスリーの兄弟がこの問題を数学の先生だったユニヴァーシティ・カレッジ・ロンドンのオーガスタス・ド・モルガンに提示してみたところ、彼は1852年にウィリアム・ローワン・ハミルトンへの手紙でこの問題に言及した。1879年、ロンドン数学会の会合でアーサー・ケイリーがこの問題を提示した。同年、アルフレッド・ケンプがその証明をしたとする論文を発表し、その後10年ほどはこの問題は証明済みとみなされていた。この業績によってケンプは王立協会フェローに選ばれ、後にロンドン数学会の会長に就任している^[1]。

1890年、パーシー・ヘイウッドはケンプの証明が間違っていることを指摘した。ケンプの証明は地図の塗りわけに「五色」あれば十分であることを示したに過ぎなかった。その後約1世紀に渡って四色定理を証明すべく様々な努力がなされ、とうとう1976年にケネス・アッペルとヴォルフガング・ハーケンが証明した。驚くべきことに、その証明の考え方はヘイウッドやケンプの考え方に沿ったもので、途中の数十年間の様々な努力は無視されている^[2]。四色定理の証明では初めて大規模にコンピュータを利用したことも注目に値する。

1912年、彩色問題を研究する過程でジョージ・デビット・バーコフが彩色多項式を導入。これをW・T・タットがタット多項式として一般化し、代数的グラフ理論の重要な構成要素となっている。ケンプは1879年の時点で既に平面グラフ以外のグラフ一般にも言及しており^[3]、グラフ彩色のより高次のグラフへの一般化は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_{n}$

このグラフは3色で12通りの彩色が可能。P(G,t)(t=3)= t(t-1)^2(t-2)=12。三角形グラフt(t-1)(t-2)と、そこに接続される1次の頂点(t-1)の積として求められる。

彩色多項式(chromatic polynomial)とは、与えられたグラフを与えられた色数内で彩色したときの彩色の組合せ数を求める式である。例えば、右図のグラフは3色で彩色すると12通りの彩色が可能である。2色では彩色できない。4色では 24 + 4×12 = 72 通りである。4色を使った彩色は24通りで、4色のうちの3色を使った彩色はそれぞれ12通りなので、このような計算になる（4色を4つの頂点に割り当てる場合は、任意の組み合わせが可能である）。従って、このグラフの彩色数を表にすると次のようになる。

色数	1	2	3	4	…
彩色の組み合わせ数	0	0	12	72	…

彩色多項式は、 $P(G,t)$ 決定問題名称グラフ彩色、頂点彩色、k-彩色入力 n 個の頂点を持つグラフ G。整数 k出力 G は k 個の色で最適彩色可能か?時間計算量 O(2ⁿn)^[7]複雑性クラス NP完全還元 3-SATGarey–Johnson GT4最適化問題名称彩色数入力 n 個の頂点を持つグラフ G出力 χ(G)複雑性クラス NP困難近似計算量 O(n (log n)⁻³ (log log n)²)非近似計算量 O(n^1−ε) - P=NPでない場合数え上げ問題名称彩色多項式入力 n 個の頂点を持つグラフ G。整数 k出力 G を k-彩色する場合の P (G,k) の値時間計算量 O(2ⁿn)複雑性クラス #P完全近似計算量多項式時間 - 一部のケースのみ非近似計算量 P=NPでない場合、多項式時間アルゴリズムは存在しない。

多項式時間

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

正確なアルゴリズム

k-彩色の判定を力まかせ探索で行う場合、n 個の頂点に k 色を割り当てる $k^{n}$

同じグラフにおいて2種類の頂点の順序付けをしたときの貪欲彩色。うまく順序付けすれば2-彩色可能だが、貪欲彩色では

n/2

ウィキメディア・コモンズには、グラフ彩色に関連するカテゴリがあります。

[1]

[2]

[3]

[7]

グラフ彩色とは？わかりやすく解説