極小剛なBody-Hingeグラフの列挙（2013年4月15日版）
8
0
0
全文
(2) Vol.2013-AL-144 No.13 2013/5/17. 情報処理学会研究報告 IPSJ SIG Technical Report. (a). 図 1. (b). (c). (a). (a) body-bar, (b) body-hinge 及び (c) panel-hinge フレー. 図 2. (b). (a)splitting off (b)contraction. ムワーク. 繹的な生成方法や, 多項式時間 (出力 1 つあたり) 列挙アル. eが ワークとして実現可能であるための必要十分条件は, G. ゴリズムはこれまで知られていない.. D 個の辺素な全域木をもつことである, ということを意味. 一般に, グラフ G の k 本の並列な辺の複製によって各辺 が置き換えられたグラフを kG と記述するが, 本論文では e と記述する. (D − 1)G を G 命題 1. [1], [7], [9] 多重グラフ G が R に剛な bodyd. hinge 及び, panel-hinge フレームワークとして実現可能で e が D 個の辺素な全域木をも あるための必要十分条件は, G つことである.. している. 極小剛な Body-Hinge グラフに関する性質: 極小剛な body-hinge グラフ G = (V, E) が与えられたと き, より小さなサイズの body-hinge グラフを生成する２つ の操作が知られている [1].. 1 つは剛な真部分グラフを縮約する操作 contraction(図 2(a)) である (G0 = (V 0 , E 0 ) が G の剛な部分グラフで. body-bar グラフと異なり, 命題 1 を満たす body-hinge. 1 < |V 0 | < |V | を満たすとき剛な真部分グラフとよばれ. グラフに対するマトロイド的な特性は存在しないので,. る). もうひとつの操作は splitting off と呼ばれる操作 (図. body-hinge グラフを多項式時間で列挙するアルゴリズムを. 2(b)) が知られている. ここでグラフ G の頂点 v について,. 容易に構築することはできない.. v に隣接する頂点集合を NG (v) とする. splitting off とは,. 研究の成果: 単純グラフである極小剛な body-hinge グラ. 次数 2 の頂点 v に対して NG (v) = {a, b} とするとき, G よ. フを演繹的に生成する 4 つの操作を明らかにし, 多項式時. り v(及び v に接続する辺) を取り除き, 新たな辺 ab を追加 ab する操作のことである. 得られたグラフを Gab v とする. Gv. 間で列挙するアルゴリズムを開発した.. は G において va または vb のどちらかを縮約することと. 2. 準備. 同等である.. G = (V, E) を 自 己 ル ー プ を 含 ま な い グ ラ フ と す る.. splitting off は, 一般には極小性は保証されていない [1]. し. X ⊆ V のとき, G[X] を X によって誘導されるグラフ. かし剛な真部分グラフを持たないグラフに限定した場合,. とする. X ⊆ V のとき, δG (X) = {uv ∈ E|u ∈ X, v 6∈ X}. splitting off による極小性は保証される.. とする. X = v のとき, δG ({v}) を δG (v) と記す. V の分. 以下の 5 つの補題が示されている [1].. 割 P とは, 頂点集合の部分集合の族 {V1 , V2 , . . . , Vm }(Vi 6=. 補題 1. ∅(1 ≤ i ≤ m), Vi ∩ Vj = ∅(1 ≤ i, 1 ≤ j, i 6= j), ∪m i=1 Vi = V ) のことである. m = 2 のときは P = {V1 , V2 } であり, 特 に, P の異なる集合をつなぐ G の辺集合を δG (P) とする. e = (D − 1)G の辺集合を E e とし, ある辺 e ∈ E に対し G. e = (V, E) e としたとき, て e˜ = {e1 , e2 , . . . , eD−1 } とする. G e e e E のマトロイドを M(G) とし, M(G) の基底を B とする. e のランクが D(|V | − 1) と等しいことは, G eにD個 M(G) の辺素な全域木を詰込むことができることの必要十分条件 であることが知られている.. [1] グラフ G を剛な body-hinge グラフとしたと. き, G は二辺連結グラフである. 補題 2 0. [1] G = (V, E) を極小剛な body-hinge グラフ, 0. G = (V , E 0 ) を G の剛な部分グラフとするとき, G から E 0 を縮約してえられるグラフは極小剛な body-hinge グラ フである. 補題 3. [1] 剛な真部分グラフをもたない, 多重グラフを. 含んだ極小剛な body-hinge グラフ G = (V, E) について考 える. このとき, 以下の式が成り立つ.. (D − 1)|E| < D(|V | − 1) + D − 1. 辺素な全域木: 以下の定理が Tutte および Nash-williams によって示さ. 補題 4. (2). [1] 剛な真部分グラフをもたない 2 辺連結であ. る極小剛な body-hinge グラフ G = (V, E) について考え. れている [4][8]. あるグラフ G =. る. このとき, G は頂点数が高々 D のサイクルグラフであ. (V, E) が k 個の辺素な全域木を含んでいることの必要. るか, 0 ≤ i ≤ d − 1 の vi vi+1 ∈ E かつ 0 ≤ i ≤ d − 1 の. 十分条件は, 頂点集合 V の任意の分割 P に対して以下の式. dG (vi ) = 2 であるような長さ d の点列 v0 v1 . . . vd をもつ.. 定理 1 (Tutte, Nash-Williams). 補題 5. が成り立つことである.. |δ(P)| ≥ k(|P| − 1). hinge グ ラ フ G = (V, E) に つ い て 考 え る. こ の と き, (1). 定理 1 は body-hinge グラフが剛な body-hinge フレーム ⓒ 2013 Information Processing Society of Japan. [1] 剛な真部分グラフをもたない極小剛な body-. NG (v) = a, b である任意の次数 2 の頂点 v にたいして, splitting off の操作をおこなったとき, Gab v は極小剛な 2.
(3) Vol.2013-AL-144 No.13 2013/5/17. 情報処理学会研究報告 IPSJ SIG Technical Report G. body-hinge グラフである.. a. 3. 単純グラフである極小剛な Body-Hinge グ ラフを演繹的に生成する操作 H. 本章では, はじめにより大きな単純グラフである極小剛. v. a. b. な body-hinge グラフを演繹的に生成する操作を示す. 4.1 の極小性と剛性が保証されていることを示す. 4.2 では, 導. b. v. H. a. では, それらの操作によって生成される body-hinge グラフ. a. b. G. G. G. x. દ˺. y. દ˺. a. H b. a. b. v. v. H. a. ‣. v. a. b દ˺. ․. દ˺. 図 3 極小剛な panel-hinge グラフを演繹的に生成する操作. 入した操作を繰り返し用いることで任意の単純グラフであ る極小剛な body-hinge グラフが生成可能であることを証. G. v. H. 明する. 単純グラフである頂点数 n(n ≥ 3) の極小剛な body-hinge. a. a. b. b. グラフ G = (V, E) について考える. ここで, 以下の 4 つの 操作を定義する.. ⁰ ab. ⁰ G. 操 作 1(edge split).. あ る 辺 e ∈ E に 対 し て e˜ =. {e1 , e2 , . . . , eD−1 } としたとき, |B ∩ e˜| ≤ D − 2 である e の基底 B が存在する場合. (図 3(1)) ような M(G) ( 1 ) 新しく頂点 v を加える. ( 2 ) 辺 e ∈ E の端点 a, b ∈ V に対して v から辺 va, vb を 引く.. k. a. b. vb ⁰. va ⁰. ⁰ H a. b. 66-k Tj (a). 図4. T. j (b). (a) 極小剛な body-hinge グラフ G 及び G を D − 1 重化した グラフ (b) 操作 1 によりできるグラフ H 及び H を D − 1 重 e ただし, D = 6) 化したグラフ H(. ( 3 ) 辺 e ∈ E を取り除く. 操 作 2(edge split plus 1-addition).. ある P に対して. はじめに, 極小剛な body-hinge グラフ G = (V, E) に操作. 5|δG (P)| = 6(|P| − 1) を満たす場合. (図 3(2)). 1(edge split) を行ったグラフ H = (V 0 , E 0 ) が, 剛であるこ. ( 1 ) 新しく頂点 v を加える. ( 3 ) 辺 e を取り除く.. とを示す. e に詰込むことのできる, D 個の辺素な全域木を Tj (1 ≤ G e における辺素な全域木 T 0 , . . . , T 0 を, j ≤ D) とする. H. ( 4 ) 頂点分割 P より v からなる頂点集合を加えたも. 各々 T1 , . . . , TD から構成できることを以下に示す.. ( 2 ) 辺 e の端点 a, b ∈ V に対して v から辺 vb, va を引く.. 1. の を 頂 点 分 割 P 0 と す る と き, 異 な る 2 つ の 頂 点 0. 0. 集 合 Vx ∈ P ,Vy ∈ P に そ れ ぞ れ 含 ま れ る 頂 点. D. 操作 1 の条件より辺 abi (1 ≤ i ≤ D − 1) を使用する全域木. x ∈ Vx , y ∈ Vy を端点とする辺 xy を加える. この. は高々 D − 2 本で, それらを T1 , . . . , Tk (k ≤ D − 2) とした e を使用しない全域木 Tk+1 , . . . , TD は, (D − k) 個 とき, ab. とき, xy を加えてできるグラフが剛となるように追加. となる (図 4(a)).. する.. 辺 abi (1 ≤ i ≤ D − 1) を使用していた全域木 Tj (1 ≤. 操作 3(vertex 2-addition). 以下の操作を行ってできるグラ. j ≤ k) に 対 し て Tj0 は vai , vbi を 使 用 す る こ と と し,. フもまた, 極小剛な body-hinge グラフの場合.(図 3(3)). Tj0 = Tj \ ab ∪ {vai , vbi }(1 ≤ j ≤ k) とする. このと. ( 1 ) 新しく頂点 v を加える.. 0 0 き D − k 個の全域木 Tk+1 , . . . , TD が v に到達するため e には, vf a, vb の残りの辺を使用する必要がある. すなわ. ( 2 ) a, b ∈ V (a, b 6= v) を任意に選び v から辺を引く. 操作 4(triangle-addition). (図 3(4)). ち 2(D − 1 − k) ≥ D − k を満たす必要があるが, これは. ( 1 ) 新しく頂点 v1 , v2 および辺 v1 v2 を加える.. k ≤ D−2 より満たされており, グラフ H は剛な body-hinge. ( 2 ) 頂点 a ∈ V を任意に選び v1 および v2 から辺 v1 a, v2 a. グラフである.. を引く. 操作 2 の条件を満たすような P をみつけることは, [5] よ り多項式時間で実行可能である.. 次に H が極小であることを背理法により示す.. H が極小ではないと仮定し, 矛盾を示す. すなわち E 0 に取 り除いても H が剛であるような冗長な辺が存在している ことである. ここで, H の頂点 v に splitting off を行った. 3.1 各操作の正当性について 定理 2 0. 定義した 4 つの操作によってできるグラフ 0. H = (V , E ) もまた極小剛な body-hinge グラフである. 証明. 1. edge split(図 3(1)). ⓒ 2013 Information Processing Society of Japan. グラフを Hvab = (V, E) とし, 冗長な辺を辺 st とする. こ のとき, 頂点 v の次数は 2 で, 辺 va, vb を取り除くことは できないので取り除くことが可能な辺 st は st ∈ E となる. ここで, グラフ H より辺 st を取り除き, さらに頂点 v に 対して, 操作 1 の逆操作 (splitting off) を行ったグラフを. 3.
(4) Vol.2013-AL-144 No.13 2013/5/17. 情報処理学会研究報告 IPSJ SIG Technical Report G. v. H. a. G. a. b. a. b. v. H. a. b. b. c. ⁰ G. v. ⁰ H a. b. ⁰ G. a. T6. a. b. (a). a. b. c ‚⁓‛. (b). 図 5 (a) 極小剛な body-hinge グラフ G 及び G を (D − 1) 重化 e (b) 操作 2 によりできるグラフ H 及び H を したグラフ G. 図6. Tj. T'j ‚⁔‛. (a) 極小剛な body-hinge グラフ G 及び G を D − 1 重化した e (b) 操作 3 によりできるグラフ H 及び H を (D − 1) グラフ G e 重化したグラフ H. e (ただし, D = 6) (D − 1) 重化したグラフ H ab {H \ st}ab v とする. {H \ st}v もまた剛となるが, これは. グラフ. b. T'6 c. Hvab. v. ⁰ H. に冗長な辺が存在したこととなり, グラフ. Hvab. が極小であることに矛盾.. (D − 1)|δH\f (P 0 )| − D(|P 0 | − 1) = (D − 1)(|δG (P)| + 1) − D|P| = −1 < 0. (6). となり矛盾. よって H は極小剛な body-hinge グラフであ. よって H は極小剛な body-hinge グラフである. 2. る.. 2. edge split plus 1-addition(図 3(2)). 2. はじめに, グラフ H が剛な body-hinge グラフであること. 3. vertex 2-addition(図 3(3)). を示す. e に詰込むことのできる, D 個の辺素な全域木を Tj (1 ≤ G. はじめに, グラフ H が剛な body-hinge グラフであること e に詰込むことのできる, D 個の辺素な全域木を を示す. G. j ≤ D) とする. 辺 abi (1 ≤ i ≤ D − 1) を使用する全域木 e を使用しない全域木を TD とする を T1 , . . . , TD−1 とし, ab. Tj (1 ≤ j ≤ 6) とする. e を追加したグラフとする (図 e をG e に, 頂点 v 及び vf H a, vb. (図 5(a)). e の D 個の辺素な全域木を T 0 (1 ≤ j ≤ D) とし, 辺 H j. e の D 個の辺素な全域木を T 0 (1 ≤ j ≤ D) とし, 6(b)). H j. abi (1 ≤ i ≤ D − 1) を使用していた全域木は vai , vbi を使. Tj0 = Tj ∪{vai , vbi }(1 ≤ j ≤ k) とする. このとき Tj0 が頂点 e は v に到達するためには, D 本の辺が必要であるが, vf a, vb. 用することとし, Tj0 = Tj \ ab ∪ {vai , vbi }(1 ≤ j ≤ k) とす. 合わせて 2(D −1) 本あるので, グラフ H は剛な body-hinge. る. このとき. 0 TD. が頂点 v に到達するためには, 辺 vc e を使. グラフである.. 用すればよいので, グラフ H は剛な body-hinge グラフで. このように, vertex 2-addition を行ってできるグラフ H も. ある.. また剛ではあるが, 極小であるとは限らない. そのため, 操. 次に H が極小であることを示す. H に冗長な辺 f が存在. 作後のグラフが極小であるかどうかをペブルゲームを用い. すると仮定し, 背理法を用いて示す.. てテストし, 極小である場合にのみ, この操作を実行する.. G の各頂点をそれぞれ一つの頂点の部分集合とするような e の辺 頂点分割 P を考える. 操作 2 を行う際の条件より, G. 4. triangle-addition(図 3(4)). の本数と D 個の辺素な全域木が必要とする辺の本数が一 致することから,. はじめに, H が剛な body-hinge グラフであることを示す. eに グラフ G は極小剛な body-hinge グラフであるので, G. D 個の辺素な全域木を詰め込むことが可能である. 追加す る三角形グラフを F としたとき, Fe もまた D 個の辺素な. (D − 1)|δG (P)| = D(|P| − 1). (3). 全域木を詰め込むことが可能である. 全域木同士を 1 つの 頂点を共有してできるグラフもまた全域木となることから,. が成立している.. H もまた剛な body-hinge グラフである.. P に新たに加えた頂点 v を単独の集合として加えた, H\f. H が極小であることは G と F が極小であることから明ら. の頂点分割を P 0 としたとき, P と P 0 の関係は. かである. 以上より H は極小剛な body-hinge グラフである.. |δH\f (P 0 )| = (|δG (P)| + 1) 0. |P | = |P| + 1. (4) (5). 2. 3.2 任意の単純グラフである極小剛な body-hinge グラ フの生成 定義した 4 つの操作の操作列により, 任意の単純グラフで. である. 0. 定理 1 より P に対して冗長であることを仮定している. ある極小剛な body-hinge グラフを生成することが可能で. ので,. あることを示すために, 以下の補題を示す.. ⓒ 2013 Information Processing Society of Japan. 4.
(5) Vol.2013-AL-144 No.13 2013/5/17. 情報処理学会研究報告 IPSJ SIG Technical Report. 補題 6. 頂点数 3 以上の単純グラフである極小剛な bodyv. hinge グラフには, 次数 2 の頂点が少なくとも 1 つ存在する. 証明. 背理法を用いて, 次数 2 の頂点が存在することを. 示す. すべての頂点の次数が 3 以上の単純グラフである極. a. b. 小剛な body-hinge グラフの存在を仮定する. 以下では, 剛 図 7. な真部分グラフを持たない場合と持つ場合の, 2 つの場合 にわけて考える.. 二重辺を縮約して再び二重辺ができる場合. |V 0 | ≥ 3 より次数 2 の頂点が (11) より 3 個以上存在する. 2. Case 1. 剛な真部分グラフを持たない場合.. G は次数 2 の頂点をもたないという仮定より, |δ(V 0 )| ≥ 3. 剛な真部分グラフをもたないグラフ G について考える.. であるので, V 0 の各頂点は G において次数が 3 以上となっ. 補題 4 から以下の条件を満たしている.. ていることに注意しておく. 以下では G0 を縮約して出来 るグラフを G00 とし, G00 が多重辺をもつ場合と持たない場. (D − 1)|E| < D(|V | − 1) + (D − 1). (7). 合の 2 つの場合にわけて考える.. Subcase 2A. G00 が多重辺をもたない場合.. このとき頂点数と辺の関係は, すべての頂点次数が 3 以上. このとき, G00 はすべての頂点の次数が 3 以上の単純グラ. なので,. フである極小剛なグラフであり, G よりも頂点数が少ない. よって矛盾.. 3|V | ≤ 2|E|. (8). Subcase 2B. G00 が多重辺を 1 つ以上もつ場合. ここで, 以下の主張を示す.. が成り立つ. (7)(8) より、. 主張 2. G = (V, E) を極小剛な body-hinge グラフとす. る. G が多重辺をもつとき, それは二重辺であり, 二重辺を. 3(D−1)|V | ≤ 2(D−1)|E| ≤ 2D(|V |−1)+2(D−1) (9) を得る. これより, (D − 3)|V | ≤ −2 となるが |V | ≥ 3 に反 する. よって, 次数が 2 の頂点が存在する.. 縮約することにより, あらたな多重辺は生じない. 証明. G が多重辺をもつとき, 三重辺以上の場合はその. うちの 1 辺が冗長であるので極小性に反する. なぜならば,. G0 は極小剛な body-hinge フレームワークであることから,. Case 2. 剛な真部分グラフを持つ場合.. G0 と G \ G0 の間の 2 辺が 1 つの頂点 v ∈ G \ G0 を共有す. 剛な真部分グラフを持つグラフの中で頂点数の最も少な. る場合もまた剛であるので, 3 辺のうち 1 辺は冗長である.. いものを G とする. G における極小剛な真部分グラフの. 二重辺は剛な真部分グラフであるので, 補題 2 より二重辺. 0. 0. 0. うち, 頂点数の最もすくないものを G = (V , E ) とする.. を縮約しても極小性は失われない.. |V 0 | ≥ 3 より V 0 により誘導された G の部分グラフ G[V 0 ]. 二重辺を縮約して再び二重辺ができる場合があると仮定. を考える.. する. そのような場合は, 頂点 a, b ∈ V があいだに二重辺. ここで以下の主張を示す. 主張 1. ab1 , ab2 をもち, さらに共有点 v をもつときである (図 7).. 頂点数 3 以上の単純グラフである極小剛な body-. このとき, 辺 ab1 は冗長となっており, 補題 2 に反する. し. hinge グラフが, 剛な真部分グラフを持つ場合, その誘導部. たがって, 二重辺を縮約することにより, 多重辺は生じな. 分グラフには次数 2 の頂点が 3 個以上存在する.. い.. 証明. 2. 0. G[V ] の次数が 2 の頂点が k 個あるとき, 次数が. 3 以上の頂点は |V 0 | − k 個存在することとなる. このとき 頂点数と辺の関係は, すべての頂点次数が 3 以上なので,. 主張 3. G00 において G0 を縮約した頂点を s としたとき,. s に隣接する頂点が 3 つ以上ある場合は, s を端点にもつす べての多重辺を縮約した場合にも, 次数 2 の頂点が生じる. 2k + 3(|V 0 | − k) ≤ 2|E|. (10). (7)(10) より,. ことはない. 証明. 頂点 s に隣接する頂点が l 個存在するとし, 各頂. 点を v1 . . . vl とする. そこで二重辺が存在する場合につい て考える. s, vl 間に二重辺があると仮定しても一般性は失 わない. このとき. 2(D − 1)k + 3(D − 1)(|V 0 | − k) ≤ 2(D − 1)|E|. |δ(vl )| ≥ 3. ≤ 2D(|V 0 | − 1) + 2(D − 1) k ≥ (D−3)|V 0 |/(D−1)+2/(D−1) ⓒ 2013 Information Processing Society of Japan. (11). (12). が成り立っている (図 8).. 5.
(6) Vol.2013-AL-144 No.13 2013/5/17. 情報処理学会研究報告 IPSJ SIG Technical Report. δ( vl ). v. vl. G' P1. a. s. b. P2 v1 vl-1. v2. 図 10. 図 8 頂点 s0 に隣接する点. G0 がサイクルグラフである場合. v. G' a. b c. d v'. 図 9. G0 の頂点数が D + 1 以上の場合 (D = 6). 図 11. s, vl 間の二重辺を縮約してできる頂点を s0 とすると,. G00 において G0 を縮約した頂点に隣接する頂点が, 2 つの 場合. のパスが存在する (図 10). このとき, G0 は点数最小の極小剛な真部分グラフであるこ. 0. |δ(s )| ≥ l − 1 + |δ(vl )| − 2. (13). とから,. が成り立つ. よって (12) より δ(s0 ) ≥ l である. ここで s に接続する多重辺を縮約して出来る頂点を s∗ とすると,. |P1 | + |P2 | ≤ |P1 | + 2. (14). |δ(s∗ )| ≥ l であるので, 以上より l ≥ 3 のとき, すべての多. |P1 | + |P2 | ≤ |P2 | + 2. (15). 重辺を縮約した場合にも, 次数 2 の頂点が生じることはな い.. 2. 補題 4 より, G0 は長さ D 以下のサイクルグラフである場 合か, 頂点数が D + 1 以上の連続する (d − 1) 個の次数 2 の 頂点をもつグラフの場合のいずれかである.. Case 1. G0 の頂点数が D + 1 以上の場合.. が成り立つ. なぜなら, そうでなければ P1 ∪ {va, vb} また は P2 ∪ {va, vb} のサイクルグラフが, G0 より点数が小さい ので, G0 の最小性に反する. よって |P1 | ≤ 2, |P2 | ≤ 2 であ るので, 以下の場合について考える.. Subcase 2A. |P1 | = 1, |P2 | = 1 のとき. このとき G0 を縮約してできるグラフを G00 とする. G0 が. 多重グラフとなり G が単純グラフであることに反する.. 極小であることと, 剛な真部分グラフをもたないことから,. Subcase 2B. |P1 | = 2, |P2 | = 1 のとき. 0. 0. (11) より (D + 1) 以上なので, G は G \ G との間に (D − 1). このとき G0 は長さ 3 のサイクルグラフであるが, G0 ∪ v で. 本以上の辺をもつ. G0 と G \ G0 を結ぶ辺が G \ G0 側に共. 誘導されるグラフは明らかに冗長であり, G が極小剛であ. 00. 有点をもたない場合, G に次数 2 の頂点が生じることはな い. 以下では G0 と G \ G0 を結ぶ辺が共有点をもつ場合を 考える. 主張 2 より, 二重辺を縮約して再び二重辺ができ る場合はないので, 縮約していくことにより次数 2 の頂点 が生じることはない.. ることに反する.. Subcase 2C. |P1 | = 2, |P2 | = 2 のとき P1 , P2 に含まれる頂点をそれぞれ c, d とし, x ∈ V 0 と G\G0 をつなぐ辺の集合を Ex とする. 主張 3 より, G00 において. G0 を縮約した頂点に隣接する頂点が, 2 つ以下の場合を考. Case 2. G0 が長さ D 以下のサイクルグラフである場合.. える.. G0 と G \ G0 の間の 3 辺が 1 つの頂点 v ∈ G \ G0 を共有す. 1 つの場合は冗長な辺が存在することとなる.. る場合は, そのうちの 1 辺が冗長であるので G が極小剛で. 2 つの場合, δ(V 0 ) ≥ 4 より, e ∈ Ec と e0 ∈ Ed が共有点. あることに反する. そこで, G0 と G \ G0 をつなぐ 2 辺が 1. v 0 ∈ G \ G0 をもつ場合 (図 11) のみである.. つの頂点 v ∈ G \ G0 を共有する場合を考える. そのような. このとき, v, a, c, v 0 , d, b を頂点とする六角形グラフが存在. 2 辺を va, vb とする.. し, 辺 ad, bc は冗長であるので, G が極小であることに反. このとき, 補題 1 より, 剛な body-hinge グラフは 2 辺連結 0. であることから, 頂点 a, b ∈ G の間には辺素な辺列 P1 , P2 ⓒ 2013 Information Processing Society of Japan. する. 以上のことから, 縮約した後の頂点が次数 2 とはならない. 6.
(7) Vol.2013-AL-144 No.13 2013/5/17. 情報処理学会研究報告 IPSJ SIG Technical Report. ことがわかった. したがって縮約してできるグラフもま. v. G. た, すべての頂点の次数が 3 以上の単純グラフである極小. a. すべての頂点の次数が 3 以上の単純グラフである極小剛な. body-hinge グラフであるという, 仮定に反する.. P. 定理 3. 定義した 4 つの操作により, 任意の単純グラフ. である極小剛な body-hinge グラフを生成することが可能 である. 証明. 帰納法を用いて示す. n ≥ 4 である頂点数 n − 1 以. 下の任意の極小剛な body-hinge グラフは, 三角形グラフを 初期グラフとし, 4 つの操作の操作列により生成可能であ ると仮定する. 頂点数 n の任意の極小剛な body-hinge グ ラフ G = (V, E) が与えられたとき, 4 つの操作の逆操作に よって, 頂点数が n − 1 または n − 2 の極小剛な body-hinge グラフを生成できることを示す. ここで G の辺集合 E が 2 つの空でない部分集合 E1 , E2 に 分割され, E1 , E2 を辺集合とする G の辺誘導部分グラフを, それぞれ G[E1 ], G[E2 ] とする. 以下では G[E1 ] と G[E2 ] が ちょうど 1 点 v だけで共有するとき, v を G の切断点 (cut. point) と呼ぶ. 極小剛な body-hinge グラフ G が切断点をもち, 切断点に より分割してできるグラフのうち, 少なくとも 1 つが三角 形グラフのときには, 操作 4 の逆操作を行うことで, 頂点数 が 2 小さい極小剛な body-hinge グラフとなる. 以下では, 操作 4 の逆操作を行うことができない場合を考. b. P. (a). (b). 図 12. 2. a. b. e. e P. 以上より単純グラフである極小剛な body-hinge グラフに は, 次数 2 の頂点が少なくとも 1 つ存在する.. a. b. 剛な body-hinge グラフであり, G が頂点数の最も少ない,. G'(=G ab v /e). G ab v. (c). 操作 1, 操作 2 の逆操作. 行ったグラフを Gab v とする. このとき, 辺 ab が冗長な辺で ある場合は, 辺 ab を取り除くこととする. この操作は, 操 作 3 の逆操作 (vertex 2-addition) を行うことに相当する. ここで, グラフ G = (V, E) に対して操作 3 の逆操作を行っ てできるグラフ G0 が極小であることを示す. G0 が冗長で あると仮定する. このとき, 操作 3 の逆操作を行う G の次 数 2 の頂点を v, v に隣接する頂点を a, b とする. G0 が冗 長であるとき, G に冗長な辺が存在することとなり, G が 極小であることに反する. すなわち, 頂点数が 1 少ない極小剛な body-hinge グラフと なり, 帰納法の仮定を満たす. そこで, 辺 ab 以外の辺 e ∈ E \ {av, bv} が冗長な辺である 場合について考える. 以下では頂点分割 P = {V1 , V2 , . . . , Vm } において, v, a, b の含まれ方について 4 つの場合に場合分けして考える.. Subcase 2A. v, a, b ∈ V1 のとき. P より v からなる頂点集合を除いた頂点分割を P 0 とする とき, P と P 0 の関係は. える. さらに操作 1 の逆操作, 操作 2 の逆操作, 操作 3 の逆 操作の順に各操作が行えない場合を考えていき, いずれか の操作が可能であることを示す. 以下では剛な真部分グラフをもたない場合ともつ場合の, 2 つの場合にわけて考える.. |P 0 | = |P|. (16). |δG0 (P 0 )| = |δG (P)| − 1. (17). Subcase 2B. v ∈ V1 , a, b ∈ V2 のとき.. Case 1. 剛な真部分グラフをもたない場合.. P より v からなる頂点集合を除いた頂点分割を P 0 とする. 補題 6 より次数 2 の頂点が少なくとも 1 つ存在するので,. とき, P と P 0 の関係は. この場合には操作 1 の逆操作 (splitting off) を行う. この とき, 補題 5 より, 極小剛な body-hinge グラフとなり, 頂. |P 0 | = |P| − 1. (18). |δG0 (P )| = |δG (P)| − 3. (19). 点数が G より 1 小さいグラフ G0 を得ることができ, 帰納 法の仮定をみたす.. Case 2. 剛な真部分グラフをもつ場合. はじめに操作 1 の逆操作 (splitting off) を行うことを考え る. このとき, 剛ではあるが極小性は保証されていない. 極 小のときには, 頂点数が G より 1 小さいグラフ G0 を得る ことができ, 帰納法の仮定をみたす.. 0. Subcase 2C. v, a ∈ V1 , b ∈ V1 のとき. P より v からなる頂点集合を除いた頂点分割を P 0 とする とき, P と P 0 の関係は. そこで, 操作 1 の逆操作によって冗長となる場合を考える. グラフ G より頂点 v(及び v に接続する辺) を取り除き, 新. |P 0 | = |P|. (20). たな辺 ab を追加したグラフ, すなわち操作 1 の逆操作を. |δG0 (P 0 )| = |δG (P)| − 1. (21). ⓒ 2013 Information Processing Society of Japan. 7.
(8) Vol.2013-AL-144 No.13 2013/5/17. 情報処理学会研究報告 IPSJ SIG Technical Report G. v. (D − 1)(|δG0 (P 0 )| + 2) = D(|P 0 | + 1) − 2. G'. a. a. b. (D − 1)|δG0 (P 0 )| = D(|P 0 | − 1). b. (30). e. となり, δG0 (P 0 ) を (D − 1) 重化した辺のすべてが全域木 に使用されている状況であり, 操作 2 を行う際の条件と一 P. 致する. すなわち, 極小剛な body-hinge グラフ G に対し. P. ‚⁓‛. ‚⁔‛. 図 13. て, 操作 2 の逆操作をすることで頂点数が 1 小さい極小剛. 操作 2 の逆操作. な body-hinge グラフとなり, 帰納法の仮定を満たす. 以上より, 頂点数 n の任意の極小剛な body-hinge グラフ. Subcase 2D. v ∈ V1 , a ∈ V2 , b ∈ V3 のとき. それぞれ異なる頂点の部分集合に含まれ, かつ頂点 v は単. G = (V, E) が与えられたとき, 4 つの操作の逆操作によっ. 独である G の頂点分割 P をとるような場合.. て, 頂点数が n − 1 または n − 2 の極小剛な body-hinge グ. ここで. Gab v. ラフを生成可能である.. 2. 以上の議論から, 逆探索法を用いて 1 個あたり多項式時. 0. \ e を G とする.. G は剛な body-hinge グラフであることから, 定理 1 より任. 間の列挙アルゴリズムを作ることが可能である. 単純グ. 意の頂点分割 P に対して. ラフである極小剛な body-hinge グラフについて議論を. (D − 1)|δG (P)| ≥ D(|P| − 1). 行ったが, 多重グラフを許した場合にも同様な議論を行. (22). うことが可能である. その場合, 必要となる操作は, 操作. 4(triangle-addition) を除く, 3 つの操作で十分である.. が成り立つ. 極小であることから, 辺 e を除くと剛ではなくなるので,. e ∈ δG (P) を満たすある頂点分割 P に対して, 定理 1 より. 謝辞 多項式時間での計算可能性について，九州大学の神 山直之准教授にご教示頂いたことを深謝する．. 以下の不等式が成り立つ. 参考文献. (D − 1)|δG\e (P)| < D(|P| − 1). [1]. (D − 1)(|δG (P)| − 1) < D(|P| − 1) (D − 1)|δG (P)| < D|P| − 1. [2]. (23). 一方, P より v からなる頂点集合を除いた頂点分割を P 0 と. [3]. するとき, P と P 0 の関係は. |P 0 | = |P| − 1. (24). |δG0 (P )| = |δG (P)| − 2. (25). 0. 0 Gab v は剛であり, さらに辺 e は冗長な辺であるので, G も. [4] [5]. また剛な body-hinge グラフであることから定理 1 より,. (D − 1)|δG0 (P 0 )| ≥ D(|P 0 | − 1). (26). (24)(25)(26) より. (D − 1)|δG (P)| ≥ D|P| − 2. [7]. (27). (23)(27) を満たす整数の組 (|P|, |δG (P)|) は. (D − 1)|δG (P)| = D|P| − 2. [8]. [9]. (28). ここで,. |δG0 (P 0 )| = |δG (P)| − 2. [6]. [10]. N.Katoh, S.Tanigawa: A Proof of the Molecular Conjecture. Discrete Comput Geom, 45, pp.647-700, 2011. G.Laman: On graphs and rigidity of plane skeltal structures. Jounal of Engineering mathematics, 4(4), pp.331340, 1970. 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 Nash-Williams, C.: Edge-disjoint spanning trees of finite graphs. J. Lond. Math. Soc. 1(1), 445-450, 1961. A.Schrijver: Combinatorial Optimization: Polyhedra and Efficiency. Springer,Berlin, Volume B, p.881, Corollary 51.3b, 2003. S.Tanigawa: 構造物の組合せ剛性:計数条件とグラフ分割. Proceedings of the Twenty-Second RAMP Symposium, pp.31-48, 2010. T.Tay: Linking (n − 2)-dimentional panels in n-space II:(n − 2, 2)-frameworks and body and hinge structures. Graphs and Combinatrics, 5(1), pp.245-273, 1989. Tutte, W.T.: On the problem of decomposing a graph into n connected factors. J. Lond. Math. Soc.36, 221-230, 1961. W.Whiteley: The union of matroids and the rigidity of frameworks. SIAM Journal on Discrete Mathematics, 1(2), pp.237-255, 1988. W.Whiteley: Some matroids from discrete applied geometry. Contemporary Mathematics, vol.197, pp.171-311, 1996.. (29). とすると (24)(28)(29) より. ⓒ 2013 Information Processing Society of Japan. 8.
(9)
図
関連したドキュメント
にしたいか考える機会が設けられているものである。 「②とさっ子タウン」 （小学校 4 年 生～中学校 3 年生） 、 「④なごや★こども City」 （小学校 5 年生～高校 3 年生）
膵の神経染色標本を検索すると，既に弱拡大で小葉
バックスイングの小さい ことはミートの不安がある からで初心者の時には小さ い。その構えもスマッシュ
Unsteady pulsatile flow of blood through porous medium in an artery has been studied under the influence of periodic body acceleration and slip condition in the presence of
極大な をすべて に替えることで C-Tutte
１ 単元について 【単元観】 本単元では，積極的に「好きなもの」につ
るものの、およそ 1：1 の関係が得られた。冬季には TEOM の値はやや小さくなる傾 向にあった。これは SHARP
なお、保育所についてはもう一つの視点として、横軸を「園児一人あたりの芝生
