グラフの彩色拡張アルゴリズム
間宮直子

1(指導教員：萩田真理子)

はじめにグラフの彩色アルゴリズム

3

グラフの彩色アルゴリズムは、仕事のスケジューリングやシミュレーション用擬似乱数の配置問題等様々な応用があり、注目されている研究分野である。
彩色は辺彩色、頂点彩色などが上げられるが、ここでは頂点彩色を扱う。グラフ G ＝ (V, E) の彩色数をχ(G) で表す。V の部分集合 P が彩色されているグラ
フを precolored graph といい、P の点の色を変えずに、G 全体を彩色することを彩色拡張という。P のどの 2
頂点も距離が 4 以上ならば χ(G) + １ 色で彩色拡張できることが知られている。

グラフの彩色アルゴリズムは、ウエルシュパウエルのアルゴリズムがよく使われている。これは次数の高い頂点から順に距離 1 の頂点に使われていない最小の色番号で彩色するものである。しかしこのアルゴリズ
ムは彩色する頂点の隣接点にのみに注視しているため、彩色数より多くの色数を使用して彩色されるケースが多い。
この改良アルゴリズムとして、ウエルシュパウエルのアルゴリズムより少ない色数でグラフが彩色されることの多い、色次数アルゴリズムが知られている。このアルゴリズムは、隣接点に使用された色の種類の総数を色次数（dc ）とし、色次数の高い頂点の中で次数が高い頂点から順に彩色するアルゴリズムである。

一般的な彩色アルゴリズムでは、どの頂点にも色がついていない状態のグラフを彩色するが、彩色拡張アルゴリズムではグラフの一部の頂点にすでに色が与えられた状態から、残りの色を決める。このためより応用しやすいものとなっている。例えばスケジューリングの例を挙げると、一般的な彩色アルゴリズムは誰の予定も全く無い状態から各人の予定を割り振る問題に対応しているが、『A さんが月曜の 14 時から 16 時に会議』『B さんは金曜午後から出張』という条件を満たすように予定を割り振る問題に対応している。

