組合せ剛性理論に基づく冗長性を有する剛堅な2次元フレームワークの生成手法

全文

(1)Vol.2012-AL-139 No.1 2012/3/14. 情報処理学会研究報告 IPSJ SIG Technical Report. 一般に 2 次元上における剛堅 (以下では rigid) なグラフとは, 2 次元空間内における連続的な変形が, 平行移動および回転のみに限られるような bar-and-joint framework に対応する. 組合せ剛性理論に基づく冗長性を有する剛堅な 2 次元フレームワークの生成手法吉仲祐史†1. 加. 藤. 直. 樹†1. 神. 山. 直. グラフを指す. 特に Laman は 2 次元上での極小な rigid グラフ (Laman グラフ)G = (V, E) が満たすべき必要十分条件が以下の条件であることを示した4) .. |E| = 2|V | − 3. 之†2. |E(X)| ≤ 2|X| − 3. (1) for every X ⊆ V with 2 ≤ |X| ≤ |V |. (2). 頂点数 2 の辺に対して図 1 のような Henneberg I, Henneberg II と呼ばれる 2 つの操作を. 組合せ剛性理論とは, 与えられたフレームワークをグラフとして扱うことで, そのフレームワークの剛性を組合せ的に特徴付けるものである. この組合せ剛性理論に基づいて, 本研究では極小な rigid グラフである Laman グラフを 2-edge-rigid グラフへと冗長化させる問題, および辺数最小の 3-edge-rigid グラフを効率的に生成する手法について述べる.. 繰り返し行うことで全ての Laman グラフが生成されることが知られている5) . 一般に rigid グラフは全頂点を使った Laman グラフを部分グラフとして持つグラフと言える. (a). (b). Constructing 2-dimensional redundantly rigid frameworks based on combinatorial rigidity theory Yuji Yoshinaka,†1 Naoki Katoh†1 and Naoyuki Kamiyama†2. 図1. (a)Henneberg I, (b)Henneberg II. 一方で k-edge-rigid グラフとは, rigid でなくならせるには少なくとも k 本以上の辺を削除する必要があるような, 冗長性を有する rigid グラフであると定義する. Laman グラフ. We consider the problem of generatig redundantly rigid bar-and-joint frameworks in 2D based on combinatrial rigidity theory. In particular, we deal with the ploblem of augmenting the rigidity of a Laman graph to construct a 2edge-rigid graph, and present construction method of 3-edge-rigid graphs with a minimum number of edges for any number of vertices which is at least 5.. は極小な rigid グラフであることから, 辺数最小の 1-edge-rigid グラフであると言える. 一方で辺数最小の 2-edge-rigid グラフは circuit グラフとして知られている2) が, k ≥ 3 に関してはその構造について知られていない. 本研究では Laman グラフを 2-edge-rigid グラフへと冗長化させる問題および辺数最小の. 1. はじめに. 3-edge-rigid グラフの生成手法について述べる.. 自由な回転を許す joint および伸び縮みのしない堅い bar で構成される bar and joint. framework は, joint を頂点集合 V , bar を辺集合 E とするグラフ G = (V, E) として扱う. 2. Laman グラフの冗長化. ことで, 組合せ剛性理論の分野ではその剛性について組合せ的特徴付けが為されてきた6) .. 2.1 Garcia らのアルゴリズム †1 京都大学院工学研究科 Graduate School of Engineering, Kyoto University †2 九州大学マス・フォア・インダストリ研究所 Institute of Mathematics for Industry, Kyushu University. Garcia らは Laman グラフ L = (V, E) に最小本数の辺 e1 , e2 , . . . , ek を加えて 2-edge-rigid にするアルゴリズムを提案している1) . これは, L(ei ) を辺 ei を加えることで 2-edge-rigid. 1. c 2012 Information Processing Society of Japan .

