グラフの分散彩色の評価
理学専攻・情報科学コース
菊池智子

1定義 4

はじめにw(c) :=並列計算機でシミュレーションをするときに、各計算機で擬似乱数を発生させて用いることがある。

c(x)=c(y)例：核分裂の様子を調べるとき、空間を小さな区域に分割して、それぞれの領域での確率現象を、各計算機で生成した擬似乱数を用いて計算させる。

z(c) :=∑
c(x)=c(y)しかし、近くの現象を扱う計算機が、全く同じ擬似乱数列を生成していたら、それによる偏りがおきてしまう。相関が大きい場所では、なるべく違う関数で生成された擬似乱数を用いたい。何種類かの関数しかないときに、どのように割り振れば良いだろうか？
このような問題を解決するために、グラフの分散彩色アルゴリズムが必要とされている。

2∑a(c) :=

1d(x, y)(1)1d(x, y)2(2)∑11c(x)=c(y)d(x, y) 2(3)w(c) は同色頂点間距離の逆数の和、z(c) は同色頂点間距離の逆数の 2 乗の和、a(c) は同色頂点間距離の逆数の 12
同色頂点間距離が大きくなるにつれ、式 1、3 の値は小さくなる。つまり、彩色結果を評価したときにこれらの値が十分に小さければ、同色頂点間距離が大きい、良い分散彩色を与えていることになる。

定義

本稿で扱う言葉の定義を以下のようにする。
定義 1 グラフとは、集合 V = V (G) と集合 E = E(G)のペアからなる G = (V, E) で、E ⊂ {(a, b)|a, b ∈ V }を満たすもののことである。そのグラフ G の有限単純無効グラフについて

4彩色アルゴリズム

アルゴリズム 1 （WelshPowell のアルゴリズム）
このアルゴリズムは、高速に χ(G) に近い値で彩色をするアルゴリズムである。
次数の高い頂点から順に、そこから距離 1 の頂点に使われていない最小の色番号で彩色する。
入力：グラフ Ｇ (|V (G)| = n),
彩色に用いる色の数 kc : V (G) → C = {1, 2, · · · , k}で、
「xy ∈ E(G) ならば c(x) 6= c(y) をみたす、c があるとき、G は k 彩色可能といい、この c を G の k-彩色という。
定義 2 グ ラ フ G の彩 色 c : V (G) → C ={1, 2, · · · , k} について、

1. V (G) = {v1 , v2 , ...vn } が、d(v1 ≥)d(v2 ≥ ... ≥d(vn )) を満たすように並べ替える。
2. i = 1 とする。

cd(c) := min{d(x, y) | c(x) = c(y), x 6= y}

3. c = 1 とする。
を彩色距離と呼ぶ。
定義 3 彩色距離が cd(c) > d をみたす彩色が存在するために必要な色数の最小値
χd (G) := min{k|G に cd(c) > d を満たす k-彩色 cが存在 }を G の d-分散彩色数とよび、χd であらわす。
命題 1 グラフ G の d-分散彩色数は、G の距離 d 以下の頂点間を辺で結んだグラフ Gd の彩色数と等しい。
つまり、グラフ Gd を4. vi の隣接点で色 c を持つものが存在しなければ、vi に色 c を与えて (6) へすすむ。
5. c = c + 1 として (4) に戻る。
6. i < P ならば、i = i + 1 として (2) に戻る。i = Pならば終了。
出力：グラフ G の点彩色結果
アルゴリズム 2 （同色頂点間距離が必ず d 以上になるアルゴリズム）
このアルゴリズムは彩色したグラフに対し、d− 分散彩色を与える。また、アルゴリズム中で WelshPowellのアルゴリズムをしており、χd (G) を求めることができる。
入力：グラフ Ｇ (|V (G)| = n),彩色に用いる色の数 k

V (Gd ) = V (G)E(Gd ) = {xy|x, y ∈ V (G), dG (x, y) ≤ d}で定義されるグラフとすると、

χd (G) = χ(Gd )をみたす。

3

1. 入力されたグラフに対し、各頂点間の距離を求め、参照しやすいように値を保存する。（以下、list1と呼ぶ。）

評価方法

分散彩色を評価する指標として、次のように定義される彩色の重みを提案する。

1