以下が色次数アルゴリズムの方がウエルシュパウエル
より少ない色数で彩色されるグラフの例である。(次数、色次数共に同じ値が複数あった場合頂点番号の小さいものから彩色する）

今回はウエルシュパウエルのアルゴリズムと色次数アルゴリズムを利用し、与えられた一般の precoloredgraph の彩色拡張を行い、使われる色数を比較した結果を紹介する。

2

グラフの彩色定義 1 頂点集合 V (G)、辺集合 E(G) のグラフ G について、グラフの各頂点に色番号を割り当てる関数
図 1: 左：ウエルシュパウエルのアルゴリズム。右：色c : V (G) → C = {1, 2, · · · , k}

次数アルゴリズムが、「xy ∈ E(G) ならば c(x) 6= c(y)」 をみたすとき、c を G の彩色または k-彩色という。グラフ G に k-彩色が存在し、(k − 1)-彩色が存在しない時、k を彩色数といい χ(G) = k と表す。

グラフの彩色拡張アルゴリズム

4

グラフ G = (V, E) は色次数アルゴリズムより r-彩色可能。ウエルシュパウエルのアルゴリズムより r0 彩色可能である。与えられたグラフ Gp を彩色拡張するアルゴリズムとして、以下のアルゴリズムを提案する。

定義 2 V (G) のある部分集合 P が彩色されたグラフ
G を precolored graph と呼び、Gp と表す。
定義 3 Gp がすでに彩色された P の色を変えないでr-彩色が存在する時、Gp は r-彩色拡張可能であるという。

4.1

アルゴリズム 1（ウエルシュパウエル方式）∗1

1. 彩色された頂点を除いた頂点集合を V 0 (Gp ) とする。

彩色拡張については以下の結果が知られている。(参考文献 1）

2. V 0 (Gp ) で最高次数の頂点 v を選ぶ。
（最高次数が複数有る場合、頂点番号のより小さいものを選ぶ）
頂点 v の隣接で使用されていない最小色番号を vに割り当てる。

定理 1 彩色数が χ(G) のグラフ G で、P (⊂ V (G))の任意の二頂点の距離が 4 以上の時、Gp は (χ(G)+1)彩色拡張可能である。

3. |V 0 (Gp )| = 0 になるまで 1.2.3 を繰り返す。

14.2

アルゴリズム 2（色次数方式）∗20

1. 彩色された頂点を除いた頂点集合を V (Gp ) とする。
02. V (Gp ) の各頂点の色次数 dc を更新する。
3. V 0 (Gp ) の中で最高の色次数の頂点集合を V ∗ (Gp )とする。
4. V ∗ (Gp ) の中で最高次数の頂点 v を選ぶ。
（最高次数が複数有る場合、頂点番号のより小さいものを選ぶ）

差:1差:2cd − r0

差:1

差:2|P | = 41762|P | = 4621|P | = 5|P | = 6|P | = 7196224224

91210|P | = 5|P | = 6|P | = 787110
140

133|P | = 8|P | = 9|P | = 10237245270181922|P | = 8|P | = 9|P | = 101751992276912

色数の差が 3 以上のグラフはこの比較では出なかった。また残りのグラフでは差は r0 = wel,r0 = cd だった。
（1）（2）共に頂点数を増やしていくと、その差も大きくなる。予想通りアルゴリズム 1 よりアルゴリズ
ム 2 の方が少ない色数で彩色拡張可能であると考えられる。

5. 頂点 v の隣接で使用されていない最小色番号を vに割り当てる。
6. |V 0 (Gp )| = 0 になるまで 1.2.3.4.5 を繰り返す。

5wel − r0

評価|V (G)|=20,|P | = 1, 2, · · · , |V (G)|/2、|P | = i のそ
れぞれについて、辺の発生確率 1/6 でのランダムグラフ G を生成し、P もランダムに選び、1, 2, · · · , r からランダムに色を割り当てたものを 500 個生成した。

6

まとめ

ウエルシュパウエルのアルゴリズムと色次数アルゴリズムを利用し、与えられた一般の precolored graphの彩色拡張を行い、使われる色数を比較した。今後の課題として、彩色数が χ(G) のグラフ G で、P (⊂ V (G))の任意の二頂点の距離が 4 以上の時、Gp を彩色拡張するアルゴリズム 3 の作成し、(χ(G) + 1) 色以下で彩色拡張できるかどうか検証したい。
具体的には以下の方針で彩色拡張を行うアルゴリズムを作成する。

（1）それぞれのグラフで ∗1 と ∗2 のアルゴリズムを使い彩色し、使用色数の差を比較する。なお、∗1 の彩色数を wel、∗2 の彩色数を cd とする。
（2）この wel − r0 , cd − r0 の差を比較する。（r > r0の場合、wel − r, cd − r の差で比較する）
予想はアルゴリズム ∗2 の方が ∗1 より色が得なために、（1）では cd の方が wel よりも値が低くなると考えられる。（2）では wel − r0 の方が増大していると考えられる。

グラフ G = (V, E) は色次数アルゴリズムより r-彩色可能。ウエルシュパウエルのアルゴリズムより r0 -彩色可能である。またウエルシュパウエルで彩色したグラフを Gw と呼ぶ事にする。
与えられたグラフ Gp で P（ ⊂ V (G)）の任意の二頂点は互いに距離 4 以上あり、色番号（1, 2, · · · , r）をランダムに与えられている。彩色拡張とは P の色を固定して彩色することだから、P で割り振られた色番号通りに Gw の色番号を変えれば、その Gw は Gp を彩色拡張したものである。P =｛x0 , x1 , · · · , xn ｝, i = 0 とする。

（1）
cd < wel

差:1差:2wel < cd

差:1差:2|P | = 1|P | = 2|P | = 3

158
175
196444|P | = 1|P | = 2|P | = 3

1178000|P | = 4|P | = 5|P | = 6184175172532|P | = 4|P | = 5|P | = 6651000|P | = 7|P | = 81179610|P | = 7|P | = 801002. c と cw が等しいならば、Gw の xi の色番号はそのまま。

|P | = 9830|P | = 900|P | = 10680|P | = 1010
色数の差が 3 以上のグラフはこの比較では出なかった。また残りのグラフでは ∗1 と ∗ 2 で使われる色数は等しかった。

3. c と cw が等しくないならば、Gw の頂点 xi の色番号を c とする。また Gw の頂点 xi の隣接で色番号 c を割り当てられている頂点がある時、その頂点に色番号 r + 1 を割り当てる。

1. P の頂点 xi の色番号を c,Gw での色番号を cw とする。

4. i++;
5. i = n になるまで 1.2.3.4 を繰り返す。
（2）
wel − r0

差:1

差:2

cd − r0

差:1差:2|P | = 1660|P | = 1120|P | = 2|P | = 3105146

34|P | = 2|P | = 3

202800

参考文献[1] Michael
O.Albertson,Emily
H.Moore,Extending
Graph
Coloring,
J.Combin.Theory Ser.B 77(1999)83-95.
2