(2) Vol.2012-AL-139 No.1 2012/3/14. 情報処理学会研究報告 IPSJ SIG Technical Report. になる部分 Laman グラフとし, L = L(e1 ) ∪ L(e2 ) ∪ . . . ∪ L(ek ) となるように辺を加えて. ここで極小な tight vertex set は複数存在するはずで, それぞれを X1 , X2 , . . . とする. こ. いくアルゴリズムである. この際に各 L(ei ) の辺集合が極大であるように辺を選ぶことで加. こで以下の 2 つの補題が示される.. える辺数を最小に抑えられることができる. この極大な L(ei ) の辺集合を導く辺 ei の端点補題 2 X1 , X2 , . . . が全て disjoint のとき, (i, j) ∈ E であるように i ∈ Xk , j ∈ Xl を選ぶ. をそれぞれ extreme vertex と定義し, L(i, j) = L(i , j) = L(i”, j) = · · · かつ全てが極 . ことで, L(i, j) は極大となる.. 大となるような, いわば互いに等価な頂点集合 i, i , i”, . . . を extreme vertex set と呼ぶこととする.. 補題 3 互いに共有点を持つ極小な tight vertex set が存在するとき, L = L(i, j) であるよ. 以下ではこの extreme vertex set が成すグラフ構造を新しく tight vertex set という概念. うな i, j ∈ V が存在する.. を導入することで解明する.. この 2 つの補題から次の定理が導かれる.. 2.2 tight vertex set の導入 Laman グラフ L = (V, E) に対して, 頂点の部分集合 X ⊂ V が. 定理 1 互いに共有点を持たない極小な tight vertex set が 3 つ以上存在するとき, Garcia. |E(X)| + |δ(X)| − 2|X| = 0. らの定義する extreme vertex set は tight vertex set に一致する (図 3).. (3). 表している (図 2). ここでまず以下の補題が成り立つ.. k. X1 i. X2 j. w. (b) V-X. 図3. X δ(X) E(X). E(X). X2. X1. 補題 1 式 (1) を満たす tight vertex set X に対して |V − X| > 1 が成り立つ.. X. v. X3. E(X) は頂点集合 X によって誘導される辺集合で, δ(X) は X と V − X の間の辺の集合を. (a). X3. (b). (a). を満たしているとき, この X はグラフ L における tight vertex set と呼ぶこととする.. 極小な tight vertex set が 3 つ存在する場合. 3. 3-edge-rigid グラフの生成 V-X. 3.1 X-replacement G = (V, E) に対して以下の操作を考える.. δ(X) 図2. 1. 新しく頂点 v を加える.. (a)tight vertex set, (b)non tight vertex set. 2. (w, x), (y, z) ∈ E であるような 4 点 w, x, y, z ∈ V に対して v から辺を引く. . 3. 2 辺 (w, x), (y, z) ∈ E を取り除く.. . ここで, V − X = X とすると, X で誘導される部分グラフは Laman グラフである. つまりこの補題 1 から, 明らかに 4 点以上からなる任意の Laman グラフに対して, tight vertex. この操作は X-replacement と呼ばれ (図 4), Laman グラフに対してこの X-replacement を行うことで出来るグラフは再び Laman グラフとなることが知られている5) .. set は必ず存在し, すべての頂点はいずれかの tight vertex set に属する. さらに tight vertex set のうちで極小な頂点集合を考える.. 2. c 2012 Information Processing Society of Japan .

