数理解析研究所講究録
第 1849 巻 2013 年 88-9088

分散システムでの剛性グラフに対する局所交換可能性

Transitivity of Laman Graphs in Distributed System
Taufiqurrachman
来嶋秀治

山内由紀子
Yukiko Yamauchi
山下雅史

Shuji Kijima

Masafumi Yamashita

タウフィックラチマン

九州大学
Kyushu University

12.2

はじめに

ペブルゲーム本研究では，グラフ $G=(V, E)$ 上のラーマングラ$O(|V||E|)$ でグラフのラーマン性を判定するためフ全体の集合上での局所遷移可能性について議論する．特に，あるラーマングラフから別のラーマング
ラフヘ，剛性を保ちながら変形する分散アルゴリズに，ペブルゲームというアルゴリズムが提案されている [1].
ペブルゲームの初期状態では，各頂点にそれぞれ2 個の石が与えられる．ペブルゲームは 2 つの操作にそれぞれ 2 個のからなる．1 つは，ある頂点対石があれば，から石を 1 個削り，から への辺を追加する．もう一つは，有向辺の終点に石があるな

ムを提案する．

$a,$

$b$

$b$

$b$

2

準備2.1

ラーマングラフと疎性マトロイド$E$ の各辺の長グラフ $G=(V, E)$ が剛であるとは，さを不変としたとき，頂点を任意に動かしてもグラフの形が変わらないことを言う．
2 次元の極小の剛なグラフは，次のラーマンの条件を満たすことと等価であることが知られている [2].
(1)$|E| = 2|V|-3$$|E[U]|$$\leq$$2|U|-3$$\forall U\subseteq V,$$|U|\geq 2$

(2)

$a$

らば，石を始点に移動し，辺の向きを逆にする．
以上の操作を繰り返し，グラフ全体に 3 個の石を残して全ての辺に向きが付いているならば，得られたグラフはラーマンである．

3提案アルゴリズム

3.1

アルゴリズムの概略

本研究では，同一の頂点集合$V$をもつラーマング

ラフ $L_{0}=(V, E_{0})$ と $L_{n}=(V, E_{n})$ が与えられたとラーマンの条件を満たすグラフをラーマングラフと$\square =$う．特に，(2) は疎条件と呼ばれ，疎条件を満たす辺集合は疎性マトロイドを構成することが知られている [2].

グラフがラーマンの条件を満たすかどうかを素朴に判定するには，すべての誘導部分グラフを確認す$O(2^{|V|})$ 時間かかる．
る必要があり，き，グラフの辺の交換により， から$L_{0}$

ラフの系列$L_{0},$ $L_{1},$$\cdots,$$L_{n}$$L_{n}$へ至るグを見つけるというものである．

辺の交換は，グラフの剛性を保持するために，$L_{i}$にある辺$e\in E_{n}\backslash E_{1}$を追加し，別の辺$e’\in E_{0}\cap E_{i}$を削除する操作と定義される．マトロイド基の同時交換可能性から，任意の辺$e\not\in E_{i}$$L+e-e’$に対し，がラーマングラフとなるような $e’\in E_{:}$ が存在する．

89
3.2

交換可能辺の探索$u$とにある 3 個の石を辺に変え，3 個の石の代わ$v$の間に 3 本の多重辺を追加する．

りに，$\{u, v\}$

本節では，ラーマングラフ $L=(V, E)$ とある辺$\{u, v\}$に 3 個の石を集めることで，ラーマンの条件を満たさなくなることにより，ある頂点部分集合 が存在が与えられるとき，ペブルゲームの向き付けを用いて，辺 と交換可能な辺 $e\in L$ を局所的に探$f\not\in L$$U$$f$して，索するアルゴリズムを与える．

が成り立ち，すなわち$u,$ $v$はそれぞれ 2 個，1 個の石をもつときの向き付けをとする．このとき， からの有向パスを持$U$ で誘導される部つ頂点の集合を $U\subset V$ とすると，$\hat{L}=(V,\hat{E})$$|E[U]|+3|\{uv\}|$$v$

作から $k(k\leq n)$ 個の頂点からできている誘導部分グ$u,$ $v$

ラフは高々 $2k$ 本の辺しか持つことができないため，矛盾である．

$=(V,\hat{E}_{i})$

$v$

$f$

に対し，以上の議論から，任意の頂点対計で 3 個の石を集めることができることが示され$\{u, v\}\subset V$$L_{n}\backslash$$f$$2|U|-3+3=2|U|$ (4)しかし，ペブルゲームの初期状態では，グラフの各頂点に 2 個の石が与えられる．ペブルゲームの操はラーマングラフである．
$e$$>$を得る．

