並列計算機によるシミュレーション と地図の塗り分け問題
萩田真理子
お茶の水女子大学理学部
概 要
地図は何色で塗り分けることができるでしょうか？ 実は, 「4色あればどんな地図で も,隣り合う領域が異なる色となるように塗り分けることができる」と知られています. こ の問題はグラフの彩色問題として書き表すことができます. この講演では,地図の塗りわ けのためのグラフの彩色問題の解説と,実際に地図を少ない色数で塗り分けるためのアルゴ リズムを紹介します. このような地図の塗り分け問題は, たくさんの計算機でシミュレー ションをするときに必要になることがあります. 例えば, 核分裂の様子を調べるのに,空間 を小さな区域に分割して,それぞれの領域に一台の計算機を割り振ってシミュレーションを 行うとします. このとき,近くの空間を割り振られた計算機に対しては,できるだけ違うタ イプの乱数発生器を使いたいということが起きます. 乱数発生器のタイプが限られている ときに,近い空間ではできるだけ違うタイプの乱数発生器を使うにはどう割り振ればいいで しょうか？この問題はグラフの分散彩色問題として書き表すことができ,実は地図の塗りわ け問題と関係しています. このような配置を実現するためのアルゴリズムも紹介したいと思 います.
1 グラフの定義
グラフとは,集合V =V(G)と集合E =E(G)のペアからなるG= (V, E)で,E ⊂ {(a, b)|a, b∈ V}を満たすもののことです．
V(G)をグラフGの点集合, E(G)をグラフGの辺集合と呼び, それぞれの元を点, 辺と呼び ます.
グラフは右図のように，V の元を点で，
Eの元を点どうしを結ぶ曲線で表します．
グラフGの点u, v ∈V について,辺e= (u, v)が存在するとき,
・点u, vは隣接する
・u, vは辺eに接続する
・辺eは端点u, vを結ぶ といいます.
ある点から出る辺の本数をその点の次数と呼び, d(v)で点v ∈V(G)の次数を表します. x∈V(G)について, xに隣接する点の集合をxの近傍と呼び,
N(x) = {y∈V(G)|xy∈E(G)} で表します. |N(x)|=d(x)となります. グラフの次数は, 握手補題として知られている次の性質を満たします. 補題 1. 任意のグラフGについて, 次数が奇数の点の数は偶数個です.
Proof. グラフGの次数をすべて足すと, 各辺はその両端点で一回ずつ数えられるので,
v∈V(G)
d(v) = 2|E(G)|
となります. 右辺は偶数なので,左辺で足された奇数は偶数個とわかります.
以下, グラフ理論の基本的な用語です.
・HがGの部分グラフ⇔ Hが E(H)⊆E(G), V(H)⊆V(G) を満たすグラフ
・HがGの全域部分グラフ ⇔ Hが V(H) = V(G)を満たすGの部分グラフ
・S ⊂V(G) によって誘導されたGの誘導部分グラフ: Sを点集合, {(x, y)∈E(G)|x, y ∈S}
を辺集合とするGの部分グラフ. S ⊂V(G)によって誘導されたGの誘導部分グラフを ＜S＞ で表します.
・G\A : 点集合V(G)\A, 辺集合{(x, y)∈E(G)|x, y ∈V(G)\A} のグラフ.
・グラフGの道：Gの点の列(v1, v2, . . . , vk) で(vi, vi+1)∈E(G) (i= 1,2, . . . , k−1) を満た すもの. この道をv1からvkへの道とも呼びます.
・道P の長さ：道P に使われた辺の本数
・閉路C：v1 =vkの道(v1, v2, . . . , vk)
・u, v間の距離 d(u, v) : グラフGの点u, v ∈V について,uからvへの道の長さの最小値.
・グラフGが連結：Gのどの2点u, v間にも, uからvへの道がある.
・グラフGがk-連結：|V(G)|> kで, |X|< kなる∀X ⊂V(G)についてG\Xが連結.
・グラフの成分：グラフGの点x∈V について, xから有限の距離を持つ点全体で誘導され るグラフGの誘導部分グラフを, xを含むGの連結成分, または単にGの成分という. グラフ Gの異なる成分の個数をGの成分数といい,ω(G)で表す. ただし,P = (u)も長さ0の道とみな し, d(u, u) := 0,またuからvへの道が存在しないとき,d(u, v) := ∞.
・完全グラフKn：相異なる２点がすべて隣接している位数nのグラフ. |E(Kn)|=n(n−1)/2.
・完全2部グラフKm,n ：点集合が V(Km,n) =A∪B, |A|=m,|B|=n で 辺集合が E(Km,n) ={(x, y)|x∈A, y∈B} のグラフ.
・2部グラフ：完全2部グラフの部分グラフ. つまり, 点集合が V(G) =A∪Bで辺集合が E(G)⊂ {(x, y)|x∈A, y∈B} のグラフ.
・木：閉路を含まない連結なグラフ. n点上の連結なグラフが, 木 ⇔ n−1本の辺を持つ.
2 地図の塗り分け問題
与えられたすべての地図を隣り合う（線分を共有する）領域は違う色になるように塗り分け ることができるためには,何色の絵の具が必要でしょうか？
この問題は, 領域を点, 線分を共有する２領域間を辺で結んだグラフを考えると,地図を塗り 分ける問題は,地図から作られたグラフの点を, 辺で結ばれた2点が異なる色になるよう塗り分 けることと等しくなります.
2.1 グラフの点彩色
G= (V(G), E(G))：頂点集合V(G),辺集合E(G)の有限単純無向グラフについて, c:V(G)→ {1,2, . . . , k}
で xy ∈ E(G)ならば c(x) =c(y) をみたす c があるとき, Gはk-彩色可能といい, このcをG のk-彩色と呼びます.
χ(G) := min{k|G は k−彩色可能} をGの彩色数(chromatic number)と呼びます.
2.2 グラフ彩色の性質
基本的なグラフ彩色の性質として, 以下が成り立ちます.
（１）χ(G)≤ |V(G)|
（２）H :Gの部分グラフ ⇒χ(G)≥χ(H)
（３）χ(Kp) =p
（４）GがKnを部分グラフとして含む⇒χ(G)≥n
2.3 地図からグラフをつくる
地図上の領域・2領域間の隣接関係を，グラフの 点・辺として捉えると，地図の塗り分け問題をグ ラフの点彩色問題として考えることができます．
まず，地図をグラフに変換する方法を，右の地 図を使って見てみましょう．
1．各領域にひとつずつ点を描きます
2．地図上で隣り合っている2領域について，対応 する2点を結ぶ辺を描きます
3．完成
・このようにしてつくられたグラフに対して, 点彩色を行う ことと，
・もとの地図を，隣り合う領域が異なる色になるように塗り分ける ことは同じ意味をもちます．
つまり，ある地図M からつくられたグラフを5色で点彩色することができたなら，地図M も5色で塗り分けられることになります．
2.4 地図から作られたグラフの性質
地図からグラフを作るとき，各辺を自分の領域と相手の領域だけを通る曲線として上手に描 くとどの2辺も端点以外で交わらないように描くことができます．
・どの2辺も端点以外は交わらない曲線として平面上に描かれたグラフを平面グラフ,
・平面グラフとして描くことのできるグラフを平面的グラフ, と呼びます. 地図から作られたグラフは平面的グラフです.
平面グラフについて, 何本かの辺によって囲まれた部分とすべての辺の外側にある部分を領 域, または面と呼びます.
平面グラフ G について, その領域の集合をL(G)であらわすことにします. 平面的グラフの性質として, 以下が知られています.
定理 2 (オイラーの定理). 位数3以上の連結な平面グラフ G について,
|V(G)| − |E(G)|+|L(G)|= 2.
Proof. 点の数を固定して, 辺の本数についての帰納法で証明しましょう. |V(G)|=nとすると,
Gは連結なので|E(G)| ≥n−1ですが,|E(G)|=n−1のときGは木で閉路を含みませんので, 面は一つだけで,
|V(G)| − |E(G)|+|L(G)|=n−(n−1) + 1 = 2 を満たします.
|E(G)| ≥n とし, それより辺が少ないグラフでは定理が成り立つと仮定しましょう. このグ
ラフは木ではないので閉路を含みます. 閉路の中の一辺eを除いたグラフGは連結で辺の数が 減っていますから, 帰納法の仮定より,
|V(G)| − |E(G)|+|L(G)|= 2
を満たします. 今, eはGの閉路の一辺でしたので, Gではその両側にあった面が一つの面に なっていて, |L(G)|=|L(G)| −1です. |V(G)|=|V(G)|, |E(G)|=|E(G)| −1より,
|V(G)| − |E(G)|+|L(G)|= 2 で, Gでも条件を満たします.
系 3. 位数3以上の連結な平面的グラフ G について,
|E(G)| ≤3|V(G)| −6.
Proof. 面Lとその境界にある辺eとのペア(L, e)の数を数えてみましょう. 内部の面は3本以
上の辺で囲まれていて, 外部領域も3本以上の辺に接しているので,
#{(L, e)|eはLの境界} ≥3|L(G)|
を満たします. 一方, 1辺の周りにある面は高々2つなので,
#{(L, e)|eはLの境界} ≤2|E(G)|
とわかります. オイラーの定理から|L(G)|を消去すれば,
2|E(G)| ≥3|L(G)|= 6−3|V(G)|+ 3|E(G)|, |E(G)| ≤3|V(G)| −6 となります.
系 4. 平面的グラフには次数5以下の点が存在する.
Proof. すべての点の次数が6以上とすると,辺の本数は
|E(G)|= 1 2
v∈V(G)
d(G)≥3|V(G)|
となり, 上の系に矛盾します.
また, K5 と K3,3 は平面的グラフではありません.
これらの性質を使うと, すべての地図が6色で塗り分けられることを意味する次の定理が示 せます.
定理 5 (6色定理). G が平面的グラフならば, χ(G)≤6.
Proof. 点の数についての帰納法で示しましょう. 6点以下ならすべて違う色で塗れば塗り分け
られます. Gを|V(G)| = n ≥7 の平面的グラフとし, n−1点以下のグラフについては定理が 成り立っていると仮定しましょう. 系3より, Gには次数5以下の点vが存在します. G\ {v} は帰納法の仮定から6色で塗れるので塗ってみましょう. Gに戻るとvの次数は5以下なのでv の周りには高々5色しか使われていません. vに, まだ周りで使われていない色をつければGも 6色で塗れます.
すべての地図が5色で塗り分けられることを意味する次の定理も, 簡単に証明することがで きますので今回の講演でご紹介します.
定理 6 (5色定理). G が平面的グラフならば, χ(G)≤5.
実は, すべての地図は4色で塗り分けることができます. 定理 7 (4色定理). G が平面的グラフならば, χ(G)≤4.
4色定理には簡単な証明が知られていませんが, どのように考えられているか,方針だけ簡単 にご紹介する予定です.
2.5 グラフ彩色アルゴリズム
与えられたグラフを比較的少ない色数で彩色するアルゴリズムとして, 次数の大きな点から 順に,使える一番小さな番号で彩色していくウェルシュ・パウエルのアルゴリズムがよく使われ ています.
アルゴリズム 1 (ウェルシュ・パウエルのアルゴリズム).
入力：グラフ G.
(0) V(G) = {v1, v2, ..., vn} がd(v1)≥d(v2)≥...≥d(vn) を満たすように並べ替える．
(1) i= 1とする．
(2) c= 1とする．
(3) viの隣接点で色cを持つものが存在しなければ，viに色cを与えて(5)へ進む．
(4) c=c+ 1として(3)に戻る．
(5) i < P ならば，i=i+ 1として(2)に戻る．i=P ならば終了．
出力：Gの点彩色.
3 シミュレーションのためのグラフの分散彩色
並列計算機でシミュレーションをするときに, 各計算機で擬似乱数を発生させて用いること があります.
例： 核分裂の様子を調べるとき, 空間を小さな区域に分割して, それぞれの領 域での確率現象を,各計算機で生成した擬似乱数を用いて計算します.
しかし, 近くの現象を扱う計算機が,全く同じ擬似乱数列を生成していたら, それによる偏り がおきてしまいます. 相関が大きい場所では,なるべく違う関数で生成された擬似乱数を用いな くてはいけません. 何種類かの関数しかないときに, どのように割り振れば良いでしょうか？
この問題は,領域を点として面を共有して隣り合う領域を辺で結んだグラフについて,近くの 点がなるべく違う色になるように塗り分けるにはどうしたら良いか, という問題に言い換える ことができます.
3.1 グラフの分散彩色
グラフ Gの彩色 cについて,
cd(c) := min{d(x, y)|c(x) =c(y), x=y}
を彩色距離と呼ぶことにします.
また, グラフ G と与えられた色数r について,
cd(G, r) := max{cd(c)|c は G の r− 彩色} を G の色数r での 彩色距離 としましょう.
また, グラフ G の r 色での彩色が, 距離 d 以下のどの2点も異なる色となっているとき, こ の彩色を Gの 距離 d の(r-)分散彩色と呼びます.
問題 1. 与えられたグラフ G と色数 r についてcd(G, r) の大きな彩色を見つけるアルゴリズ ムが作りましょう.
ここで, グラフ彩色アルゴリズムとして最初に紹介したウェルシュ・パウエルのアルゴリズム について考えてみましょう.
このアルゴリズムでは, それぞれの点を着色するときに, まだ周りに使われていない一番番号 の小さな点で塗っています. 隣に1で塗られた点がなければ必ず1で塗りますので, たいてい色 1で塗られた距離3以下の2点が現れてしまいます. 比較的少ない色数で点彩色するアルゴリズ ムですが,バランスよく色を与えるアルゴリズムにはなっていないのです.
4 格子グラフの分散彩色
n次元空間の格子点, つまり座標がすべて整数の点 全体を点集合として,その空間内での距離が1の2 点間を辺で結んだグラフをn次元格子グラフとい います. 右は2次元格子グラフです.
最初の空間内の核分裂の様子を調べる問題は, 空間を小さな立方体に分割してそれぞれの領 域を点として, 面を共有して隣り合う領域を辺で結んだグラフ G について, cd(G, r) の大きな
r-彩色を見つけるという問題に言い換えることができますが, このグラフGは3次元の格子グ
ラフになっています.
問題 2. 格子グラフ G が cd(G, r)≥d となるためには何色必要でしょうか？
4.1 格子グラフの最適な分散彩色
まず2次元の格子グラフについて考えてみましょう.
たとえば d= 2m では,
D2m :=
(a, b)a, b∈Z,|a|+|b| ≤m を考えると, この中のどの2点も距離は 2m 以下で,
|D2m|= 2m+ 1 + 2((2m−1) + (2m−3) +· · ·+ 1) = 2m2+ 2m+ 1 なので, 少なくとも 2m2+ 2m+ 1 色は必要です.
このように各点から距離 d 以下の点を異なる色とするために必要な色数で, 実際にそのグラ フを塗り分けることができたとき,完全な分散彩色と呼ぶことにします.
定理 8. G : 2次元格子グラフのとき, 完全な分散彩色が存在します.
Proof. 上記より, d= 2m では少なくとも 2m2+ 2m+ 1 色は必要ですが, 格子点 (x, y) を, 色 (2m+ 1)x+y mod 2m2+ 2m+ 1 で塗れば分散彩色になってます.
d= 2m+ 1 でも, D2m+1 :=
(a, b)∈Z2 |b| ≤ |a| (0≤a≤m),|b| ≤2m+ 1− |a| (m+ 1≤a≤2m+ 1) を考えると, この中のどの2点も距離は 2m+ 1 以下で,
|D2m+1|= 2((2m+ 1) + (2m−1) + (2m−3) +· · ·+ 1) = 2m2+ 4m+ 2
なので, 少なくとも 2m2 + 4m+ 2 色は必要ですが, 格子点 (x, y) を, 色 (2m+ 1)x+y mod 2m2+ 4m+ 2 で塗れば分散彩色になっています. これらは完全な分散彩色です.
問題 3. n ≥ 3 についても, G : n 次元格子グラフのとき, 完全な分散彩色は存在するでしょ うか?
実は, 2次元のように無駄の全くない分散彩色は存在しないことがわかっています.
4.2 格子グラフの分散彩色アルゴリズム
まず2次元の格子グラフについて考えてみましょう. グラフ G を X×Y 個の点をもつ2次 元格子グラフ，すなわち平面R2 上の格子点
V(G) ={v(x,y)|1≤x≤X,1≤y≤Y}
を点集合とし，長さ1の2点を辺集合
E(G) ={v(x,y)v(x+1,y)|1≤x≤X−1,1≤y≤Y} ∪ {v(x,y)v(x,y+1)|1≤x≤X,1≤y≤Y −1}
としたグラフとします.
次のアルゴリズムは,お茶の水女子大学の研究生有間久美子さんによる与えられた色数で2次 元格子グラフを分散彩色するためのアルゴリズムです.
アルゴリズム 2.
入力：グラフG, 色数 K.
(0) 全ての点vに色K+ 1を与える．i= 0とする．
(1) 全ての点vに対し，vと同じ色を与えられている点までの最小距離d(v)を与える．
(2) x= 1, y = 1とおく．
(3) d(v(x,y))を最も大きくするような色k(1≤k ≤K)を，点vに与える．
(4) x < Xのとき，x=x+ 1とする．x=Xのとき，x= 1, y =y+ 1とする．
(5) x≤X, y ≤Y ならば，(3)に戻る．
(6) i=i+ 1とする．
出力：グラフのr-分散彩色.
前定理での塗り方は点(x, y, z)をax+by+cz modn で塗るという線形な塗り方では色数の 最高次係数がもっとも小さいものと証明できていますが, 3次元での同様のアルゴリズムで彩色 すると, より少ない色数での分散彩色が見つかることがあります.
今回の講演では,彩色アルゴリズムがどのように動くか, 実際に色が塗られていく様子を紹介 する予定です.
