グラフ彩色

出典: フリー百科事典『ウィキペディア（Wikipedia）』

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

目次 1 概要 2 頂点彩色 3 彩色数 4 アルゴリズム的観点 4.1 最適彩色 4.2 既存のアルゴリズム 4.2.1 Welsh-Powellアルゴリズム 5 彩色多項式 5.1 例 5.2 属性 5.3 彩色多項式の計算 6 脚注 7 関連項目 8 参考文献 9 外部リンク

[編集] 概要

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

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

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

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

[編集] 頂点彩色

単にグラフの彩色(coloring)と言った場合、「頂点彩色」を意味することが多い。また、隣接する頂点が同じ色にならないよう彩色することを意味する。隣接する頂点とは、同じ辺と接している頂点である。最大 k 色を使った彩色を k-彩色と言い、頂点集合を k 以下の独立部分集合に分割するのと等価である。

グラフ彩色の応用としては、時刻表のスケジューリング、コンパイラでのレジスタ割り付け、移動体通信への周波数割り当て、パターンマッチなどがある。

[編集] 彩色数

グラフ G の彩色に必要な最小の色数を彩色数(chromatic number)と呼び χ(G) で表す。例えば、n 個の頂点からなる完全グラフ（あらゆる頂点間に辺があるグラフ）K_n の彩色数は、χ(K_n) = n である。k-彩色できるグラフをk-彩色可能(k-colorable)といい、そのkが彩色数であるとき、k-chromatic という。

彩色数を求める問題はNP困難である。対応する決定問題（最大 k 色で彩色できるか?）はNP完全である。1974年に Garey と Johnson が示したとおり、次数が最大4の平面グラフであってもNP完全である^[1]。ただし、半正定値計画を利用した効率的な近似アルゴリズムが存在する。平面グラフについては四色定理がある。

χ(G) には次のような特性がある。

1. G が全く辺のないグラフであれば、χ(G) = 1 である。
2. G が奇数個の頂点からなる環状グラフであれば、χ(G) ≥ 3 である。
3. クリーク数（G の最大クリークの頂点数）を ω(G) としたとき、χ(G) ≥ ω(G) である。
4. 頂点の最大次数を Δ(G) としたとき、χ(G) ≤ Δ(G)+1 である。
5. G が完全グラフや奇数個の頂点からなる環状グラフでない単純グラフの場合、χ(G) ≤ Δ(G) である。
6. 平面グラフの場合、χ(G) ≤ 4 である。これを四色定理と呼び、1852年にオーガスタス・ド・モルガンが提示したが、証明されたのは1976年であった。

無限グラフについては、まだよく判っていない。無限グラフ G の全ての有限部分グラフが k-彩色可能であれば、G自体も同様である。(de Bruijn and Erdős 1951)

[編集] アルゴリズム的観点

[編集] 最適彩色

頂点彩色は一般にNP完全問題である。グラフの彩色数を問う代わりに、「このグラフは最大k色で彩色できるか?」という問いを考える方がやさしい。

k = 2 かどうかを問うことは、そのグラフが2部グラフかどうかを問うことと等価である。これは多項式時間で解くことができる。k >= 3 の場合はNP完全となる。

特筆すべき成果として、László Lovász は完全グラフの彩色数を多項式時間で求めることが可能であると示した。

[編集] 既存のアルゴリズム

彩色アルゴリズムは2つに分類される。

• 最適彩色アルゴリズム（Zykov のアルゴリズム、分枝限定法など）
• 最適彩色とは限らない（彩色数より多い可能性のある）彩色アルゴリズム。逐次的アルゴリズム、ヒューリスティクス、乱択アルゴリズム、メタヒューリスティクス（焼きなまし法、タブーサーチなど）、遺伝的アルゴリズムなどがある。

[編集] Welsh-Powellアルゴリズム

Welsh-Powellアルゴリズムは、貪欲法に単純なヒューリスティックを使ったグラフ彩色アルゴリズムである。Δ(G) をそのグラフの最大次数としたとき、このアルゴリズムで彩色したときの色数は最大 Δ(G) + 1 となる。アルゴリズムは次の通り。

1. 頂点を次数が小さくなる順序でソートする。この時点では頂点には色は付けていない。
2. その順序に従って、頂点を見ていく。ある頂点がまだ彩色されておらず、隣接する頂点に1番の色が付けられていない場合、その頂点に1番の色を付ける。
3. 同じことを頂点のリストの先頭から、2番の色、3番の色とやっていき、全頂点が彩色されるまで繰り返す。

このアルゴリズムは χ(G) の最適な彩色を発見するとは限らない。

[編集] 彩色多項式

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

色数	1	2	3	4	…
彩色数	0	0	12	72	…