ては、n 回繰り返すので、この部分の計算量は O(n2 )となる。
アルゴリズム 5 の計算量
彩色の重みを w(c) から z(c) に変更しただけなので、アルゴリズム 3 と同様。

2. 頂点間距離が d(= 1) ならば、辺を追加し、このグラフを Gd とする。（辺の追加時には、list1 を参照する。）
3. WelshPowell のアルゴリズムでグラフ Gd を彩色する。

6

4. 彩色数が k より少ないならば、d の値を 1 増やし、2, 3 を繰り返す。

彩色数

アルゴリズム 2 は彩色距離を大きくすることができ、アルゴリズム 3 は同色頂点間距離を大きくできる利点がある。
今回、６点まですべてで作りうるグラフにおいて、アルゴリズム 2 を用いて彩色した。各点を固有のものとし、同型のグラフも異なる彩色をされるとする。たn(n−1)
通りある。
とえば n 点のグラフなら、グラフは2実行結果を表 1〜4 に示す。

5. 彩色数が k を超えたら、1 つ前の状態を返して終了。
出力：グラフ G の点彩色結果
アルゴリズム 3 （同色頂点間距離を大きくするアルゴリズム）
入力：グラフ Ｇ (|V (G)| = n),
彩色に用いる色の数 k

表 1：頂点数 3 にたいして全通りの彩色
K d=1 d=21. 各頂点間の距離を求め、参照しやすいように値を保存する。（以下、list1 と呼ぶ。）

111263

2. すべての頂点の色を c1 とする。

314

表 2：頂点数 4 にたいして全通りの彩色
K d=1 d=2 d=3

3. list1 を参照しながら、同色頂点間距離の逆数の和の list を作成する。（以下、list2 と呼ぶ。）
4. 頂点の色を変更することで、彩色の重み w(c) が小さくなるならば、色を変更する。
5. 色の変更にともない、list2 の更新を行う。
6. 4、5 を n 回繰り返したら終了。

111240993222816412638

表 3：頂点数 5 にたいして全通りの彩色
K d=1 d=2 d=3 d=4

出力：グラフ G の点彩色結果
アルゴリズム 4 （同色頂点間距離を大きくするアルゴリズム ）アルゴリズム 3 の彩色の重み w(c) を z(c) にしたものをアルゴリズム 5 とする。
アルゴリズム 5 （今回作成したアルゴリズム）
アルゴリズム 3 の彩色の重み w(c) を a(c) にしたものをアルゴリズム 5 とする。

51

K

計算量

各アルゴリズムの計算量について考える。
WelshPowell のアルゴリズムの計算量
次数が降順になるように点に番号を付ける：計算量
O(n)。周りに使われていない色で順に彩色する：計算量 O(n2 )。
同色頂点間距離が必ず d 以上になるアルゴリズム (アルゴリズム 2) の計算量
list1 の作成:O(n3 )。グラフ Gd の作成:O(n2 )。次の 2 つは WelshPowell のアルゴリズムと同じである。次数が降順になるように点に番号を付ける：計算量 O(n)。周りに使われていない色で順に彩色する：計算量 O(n2 )。
グラフ Gd と WelshPolwell のアルゴリズムを指定した
色数を超える手前まで Gd (d = 2, 3, · · · ) で繰り返す。

711111237525252535822008080465430250

19051368668728

表 4：頂点数 6 にたいして全通りの彩色
d=1d=2
d=3
d=4
d=5

1

1111125066

7575

7575

3323771620

480480

480

45152

6480

1860

1140

1140

5171

13668

6888

4728

4368

6110924

23464

26344

26704

比較

今回の彩色数の結果に対して、彩色の重みとしてw(c)、z(c)、a(c) の 3 つを提案している。どの評価方法がよりよいものなのだろうか？頂点数 6 までの全通りの場合と、頂点数が 100 で、辺の本数が最大 495 本のランダムな連結グラフを作成して本稿で比較する。

アルゴリズム 3 の計算量
list1 の作成:O(n3 )。頂点の色の初期化:O(n)。list2 の作成:O(n2 )。色の変更:O(n)。色の変更に伴う list2 の更新:O(n)。色の変更と、それに伴う list の更新につい参考文献[1] Martin Aigner : Discrete Mathematics

2