グラフの彩色アルゴリズム
遠藤貴世美

1

(指導教員：萩田真理子)
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 とする。

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

出力：グラフ G の点彩色定理 1
アルゴリズム１でグラフ G を彩色したときに使われる色数は、彩色の際に出てくる G の部分グラフ H における δ(H) の最大値 +1 以下となる。

この二つのアルゴリズムを用いて実際にグラフを彩色した場合に色数にどのような違いが見られるか。また与えられたグラフが平面グラフに限った場合のアルゴリズムなども提案していく。

2

この定理は，よく知られている以下の定理を含む。
系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 の彩色を示す。

3計算量

このようにグラフを彩色する方法としてよく知られている次のアルゴリズムを紹介する。

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

Welsh・Powell のアルゴリズム
入力：グラフ G ( |V (G)| = n )Welsh・Powell のアルゴリズムの計算量
次数が降順になるように点に番号を付ける：計算量
O(n)、外部記憶 O(n)。周りに使われていない色で順に彩色する：計算量 O(n2 )、外部記憶 O(1)。

1. d(v1 ) ≥ d(v2 ) ≥ · · · ≥ d(vn ) となるように、次数が大きい順に点に番号を付ける。
2. i = 1, 2, · · · , n について、以下を繰り返す：(a) vi を G で周りに使われていない最小の色番号でぬる。

アルゴリズム１の計算量
次数が降順になるように点に番号を付ける：計算量O(n)、外部記憶 O(n)。最小次数を選び部分グラフを作成：計算量 O(n2 )、外部記憶 O(n2 )。周りに使われていない色で順に彩色する：計算量 O(n2 )、外部記憶O(1)。

出力：グラフ G の点彩色
これは「次数の大きい点から順にできるだけ小さな番号の色で彩色する」アルゴリズムで、この方法で彩色されたグラフの色数は ∆(G) + 1 以下となる。

アルゴリズム１では部分グラフを作成するため計算量・外部記憶共に増加する。しかし彩色の際の計算量がどちらも O(n2 ) であることと、もともとグラフ自体の辺情報が O(n2 ) であるため、計算量と計算空間はどちらも O(n2 ) となる。実際は Welsh・Powell のアルゴリズムと比べてアルゴリズム１の方が約 2 倍必要となる。

今回はこのアルゴリズムを改良して得られたものでより少ない色数で彩色できることの多い次のアルゴリズムを提案する。
アルゴリズム 1
入力：グラフ G ( |V (G)| = n )39

4

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

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) どちらかで彩色する。
(a) の場合は周りに使われていない最小の色番号でぬる。
(b) の場合は縮約された点を戻して x についていた色 C を a, b につけて v を周りにない最小の色番号でぬる。

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

出力：グラフ G の点彩色

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

合 2 2 通りのグラフを、それぞれのアルゴリズムを使って彩色した結果を以下に表す。
アルゴリズム２では次数 5 の点の周りには隣り合わない点が必ず存在するとしている。そのような点が存在しないで全ての点が隣り合っているということは、部分グラフ H が頂点数 5 の完全グラフ K5 ということになり、以下の Wagner の定理より平面的グラフではないことがわかる。

色数が少ないグラフの数|V (G)|総数

Welsh・Powellアルゴリズム１

6715222182891

20029337

8228866813

7213269

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

5Wagner の定理
G が平面的グラフであるための必要十分条件は、縮約して K5 又は K3,3 となる部分グラフを含まないことである。

平面グラフの彩色定理 3
平面的グラフをアルゴリズム２を用いて彩色すると、必ず５色以下で彩色される。

アルゴリズム１を使い平面グラフを彩色した場合を考える。全ての平面的グラフは次数 5 以下の点を持つことが知られているので、平面グラフ G の任意の部分グラフ H において max{δ(H)} + 1 ≤ 6 を満たし、定理１より次が成り立つ。

ただし、平面的グラフでなくても K3,3 のように 5 色以下で彩色できるものがあるので、アルゴリズム２で彩色できたからといって平面的グラフであるとは言えない。

定理 2
平面的グラフをアルゴリズム１を用いて彩色すると、必ず６色以下で彩色される。

66 色では彩色できることがわかったので、次に平面的グラフを 5 色以下で彩色するアルゴリズムを考える。

まとめと今後の課題

アルゴリズム１では、δ(H) の最大値 +1 色以下で彩色可能。平面的グラフは 6 色以下で彩色可能である。
アルゴリズム２では、平面的グラフは 5 色以下で彩色可能。アルゴリズム２で彩色できないグラフは平面的グラフではない。

補題 1
平面グラフには次数 5 の点 v の周りの点の中に互いに隣接していない 2 点が必ず存在する。
これにより、その互いに隣接していない 2 点を同じ色で彩色すればいいとわかる。

今後の課題としては、ただ隣り合う点を異なる色で彩色するだけでなくできるだけ色の偏りが少なくなるように彩色する分散彩色アルゴリズムを作りたい。

アルゴリズム 2
入力：グラフ G ( |V (G)| = n )参考文献

1. H = G として点がなくなるまで以下を繰り返す：(a) グラフ H の中で次数が最小の点 v を選び v の次数によって場合分けを行う。
i. d(v) ≤ 4 の場合v を取り除いたグラフを新しく H とする。

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

40