(3) Vol.2012-AL-139 No.1 2012/3/14. 情報処理学会研究報告 IPSJ SIG Technical Report v. v. z. w. w. z. y. x. w. a. z x. G. G - { (w,x), (a,b) }. G. G. y. x y. a. b. x y b. 図6 図4. z. w. 1 本ずつ除く場合. X-replacement. (iii) 元の E に含まれていた辺から 2 本を除く場合. ここで次の補題を示す. ここで除かれる辺を (a, b), (c, d) とする. G からこの 2 辺 (a, b), (c, d) を除いたグラフ補題 4 3-edge-rigid グラフ G = (V, E) に対して X-replacement を行うことで得られるグ. は rigid である. このグラフに対して X-replacement の操作を行って出来るグラフは, 再び. ラフ G = (V , E ) は再び 3-edge-rigid グラフである. 証明. rigid グラフであることがわかる (図 7). v. 生成された G から任意に 2 本の辺を除いても残されたグラフがまだ rigid であるこ. G. G - { (a,b), (c,d) }. とを示す. 除く 2 辺について以下のように場合分けをして考える. w a. (i) 新しく加えた辺から 2 本を除く場合. v. w x. y. z. 図7. w. w. d. a. z x y. d. b c. 元の辺から 2 本を除く場合. 以上より, グラフ G から任意に 2 辺を除いてもまだ rigid であることが示された.. z x. z. b c. G. G - { (w,x), (y,z) }. x y. 2. y. ここで, 3-edge-rigid グラフの各頂点の次数は 4 以上である. つまり, 4-regular かつ 3図5. 新しい 2 辺を除く場合. edge-rigid なグラフが存在すれば, これは辺数最小の 3-edge-rigid グラフであると言える. 一方で, 頂点数が 5 の完全グラフ K5 は 4-regular グラフであり, かつ 3-edge-rigid グラフ. 元のグラフ G は 3-edge-rigid グラフなので, ここから 2 辺 (w, x), (y, z) を除いてもまだ. であることが確認できる.. rigid である. Henneberg I に従ってこのグラフに, 頂点 v を加え, さらに w, x, y, z のうちの 2 点と v とを結ぶように辺を加えることでできるグラフは明らかに rigid である (図 5).. 4-regular グラフに対して X-replacement を行うことで得られるグラフは再び 4-regular グラフであることから, この K5 に対して X-replacement の操作を繰り返し適用することで. (ii) 新しく加えた辺から 1 本と元の E に含まれていた辺から 1 本を除く場合.. 生成されるグラフは 4-regular かつ 3-edge-rigid なグラフ, つまり辺数最小の 3-edge-rigid. ここで除かれる E 由来の辺を (a, b) とする. G は 3-edge-rigid であるので (w, x), (a, b). グラフであることがわかる. 次に以下の補題を示す.. の 2 本を除いてもまだ rigid である. Henneberg II に従ってこのグラフに, 頂点 v および 3 辺 (v, x), (v, y), (v, z) を加え, さらに辺 (y, z) を除いたグラフは rigid である (図 6).. 補題 5 4-regular かつ 3-edge-rigid なグラフ G = (V, E) において, ある 1 点 v ∈ V に隣接する頂点が {w, x, y, z} であるとする. ここで (w, x) および (y, z) に辺が存在しないとき,. 3. c 2012 Information Processing Society of Japan .

