グラフの分散彩色アルゴリズム
理学専攻 情報科学コース
遠藤貴世美

1はじめにグラフの彩色アルゴリズムとして最も有名な Welsh・Powell のアルゴリズムは、与えられたグラフ G を、Gの最大次数 ∆(G) + 1 色以下で彩色する、高速かつ比較的少ない色数で彩色できるアルゴリズムである。これを改良し、G の部分グラフ H の最小次数 δ(H) の最大値 +1 色あれば必ず彩色でき、計算に必要な時間も計算空間にもそれほど差がない以下のアルゴリズムを提案する。
１．次数の小さい点から順に番号をつけ、H = G とする。２．H の中で次数が最小の点の内一番小さな番号の点 v を選び、H = H − {v} とする、この操作をグラフの点の数だけ繰り返す。３．２で順に選び出していった点と逆順に彩色を行う。ただし、使用する色番号はその点の周りに使われていない色番号の中で一番小さい色番号とする。
この二つのアルゴリズムを用いて実際にグラフを彩色した場合に色数にどのような違いが見られるか。また与えられたグラフが平面グラフに限った場合のアルゴリズムなども提案していく。

2アルゴリズム 1
入力：グラフ G ( |V (G)| = n )1. d(w1 ) ≥ d(w2 ) ≥ · · · ≥ d(wn ) となるように、次数が大きい順に点に番号を付け H = G とする。
2. i = 1, 2, · · · , n について、以下を繰り返す：(a) グラフ H の中で次数が最小の点の内、一番大きな番号の点 vi を選ぶ。
(b) H = H − {vi } とする。
3. i = n, n − 1, · · · , 1 について、以下を繰り返す：(a) vi を H で周りに使われていない最小の色番号でぬる。
(b) H に vi−1 と G での vi−1 の周りの辺を加えたグラフを新しく H とする。
出力：グラフ G の点彩色定理 1アルゴリズム１でグラフ G を彩色したときに使われる色数は、彩色の際に出てくる G の部分グラフ H における δ(H) の最大値 +1 以下となる。

彩色アルゴリズム

グラフの点彩色とは、隣り合う点が互いに異なる色となるようにグラフ全体を塗り分けるというものである。このようにグラフを彩色する方法としてよく知られている次のアルゴリズムを紹介する。

Welsh・Powell のアルゴリズム
入力：グラフ G ( |V (G)| = n )1. d(v1 ) ≥ d(v2 ) ≥ · · · ≥ d(vn ) となるように、次数が大きい順に点に番号を付ける。
2. i = 1, 2, · · · , n について、以下を繰り返す：(a) vi を G で周りに使われていない最小の色番号でぬる。

この定理は，よく知られている以下の定理を含む。
系1
H を G に含まれる全ての部分グラフとすると、χ(G) ≤max{δ(H)} + 1 となる。
証明
アルゴリズム１で彩色に使われた色数を n とする。n番目の色でぬられた点を v としてアルゴリズム１で vまで戻したグラフを H とする。v を彩色するには n番目の色を使用しなければならないので v は少なくとも次数 n − 1 のはずであり、v は H で次数が最小の点なので δ(H) ≥ n − 1 となる。
よって、χ(G) ≤ n ≤ δ(H) + 1 ≤ max{δ(H)} + 1 が示された。

出力：グラフ G の点彩色
これは「次数の大きい点から順にできるだけ小さな番号の色で彩色する」アルゴリズムで、この方法で彩色されたグラフの色数は ∆(G) + 1 以下となる。
今回はこのアルゴリズムを改良して得られたものでより少ない色数で彩色できることの多い次のアルゴリズムを提案する。

3

計算量計算に必要な時間や計算空間にはどの程度違いが見られるのかを検証していく。

Welsh・Powell のアルゴリズムの計算量次数が降順になるように点に番号を付ける：計算量O(n)、外部記憶 O(n)。周りに使われていない色で順に彩色する：計算量 O(n2 )、外部記憶 O(1)。
アルゴリズム１の計算量
次数が降順になるように点に番号を付ける：計算量O(n)、外部記憶 O(n)。最小次数を選び部分グラフを作成：計算量 O(n2 )、外部記憶 O(n2 )。周りに使われていない色で順に彩色する：計算量 O(n2 )、外部記憶O(1)。
アルゴリズム１では部分グラフを作成するため計算量・外部記憶共に増加する。しかし彩色の際の計算量がどちらも O(n2 ) であることと、もともとグラフ自体の辺情報が O(n2 ) であるため、計算量と計算空間はどちらも O(n2 ) となる。実際は Welsh・Powell のアルゴリズムと比べてアルゴリズム１の方が約 2 倍必要となる。

5

平面グラフの彩色

アルゴリズム１を使い平面グラフを彩色した場合を考える。全ての平面的グラフは次数 5 以下の点を持つことが知られているので、平面グラフ G の任意の部分グラフ H において max{δ(H)} + 1 ≤ 6 を満たし、定理１より次が成り立つ。
定理 2
平面的グラフをアルゴリズム１を用いて彩色すると、必ず６色以下で彩色される。
次に以下の補題より、平面的グラフを 5 色以下で彩色するアルゴリズムを考える。
補題 1
平面グラフには次数 5 の点 v の周りの点の中に互いに隣接していない 2 点が必ず存在する。
アルゴリズム 2
入力：グラフ G ( |V (G)| = n )1. H = G として点がなくなるまで以下を繰り返す：

4

彩色に用いられる色数の違い

実際に Welsh・Powell のアルゴリズムとアルゴリズ
ム１でグラフを彩色した場合に用いられる色数にどのくらい差があるのかを見ていく。
例えば下のように頂点番号が与えられていたグラフの場合の彩色は図のようになる。

(a) グラフ H の中で次数が最小の点 v を選び vの次数によって場合分けを行う。
i. d(v) ≤ 4 の場合v を取り除いたグラフを新しく H とする。
ii. d(v) = 5 の場合
v の周りの点のうち互いに隣接していな
い 2 点 a, b を選び、v, a, b を 1 点 x に縮約したグラフを新しく H とする。
iii. d(v) > 5 又は で a, b が見つからない
場合G は平面的でないとして終了。
2. グラフを戻しながら点 v を (a) (b) どちらかで彩色する。の場合は周りに使われていない最小の色番号でぬる。
(b) の場合は縮約された点を戻して x についていた色 C を a, b につけて v を周りにない最小の色番号でぬる。

(a)
アルゴリズム１は隣接している点を優先的に彩色できるので色数も得をする場合が多い。
ではグラフ全体ではどの程度の差が見られるのか。
同形なグラフであっても、上記のように点の番号の付け方で彩色の仕方に違いが出るため |V (G)| = n の場
n(n−1)
2通りのグラフを、それぞれのアルゴリズム合2を使って彩色した結果を以下に表す。

n総数

678

色数が少ないグラフの数

Welsh Powell

Algorithm 121522182891

20029337

2288668137213269

アルゴリズム１の方が少ない色数で彩色できることが多いとわかる。

出力：グラフ G の点彩色定理 3
平面的グラフをアルゴリズム２を用いて彩色すると、必ず５色以下で彩色される。
ただし、平面的グラフでなくても K3,3 のように 5 色以下で彩色できるものがあるので、アルゴリズム２で彩色できたからといって平面的グラフであるとは言えない。

参考文献[1] R.A.Wilson,
Graphs, Colourings and theFour-colour Theorem. Oxford University Press
Reprinted 2004.