分グラフ $G[U]$ の任意の辺 $e\in E$ に対し，$L+\{uv\}-e$に定理 1 に基づき，追加したい辺 の両端点それぞれ 2 個と 1 個の石を集め，ペブルゲームの向き付け均を得る．その向き付けを保持したまま，からの有向パスをもつ頂点を探索し， 現の無い辺 を見つけると，$L_{i}+e$はラーマング(3)$|E[U]| > 2|U|-3$

定理 1. ラーマングラフ $L=(V, E)$ と任意の頂点
対 $\{u, v\}\subset V$ に対し，ペブルゲームの操作で，ラフである．分散アルゴリズムにつ- いては 3.3 節で る．ペブルゲームの操作から，各頂点に最大で 2 個述べる．

$\hat{D}$の石しか持つことができないため，頂点対まった 3 個の石を 2 つの頂点に分ける．

$\{u, v\}$

以下，定理 1 の証明のアイデアについて述べる．準$\mathfrak{i}$$\ovalbox{\tt\small REJECT}$$u,$ $v$

備として，次の補題を用意する．ににそれぞれ 2 個，1 個の石もしくは 1 個，2 個の石を集め

補題 2. $\hat{L}=(V,\hat{E})$ はラーマングラフ $L=(V, E)$ことができる．

$\delta$にそれぞれ 2 個，1 個の石が集められる状態とる．にある石の数は 1 であるから，補題 2 より，点 $v\in V$ の持つ石の数が 個 (同様に 1 個) ならば，から1への有向パスが存在する．その有向パスを3 個 ( に無い 2 個) の石のうちの少なくとも 2 個 (1$u,$ $v$

上のペブルゲームの向き付けとする．このとき，頂$?^{-}$$v$$0$$u$$v$$v$$\overline{7}$$\ovalbox{\tt\small REJECT}|\rfloor$個$)$の石について，その石のある頂点から$u$$u$用すれば， から へ石を動かすことができる．
したがって，任意の頂点対に対して， に$u$に対して，$v$$v$$u,$への有向パスが存在する．

$v$

$u,$