(4) Vol.2012-AL-139 No.1 2012/3/14. 情報処理学会研究報告 IPSJ SIG Technical Report. 以下の操作を行って出来るグラフ G = (V , E ) は再び 4-regular かつ 3-edge-rigid グラフ. る. つまり, a, b, c, d 間には Hamilton 閉路が存在するはずであり, 互いに disjoint な 2 辺を. である.. 追加することが可能である. よって補題 5 の操作を実行できる.. 1. 頂点 v および v に接続する 4 辺 (v, w), (v, x), (v, y), (v, z) を取り除く.. 次に頂点数が 7 以上の辺数最小な 3-edge-rigid グラフ G = (V, E) として図 9 のような. 2. 新しく (w, x), (y, z) に辺を加える.. グラフを考える. ここで v に接続する 4 点を a, b, c, d とする. X = V − {a, b, c, d, v} とおくと, |δ(X)| ≥ 5 であることがわかる. というのは, |δ(X)| < 5 であれば, この δ(X) から 2. この証明については, 各頂点の次数は 4 のまま保たれることは明らかなので, G = (V , E ). 辺を除くことで |δ(X)| < 3 となり, rigid グラフの必要条件に反するためである.. から任意の 2 辺を除いても残されたグラフがまだ rigid であることを示せばよく, 先の補題. e=1 a. 4 の証明と同様に示すことが出来る. また, この補題 5 の操作はまさに X-replacement の逆 v. 操作にあたることがわかる.. G. b. 定理 2 K5 に対して X-replacement の操作を繰り返し行うことで辺数最小の 3-edge-rigid グラフがすべて生成できる. 証明. a c. b. c. e=3 a b. フを考える (図 8).. 図9. a. v. G. いま a, b, c, d 間の辺数をいま e とすると, 各頂点の次数が 4 であることから. c. 2e + 4 + |δ(X)| = 16 a. c. c. 7 点以上の場合. d b. d. d. X. まず, ある頂点数が 6 の辺数最小な 3-edge-rigid グラフを G = (V, E) として以下のグラ. b. d. δ(X). 題 5 の操作が行えることを示す.. a. c. e=2 a. d b. はじめに, 頂点数が 6 以上である任意の辺数最小の 3-edge-rigid グラフに対して, 補. d. が成り立ち, e ≤ 3 が言える.. d b. (4). e ≤ 2 の場合は明らかに, 互いに disjoint な 2 辺を追加することが可能であるため, 補題. c. 5 の操作は実行可能である. a. d. x b. 図8. e = 3 の場合, 例えば次ページの図 10 のような場合は a, b, c, d 間に互いに disjoint な 2 辺を追加することは不可能である.. c. 6 点の場合. (i) の場合は a および a に接続する 4 点 {a , a , b, v} に注目すると, (a , v) および (a , b) 間に辺は存在することはなく, 補題 5 の操作が実行できることがわかる. また (ii) の場合は. V = {a, b, c, d, v, x} とすると, G が 4-regular グラフであることから v に接続する 4 点. 点線が示している通り 4-edge-connected であり, そもそも 3-edge-rigid グラフではない.. が a, b, c, d であれば x に接続する 4 点も a, b, c, d であり, a, b, c, d 間に辺は 4 本存在するはずである. 各頂点は x, y にそれぞれ隣接しているので, 残される次数はそれぞれ 2 ずつであ. 4. c 2012 Information Processing Society of Japan .