彩色多項式は、P(G,t) で表され、グラフ G を t 色で彩色したときの色の組合せ数である。名前が示すとおり、ある G についての彩色多項式は、t に関する多項式となる。例に挙げたグラフでは、P(G,t) = t(t − 1)²(t − 2) となる。

彩色多項式は彩色数と共に、G の彩色可能性についての情報をもたらす。実際、彩色数 χ は彩色多項式の根ではない最小の正の整数である。

χ(G) = min{k:P(G,k) > 0}

この概念を最初に使ったのは George David Birkhoff と D. C. Lewis であり、四色定理の証明を試みる過程で用いた。任意の2つのグラフの彩色多項式が同一かどうかの判定や、ある多項式が彩色多項式かどうかの判定は未解決の問題である。

[編集] 例

特定のグラフに関する彩色多項式

三角形 K3	t(t − 1)(t − 2)
完全グラフ Kn	t(t − 1)(t − 2)...(t − (n − 1))
n 頂点の木	t(t − 1)n − 1
環状グラフ Cn	(t − 1)n + ( − 1)n(t − 1)
ピーターソングラフ	t(t − 1)(t − 2)(t7 − 12t6 + 67t5 − 230t4 + 529t3 − 814t2 + 775t − 352)

[編集] 属性

• P(G,0) = 0
• P(G,1) = 0 （G に辺がある場合）
• P(G,t) = 0（t < χ(G) の場合）
• G が n 個の頂点、m 個の辺、k 個の連結成分 G₁,G₂,…,G_k から成るとき、
  • P(G,t) の次数は n である。
  • P(G,t) における tⁿ の係数は 1 である。
  • P(G,t) における t^{n − 1} の係数は − m である。
  • t⁰,t¹, … t^{k − 1} の係数は全てゼロである。
  • t^k の係数はゼロではない。
  • P(G,t) = P(G₁,t)P(G₂,t)⋯P(G_k,t)
• 全ての彩色多項式の係数は符号が交互に変化する。
• P(G,t) = t(t − 1)^{n − 1} であるときのみ、n 頂点のグラフ G は木である。
• 単位元で評価された導関数 P'(G,1) は「彩色不変量(chromatic invariant)」θ(G) である。

[編集] 彩色多項式の計算

G に自己ループがある場合、厳密には正しい彩色は不可能であるから、次のようになる。

P(G,t) = 0

辺 e が自己ループでない場合、彩色多項式について次が成り立つ。

P(G,t) = P(G − e,t) − P(G / e,t)

ここで、G − e はその辺を除去したグラフ、G / e はその辺の両端の頂点を1つの頂点にしたグラフを意味する。

これらから、再帰的な手続きが考えられる。すなわち、与えられたグラフを辺が1つ少ない2つのグラフに変換し、それを再帰的に繰り返すのである。従って、辺が m 個あるとき、処理時間は 2^m の多項式で表される。これは 1.62^{n + m} まで改善できる。

他にもアルゴリズムは知られているが、いずれの場合もグラフの大きさに対して指数関数的に処理時間が増大する。一部のグラフ形式については、多項式時間のアルゴリズムも知られている。例えば、空のグラフ、完全グラフ、森、chordal graph、wheel、ladder などである。一般に、彩色多項式の計算問題は #P完全であり、あらゆるグラフについて多項式時間のアルゴリズムは発見できないと考えられている。

[編集] 脚注

[編集] 関連項目

• 四色定理
• 数独

[編集] 参考文献

• R. L. Brooks (1941年). “On colouring the nodes of a network”. Proc. Cambridge Phil. Soc. 37: 194–197.
• N. G. de Bruijn, P. Erdős (1951年). “A colour problem for infinite graphs and a problem in the theory of relations”. Nederl. Akad. Wetensch. Proc. Ser. A 54: 371–373. (= Indag. Math. 13)
• Tommy R. Jensen and Bjarne Toft (1995年). Graph Coloring Problems. Wiley-Interscience, New York. ISBN 0-471-02865-7. 
• Marek Kubale et al. (2004年). Graph Colorings. American Mathematical Society. ISBN 0-8218-3458-4. 
• Michael R. Garey, David S. Johnson, and L. Stockmeyer (1974年). “Some simplified NP-complete problems”. Proceedings of the sixth annual ACM symposium on Theory of computing, 47-63.
• Michael R. Garey and David S. Johnson (1979年). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5.  A1.1: GT4, pg.191.

[編集] 外部リンク

• Chromatic number of a space at PlanetMath.org
• Graph Coloring Page by Joseph Culberson （グラフ彩色プログラム）
• 各種グラフ彩色プログラムのソースへのリンク集