補題 3. [1/ ペブルゲーム上で任意の頂点対に 3 個の補題 2,4 から次の補題が導かれる．

石を集めることができる．

1 題 5. ラーマングラフ $L=(V, E)$ と任意の頂点対補題 2,3 を用いて，次の補題が得られる．

に対し，ペブルゲームの操作で， にれぞれ 2 個，1 個の石を集めたときの向き付けを$\{u, v\}\subset V$$d\{$

補題 4. ラーマングラフ $L=(V, E)$ と任意の頂点対$\{u, v\}\subset V$に対し，ペブルゲームの操作で，$u,$ $v$に$*$$i$

それぞれ 2 個，1 個の石を集めることができる． から$\{u, v\}\subset V$に対し，合計で 3 個の石を集めることができないと仮定して，矛盾を導. 任意の頂点対に 3 個の石を集めることが$\langle$$\{u, v\}$できないとする．この条件は，$\{u, v\}$に 3 個の石を集めることで，ラーマンの条件を満たさなくなるこ$|E[U]|>2|U|-3,$とを意味する．つまり，$U\subseteq V,$$|U|\geq 2$在する．

を満たす$V$の頂点部分集合$u,$ $v\in$
$U$が存

$u$

$u,$ $v$とする．このとき，に対して，への 2 本の辺疎な有向パスが存在する．

$\hat{L}=(V,\hat{E})$

$v$
$w$

証明．任意の頂点対$v$:$f$ れぞれ 2 個，1 個の石を集めることができる．口

$(V, w)\in\hat{E}$明．補題 2 より， を除く任意の頂点は への有パスを少なくとも 1 本持つ．
グラフの頂点を， への 2 本以上の辺疎な有向パX を持つ頂点の集合巧と への有向パスが 1 つしかい頂点の集合巧に分ける．
このとき， の出次数は 1 であるから，巧に含ま$\overline{\frac{=}{-}}f$$\underline{\underline{\frac{-}{-}}}$

$u$

$u$

$\cap
D$$r|$

$u$

/

$u$

$f$
$f_{S}$$v$$\gamma_{1}$$\chi$ることに注意されたい．
$w$

が巧の要素であるならば，明らかである．

90は巧の要素とする．よって， に から 1 個 3.3 分散アルゴリズムの設計の石を移動することができ，巧に 2 個の石を集める
本節では，定理 1 を用いて，分散アルゴリズムを設ことができる．補題 4 より，任意の頂点対に 2 個，1計する．まず，ペブルゲームに関する新しい局所操作
$w$

$w$

$u$個の石を集めることができる．よって，少なくとも，頂点対巧に 3 個目の石を集めるために，巧$\{x, y\}\subset$から巧へのもう一つのパスが存在し，グラフが 2 つのカットを持っている．そのため， から$w$$u$への 2を定義する．

$\hat{L}_{i}=(V,\hat{E}_{i})$をペブルゲームで向き付けされたラーマングラフとし，ある頂点対$E_{n}\backslash$$u,$ $v;\{uv\}\in$

瓦に対して， に石が 2 個， に石が 1 個ある$v$$u$ものとする．補題 2 より，頂点 は出次数が 1 であることが言える．このとき， から出る辺の終点を$v$つの辺疎な有向パスが存在する

口$v$

補題 2,4,5 を用いて，定理 1 の証明を行う．
証明．帰納法で証明する．
仮定より， が 1 個の石しか持たないため，補題 2$v$

よりペブルゲームの向き付け $\hat{L}=(V,\hat{E})$ では， の$v$出次数が 1 である．まず， が始点となる辺 $(v, w)$ に$v$$(v, w)$ の終
対し，補題 5 より の石を動かさずに，$(v, w)$ の削除より，
点 に 2 個の石を集められる．
$v$に 1 個の石を与える． から$w$$u$に 2 個の石を戻し，$u$に2個，に 1 個のままであることに注意されたい．ペブルゲームの操作により，石を から に 1 個移動
$v$

$u$

し，$\hat{E}_{1}"=\hat{E}_{1}’$$v$$(v, u)+(u, v)$ もペブルゲームの正し

い向き付けにな- る．

補題 2 より， から$w$がわかる． の石を$u$$(u, v)$ の追加が可能になる．

$(v, w)+(v, u)$ と$\hat{E}_{i}’=\hat{E}_{i}$の正しい向き付けになっている．なお，石は$v$$w$とする．このとき？

したものは，ラーマングラフに対-するペブルゲーム

$w$

$w$

$u$

へ有向パスが存在すること$(u, v)$ を追に移動させると，加する前と同様な状態になる．従って，再帰的ににない辺が削除されるまで，上記の操作を繰り返す．
$L_{n}$

同様に ,$\grave{}$$v$

からの有向パスをもつ頂点をと再帰的に操作を行うことで題意を得る$w$とする口

なお，定理 1 と補題 2 から，次の系 6 が導かれる
ことを補足しておく．

4

おわりに-Circuit とは $2|V|-2$ 本の辺を持ち，(2) を満たラーマングラフの局所遷移可能性について，ペブすグラフと定義する．M-Circuit の各誘導部分グラルゲームを用いて，議論を行った．今後の課題とし$M$ -Circuit の任意の辺を削除
フが (2) を満たすため，ては，MCMC 法を用いたラーマングラフのランダムすると，ラーマングラフになる．すなわち $M$ -Circuit 生成法の設計が挙げられる．
$M$はサイズ $2|V|-2$ を持つ疎性マトロイドのサーキットである．

系 6. ラーマングラフ $L=(V, E)$ と追加したい辺$L=$$f=\{uv\},$ $\{u, v\}\subset V$ が与えられるとする．

参考文献とする．このとき，ペブルゲームで得ら[1] Jacobs, D., Hendrickson, B.: An algorithm fortwo dimensional rigidity percolation: the pebblegame, Joumal of Computational Physics, 137(1997), pp.346-365.

れた向き付けにおいて，$G+f$ 上で を含む強連結とすると， で誘導され成分を満たす部分グラフ$M$る部分グラフが $G+f$ の -Circuit である．

[2] 加藤直樹: 三角形分割とラーマングラフ: 建築への応用，RAMP シンポジウム 2006, pp. 135-152.

$(V, E)$$u,$と $f$ に対して，ペブルゲームを行った後，$v$

はそれぞれ 2 個，1 個の石をもつときの向き付けを$\hat{L}=(V,\hat{E})$

$u$

$U$

$U$

$f$の 1 個の石しか持たない頂点$v$から到達可能な全ての頂点を見つけるために，深さ優先探索を行う．
深さ優先探索で見つからない頂点に関しては，その頂点から出る辺が必ず と交換可能ではないため，$f$

M-Circuit の要素ではない．よって，ペブルゲームの向き付け上で動作する深さ優先探索は M-Circuit を見つけることができる．