(5) Vol.2012-AL-139 No.1 2012/3/14. 情報処理学会研究報告 IPSJ SIG Technical Report v. v. (i). 得られることである (図 11).. (ii) v. (a) a. a. d b. c. x. c. w. z x. X. w. d b. a. v. (b). X. y. y. z. 図 11 4-regular かつ essentially 6-edge-connected. a. 図 10 e = 3 場合. この (a) の操作は明らかに X-replacement の操作である. また, (b) の操作は元のグラフに対して X-replacement を 2 回実行したことと同義であることが, 先の定理 2 の証明から. よって以上から頂点数が 6 以上である任意の辺数最小な 3-edge-rigid グラフに対して, 補. わかる. つまり以下の補題が導かれる.. 題 5 の操作が行えることが示された.. 補題 6 グラフ G = (V, E) が 4-regular かつ essentially 6-edge-connected であることの必. このことから, 頂点数が 6 以上である任意の辺数最小な 3-edge-rigid グラフは, 補題 5 の. 要十分条件は, K5 に X-replacement の操作を繰り返すことで G が得られることである.. 操作を繰り返すことによってやがて K5 が生成されるはずである. つまり補題 5 の逆操作である X-replacement を K5 に対して繰り返し行うことで元のグラフが得られるはずである.. ここで定理 2 および補題 6 から, 辺数最小の 3-edge-rigid グラフと 4-regular かつ essen-. つまり, K5 に対して X-replacement の 1 種類だけの操作を繰り返すことによってすべての. tially 6-edge-connected なグラフは, 全く同じ操作によって生成されることが分かる. つま. 辺数最小な 3-edge-rigid グラフを生成することが可能であることが示された.. 2. り以下の定理が導かれる.. X-replacement は, Laman グラフから Laman グラフを生成する操作として知られてい. 定理 4 G = (V, E) が辺数最小な 3-edge-rigid グラフであることの必要十分条件は, G が. ることは先にも述べたが, 一般に X-replacement の逆操作では Laman グラフは維持されな. 4-regular かつ essentially 6-edge-connected であることである.. い場合がある5) .. 以上より, 間接的ではあるがグラフの連結性と剛性には密接な関係が存在することがわ. その一方で, このような X-replacement という操作も, 3-edge-rigid グラフに対してはそ. かった.. のいずれの向きにも剛性および冗長性が常に保たれる, という非常に興味深い結果が本節では得られたと言える.. 4. 5-edge-rigid グラフ. 3.2 グラフの連結性と剛性. 6 点以上からなるグラフ G = (V, E) に対して, 以下の操作以下の操作を考える.. グラフ G = (V, E) において, 2 ≤ |X| ≤ |V | − 2 であるような任意の edge cut δ(X)(X と. 1. 新しく頂点 v0 を加える.. V − X を結ぶ辺集合) のサイズが常に k 以上であることを essentially k-edge-connected. 2. (v1 , v2 ), (v3 , v4 ), (v5 , v6 ) ∈ E であるような 6 点 v0 , . . . , v6 ∈ V に対して v0 から辺を. と定義する. ここで以下のことが C.Kiraly らによって示されている3) .. 引く.. 3. 3 辺 (v1 , v2 ), (v3 , v4 ), (v5 , v6 ) ∈ E を取り除く.. 定理 3 (C.Kiraly et al.) グラフ G = (V, E) が 4-regular かつ essentially 6-edge-. connected であることの必要十分条件は, K5 に以下の 2 種類の操作を繰り返すことで G が. 5. c 2012 Information Processing Society of Japan .

(6) Vol.2012-AL-139 No.1 2012/3/14. 情報処理学会研究報告 IPSJ SIG Technical Report. LX (v0 , v2 ) が複数の頂点を共有するのであれば LX (v0 , v1 ) ∪ LX (v0 , v2 ) は Laman 部分グ. v0. G. G. v2. v3. v4. v6. v1. v6. v1. ラフとなり, 辺 (v1 , v2 ) が redundant な辺となってしまう (図 14).. v2. v5. 図 12. v3. v4. v0. ∗-replacement. v1. この操作は X-replacement の拡張として ∗-replacement と呼ぶこととする (図 12). この. ∗-replacement の操作について以下の補題を示す.. 図 14. 補題 7 6 点以上からなる Laman グラフ G = (V, E) に対して, ∗-replacement の操作を行. 本以外には存在しない. もしも (v1 , v2 ) 以外の辺が存在するならば, これらの辺は redundant になり, 再び GX が Laman グラフであることに矛盾するためである.. 3 辺 (v1 , v2 ), (v3 , v4 ), (v5 , v6 ) ∈ E のうちのいずれか 2 辺に対して X-replacement. 以上の事から, LX (v0 , v1 ) と LX (v0 , v2 ) は, 4 辺 (v0 , v3 ), (v0 , v4 ), (v0 , v5 ), (v0 , v6 ) のう. を行ってできるグラフは Laman グラフである. 今 (v3 , v4 ), (v5 , v6 ) ∈ E の 2 本に対して. ち 2 本ずつをかぶりなく分け合っているはずである. いま (v0 , v3 ), (v0 , v4 ) ∈ LX (v0 , v1 ). X-replacement を行ってできる Laman グラフを GX とする (図 13).. および (v0 , v5 ), (v0 , v6 ) ∈ LX (v0 , v2 ) を仮定する. このとき, LX (v0 , v1 ) において, v0 に. v0. GX. v1. v1. LX (v0 , v1 ) と LX (v0 , v2 ). の 1 点しか共有点を持たない. また, LX (v0 , v1 ) と LX (v0 , v2 ) を渡すような辺は (v1 , v2 ) の 1. (v1 , v2 ), (v3 , v4 ), (v5 , v6 ) ∈ E の組合せが必ず存在する.. G. v2. つまり GX が Laman グラフであることに矛盾するため, LX (v0 , v1 ) と LX (v0 , v2 ) は v0. うことで rigid なグラフ G = (V , E ) が生成されるような, 対象となる disjoint な 3 辺. 証明. LX(v0,v2). LX(v0,v1). v5. Henneberg I の逆操作を行ってできるグラフはもちろん Laman グラフである. つまり, このグラフに (v3 , v4 ) を加えたグラフは redundant な辺を有するグラフである. しかしこのグ. v6 v2. v3. v4. v5. ラフは元の Laman グラフ GX に部分グラフとして含まれているため矛盾が生じる. つまり. v6 v2. v3. v4. 仮定が間違っていることがわかり, LX (v0 , v1 ) と LX (v0 , v2 ) は, (v0 , v3 ), (v0 , v4 ) のうちか. v5. ら 1 本ずつ, (v0 , v5 ), (v0 , v6 ) のうちから 1 本ずつをかぶりなく含んでいるはずである. こ. 図 13 G に X-replacement. こで (v0 , v3 ), (v0 , v5 ) ∈ LX (v0 , v1 ) および (v0 , v4 ), (v0 , v6 ) ∈ LX (v0 , v2 ) としても一般性はこの GX は Laman グラフであることから, 新しく辺を挿入することでグラフの一部が. 失わない.. circuit になる. いま GX に (v0 , v1 ) を加えることで circuit になる部分 Laman グラフを. いま, LX (v0 , v1 ) と LX (v0 , v2 ) のそれぞれにおいて, v0 に Henneberg I の逆操作を行っ. LX (v0 , v1 ) とする. 同様に GX に (v0 , v2 ) を加えることで circuit になる部分 Laman グラ. たグラフをそれぞれ L1 , L2 とする. この両者は Laman グラフであり, はじめのグラフ G の. フを LX (v0 , v2 ) とする. ここでもしも (v1 , v2 ) ∈ LX (v0 , v1 ) ∪ LX (v0 , v2 ) であれば, 補題の. 部分グラフである (図 15).. 操作によって rigid なグラフが得られることがわかる.. L1 ∪ L2 ∪ {(v1 , v2 ), (v3 , v4 ), (v5 , v6 )} は Laman 部分グラフであり, L1 , L2 の間には. 以下では (v1 , v2 ) ∈ LX (v0 , v1 ) ∪ LX (v0 , v2 ) の場合を考える. このとき LX (v0 , v1 ) と. (v1 , v2 ), (v3 , v4 ), (v5 , v6 ) の 3 辺しか存在しない. 他の辺が存在すれば G が Laman グラ. LX (v0 , v2 ) は v0 の 1 点しか共有点を持たないはずである. というのは, LX (v0 , v1 ) と. フであることに反するためである. 以下では 3 つの場合に分けて考える.. 6. c 2012 Information Processing Society of Japan .

(7) Vol.2012-AL-139 No.1 2012/3/14. 情報処理学会研究報告 IPSJ SIG Technical Report L1. v1. L1∪L1. v3. L2∪L2 v3. v4. v5 図 15. v2. L2. v2. v6. v5. v6. L1 ∪ L2 ∪ {(v1 , v2 ), (v3 , v4 ), (v5 , v6 )}. 図 17 (L1 ∪ L1 ) ∪ (L2 ∪ L2 ). (i) (v1 , v3 ), (v2 , v4 ) ∈ E の場合.. (ii) (v1 , v3 ) ∈ E かつ (v2 , v4 ) ∈ E もしくは, (v1 , v3 ) ∈ E かつ (v2 , v4 ) ∈ E の場合.. 3 辺 (v1 , v3 ), (v2 , v4 ), (v5 , v6 ) について補題の操作を行うことを考える. つまり本証明冒. まず (v1 , v3 ) ∈ E かつ (v2 , v4 ) ∈ E のとき, v2 は L2 内で v4 以外の 2 点以上と接続して. 頭の議論と同様に, まず (v1 , v3 ), (v2 , v4 ) に対して X-replacement を行い, このグラフに. いるはずである. その v4 と接続している頂点のうち, v6 以外のある 1 点を u2 とする. こ. (v0 , v5 ) および (v0 , v6 ) を加えてできる redundant な部分グラフに (v5 , v6 ) が含まれていれ. こで, 3 辺 (v1 , v3 ), (v2 , u2 ), (v5 , v6 ) の 3 辺について補題の操作を行うことを考えると, (i). ば補題の操作によって rigid なグラフが生成される. もしも含まれていなければ, 先の L1 , L2. の場合と同様の議論となり, rigid なグラフが生成されることがわかる. (v1 , v3 ) ∈ E かつ. と同様な 2 つの Laman 部分グラフ L1 , L2 が存在する (図 16). L1. v1. L2. v2. (v2 , v4 ) ∈ E の場合についても同様である.. L1. L1. v1. (iii) (v1 , v3 ), (v2 , v4 ) ∈ E の場合. L2. v2. v1 が L1 内で接続している v3 , v5 以外の頂点を u1 , v2 が L2 内で接続している v4 , v6 以 v3. v4. v3. 外の頂点を u2 とする. ここで, 3 辺 (v1 , u1 ), (v2 , u2 ), (v3 , v4 ) に対して補題の操作を行うこ. v4. とを考えると, (i),(ii) の場合と同様の議論となり, rigid なグラフが生成される (図 18). v5. v6. v5. v6 L2. (ⅱ) L1. 図 16 (v1 , v3 ), (v2 , v4 ) ∈ E. ここで, v1 , v2 , v5 ∈ L1 および v3 , v4 , v6 としても一般性は失わない. |V (L1 ) ∩ V (L1 )| ≥ 2. (ⅲ). L1 v1. v2. v3. v5. 分グラフである.. u2. しかし, L1 ∪ L1 と L2 ∪ L2 の間には辺 (v5 , v6 ) が存在し, これは G が Laman グラフであることに対して矛盾が生じた (図 17). つまり, 補題の操作によって rigid なグラフが生成. v1. v2. u1 v3. L2 u2 v4. v5. v6. v6. L2. L2. 図 18. L1. L1. v4. かつ |V (L2 ) ∩ V (L2 )| ≥ 2 であることから, L1 ∪ L1 および L2 ∪ L2 は Laman 部分グラフである. また, |(L1 ∪ L1 ) ∩ (L2 ∪ L2 )| ≥ 2 であるので, (L1 ∪ L1 ) ∪ (L2 ∪ L2 ) も Laman 部. L2. (ii) (v1 , v3 ) ∈ E かつ (v2 , v4 ) ∈ E. (iii) (v1 , v3 ), (v2 , v4 ) ∈ E. 以上より, Laman グラフ G に対して補題の操作を行うことで rigid グラフが生成できる. されることがわかる.. ような, disjoint な 3 辺の組み合わせが必ず存在することが示された.. 7. 2. c 2012 Information Processing Society of Japan .

(8) Vol.2012-AL-139 No.1 2012/3/14. 情報処理学会研究報告 IPSJ SIG Technical Report. 5. 未解決問題 2 章では Laman グラフを 2-edge-rigid グラフに冗長化させる問題について述べたが, Laman グラフを最小数の辺を加えることで 3-edge-rigid 以上のグラフに冗長化させる問題. * - replacement. X - replacement. については未解決である.. 図 19 X-replacement と ∗-replacement. また 4 章では, ∗-replacement によって剛性および冗長性を維持しようとする際に, その. 図 19 は ∗-replacement で Laman グラフが維持されない例である. ここで以下の定理が. 対象となる 3 辺については任意に選ぶことが出来ないことを示したが, ∗-replacement の逆. 導かれる.. 操作についても, 任意の 6-regular かつ 5-edge-rigid に対していつでも実行可能かは未解決. 定理 5 5-edge-rigid グラフ G = (V, E) において, ∗-replacement の操作を行うこ. な問題である. 一方で完全グラフ K7 は, 6-regular かつ 5-edge-rigid である頂点数が最小の. とで再び 5-edge-rigid グラフ G を生成できるような, 対象となる disjoint な 3 辺. グラフである. つまり, この K7 に対して ∗-replacement を繰り返し適用することによって,. (v1 , v2 ), (v3 , v4 ), (v5 , v6 ) ∈ E の取り方が必ず存在する. 証明. 辺数最小の 5-edge-rigid グラフが得られることがわかるが, この操作のみによってすべての辺数最小な 5-edge-rigid グラフが得られるかについては明らかにはなっていない.. ∗-replacement の操作を行ってできる G から任意の 4 辺を除いてもまだ rigid であ. 同様の問題がさらに冗長なグラフを生成する際にも生じるため, k ≥ 2 における辺数最小. ることを示す. 本証明でも除く 4 辺について場合分けを行って考える.. の (2k + 1)-edge-rigid グラフをすべて列挙する問題についても同様に未解決である.. 新しく加えた辺から 1 本以上除く場合に関しては, 補題 4 の証明と同様に, Henneberg. I,II および X-replacement を用いることによって想定すべきグラフが得られるので, 任意の disjoint な 3 辺 (v1 , v2 ), (v3 , v4 ), (v5 , v6 ) ∈ E に対して主張が成り立つことがわかる.. 参. 以下では, 4 辺全て既存の辺から除く場合について考える. G. v1 v2. v3. v4. v5. v6. v1. v2. v6 v3. v4. 文. 献. 1) A.Garcia, J.Tejel: Augmenting the Rigidity of a Graph in R2 . Algorithmica 59, pp.145-168, 2011. 2) J.Graver, B.Servatius, H.Servatius: Combinatorial Rigidity. AMS Graduate Studies in Mathematics, vol.2, American Mathematical Society, Providence, 1993. 3) C.Kiraly, F.Peterfalvi: Balanced generic circuits without long paths. Egervary Research Group, Technical Reports H-1117, pp.1-16, 2011 4) G.Laman: On graphs and rigidity of plane skeltal structures. Jounal of Engineering mathematics, 4(4), pp.331-340, 1970. 5) L.C.Lomeli, L.Moshe, W.Whiteley: Bases and circuits for 2-rigidity: Constructions via tree partitions. Technical Report, York Univercity, http://www.math.yorku.ca/ Who/Faculty/Whiteley/menu.html 6) W.Whiteley: Some matroids from discrete applied geometry. Contemporary Mathematics, vol.197, pp.171-311, 1996.. v0. G. 考. v5. 図 20 既存辺から 4 本削除. 元の G から (v1 , v2 ), (v3 , v4 ), (v5 , v6 ) ∈ E 以外の 4 辺を除いてもまだ rigid である. ここで先の補題 7 より, ∗-replacement を行うことで rigid グラフが得られるような, 対象の. disjoint な 3 辺が必ずこのグラフには存在する. その 3 辺を (v1 , v2 ), (v3 , v4 ), (v5 , v6 ) ∈ E と設定し直した上で ∗-replacement を実行することで, 想定するグラフが得られ, もちろんこのグラフは rigid である.. 2. 8. c 2012 Information Processing Society of Japan .

(9)