リンケージの組合せ論
東京大学情報理工学系研究科
谷川

1

眞一

はじめに

三角形の合同条件の一つに『対応する各辺の長さが等しい２つの三角形は合同である』という事実があります．ここで２つの三角形が合同とは，一方の三角形を合同変換 (平行移動，回転，反転) でもう一方の三角形へ一致させることが可能ということです．この『三角形』を『グラフ』に置き換えた場合に，同じような結論を導くことが可能だろうか？ という問いが，本稿の主題です．例えば図 1(a) のグラフの場合，各辺の長さが決まると全体の形状が一意に決まります．一方で図 1の (b) と (c) は，同じグラフかつ対応する辺の長さが等しいにも関わらず，全体の形状は合同になっていません．

(c)
(a)

(b)

図 1: (a) 大域的に剛な例．(b)(c) 大域的に剛でない例．
グラフが密な場合 (辺の本数が頂点の個数に対し十分に多い場合) は，三角形の合同条件を繰り返し適用することで，多少辺がない箇所があっても，図形の合同性が言えそうです．一方，図 2(a) のような疎なグラフ (辺の本数が頂点数に比べ少ないグラフ) では，合同ではない描画が多数存在します．しかし，図 2(b) も比較的疎なグラフですが，実は辺長によって図形の形状が一意に決定されます．
それでは，『各辺の辺長が定まれば，グラフ全体の形状が一意に定まる』(1)という性質を有するグラフを完全に理解することは可能でしょうか? このような問の一つの具体例として，センサーネットワークの位置同定問題が挙げられます．
センサーネットワーク位置同定問題は，一部のセンサー間の距離とアンカーと呼ばれるいくつかの点の座標が分かっている状況で，各センサーの座標を計算する問題です．例えば，図 3 のように平面上に幾つかのセンサーが点在する状況を考え

(a)

(b)

図 2: (a) 剛でない例．(b)(c) 大域的に剛な例．

図 3: センサーネットワーク位置同定の例.
ます. 各円はセンサーから距離が計測可能な範囲を表しており，円内に存在する別のセンサーへの距離が計測可能であるとします．更にアンカーと呼ばれる四角点の座標値がわかっている際，アンカーの座標値と計測可能なセンサー間の距離情報から，全センサーの座標値を計算する問題がセンサーネットワーク位置同定問
題です．ここで正確な座標値が得られるための前提条件として，解の一意性を保証する必要がありますが，これはまさにネットワークが性質 (1) を有しているかということに対応しています．さらに，解が一意でない場合にどの程度センサーの半径を広げる必要があるか，などの問に厳密に答えるためには，性質 (1) を有する
グラフに対する知見が必要となります．
性質 (1) をもう少し厳密に定義したいと思います．頂点集合 V (G) と辺集合 E(G)の有限のグラフ G が d 次元ユークリッド空間内に描画されているとし，各頂点
v ∈ V (G) の座標を pv ∈ Rd と表すことにします．このとき xv ∈ Rd (v ∈ V (G))
を変数とする方程式系∥xu − xv ∥2 = ∥pu − pv ∥2(uv ∈ E(G))(2)の任意の解 xv (v ∈ V (G)) が，pv (v ∈ V (G)) の等長写像の像であるかを判定することが，性質 (1) を判定することに当たります．正確には，性質 (1) は写像 p : V → Rd
によって空間内に描画されたグラフの性質，つまり G と p の組の性質であります．
このようなグラフ G = (V, E) と写像 p : V → Rd の組 (G, p) をフレームワーク (骨組み) と呼び，(G, p) が性質 (1) を満たすとき (つまり (2) の解が，等長写像の差異を除いて一意のとき)，フレームワーク (G, p) は大域的に剛といいます．
この大域的に剛という用語は，この概念の局所版が構造力学で考えられている剛性に対応していることに由来します．つまり上記の方程式系 (2) において，x の取れる範囲を p の近傍に制限し，近傍内での解の唯一性が成り立つならば，(G, p) は(局所的に) 剛と呼びます．例えば，図 1(b)(c) は，大域的に剛ではないが，局所的に剛な例です．一方，図 2(a) は局所的にも剛ではありません．(辺長を保持して，くねくね変形できます．)
硬い棒材の各端点がピン接合されてできた模型はリンケージとよばれ，非自明な変形 (合同ではない模型への連続的な変形) が可能なリンケージを設計すること
は，機械工学における基本的な問の一つであります．またフレームワークは，構
造力学における (部材断面を無視して単純化した) トラス構造をモデル化しており，局所的な剛性は構造物の剛性を解析する上で最も自然な概念の１つであります．
この大域的/局所的な剛性を有するグラフを理解したい，というのが本稿の主題でありますが，これらの性質は，フレームワーク (G, p) の幾何的な情報 p に大きく依存します．例えば，図 4 のような片側 4 頂点の完全二部グラフ K4,4 を考えてみましょう．

図 4: 完全二部グラフ K4,4 のフレームワーク．
この K4,4 の頂点をランダムに平面上に配置した場合，フレームワークは局所的に剛であることが確認できます．(後述する定理 4.2 より．) 一方，全ての頂点が図のように楕円上に存在する場合，連続的にフレームワークが変形可能であることが知られています．この K4,4 の駆動可能 2 次元フレームワークは Dixon 機構やBottema 機構として知られており，フレームワークやリンケージ研究ではこのような珍しい機構を探索・解析することが一つの重要な研究目標であります．しかし本稿では，このような特殊な例を探究する話題ではなく，一般的な (generic な)振る舞いを捉える理論を紹介します．図 4 のような珍しい機構を探求する話題は我々の直感を裏切ることを目標とした研究なのに対し，本稿で紹介する話題は我々の直感を精密化するための研究と考えられます．

図 5: 一次元フレームワークの変形．

2

一次元の場合まずはウォームアップとして，一次元フレームワークを考えてみましょう．もしグラフが図 5 のように非連結であれば，一方の連結成分をスライドさせることで辺長を保持しつつ合同でないフレームワークを作成可能です．つまり図 5 のフレームワークは剛ではありません．一方で，グラフが連結ならば帰納的に局所剛性を示すことができます．つまり以下が成立します．
定理 2.1. 一次元フレームワーク (G, p) が局所的に剛であるための必要十分条件はG が連結であることである．
それでは，一次元フレームワーク (G, p) の大域的剛性も，定理 2.1 のような簡潔な特徴づけが可能でしょうか? 実は，答えは (計算という意味において)No であり，すでに一次元空間において大域剛性を理解するのは難しい問題であります．具体的には，以下の事実が成り立ちます．
定理 2.2. 一次元大域剛性判定問題 (与えられた一次元フレームワークの大域剛性を判定する問題) は NP 困難問題である．
この定理は，以下のように証明できます．まず分割問題とよばれる問題を考えます．分割問題では，与えられた n 個の自然数 a1 , . . . , an を２つの集合に分割することを考えます．その際，各集合内の整数の値の和が等しくなるような二分割があれば Yes を，なければ No を解答するという計算問題です．非常に単純な問題ですが，分割問題は NP 完全であることが知られています．1 よってここでは分割問
題を一次元大域剛性判定問題に多項式時間帰着させることで，定理 2.2 の証明とします．
分割問題の任意の入力として，n 個の自然数 a1 , . . . , an が与えれたとします．頂点集合 V = {1, . . . , n + 2} の閉路グラフを G とし，各頂点 v ∈ V の直線への写像
p:V →Rを∑v
(v = 1, . . . , n)∑i=1 avv
p(v) =
a /2 (v = n + 1)
 i=1 v0(v = n + 2)と定めます．このように定めた (G, p) に対し，(G, p) が大域的に剛であることと，元の分割問題の解が No であることが等価であることが確認できます．よって (G, p)の大域剛性を判定することで，元の分割問題の解が判定でき，大域剛性判定問題に1
分割問題は，Karp の 21NP 完全問題のうちの一つであり，最も初めに困難性が証明された組合
せ問題のうちの一つであります．

図 6: 一次元フレームワークに切断点が存在する場合，切断点を起点にフレームワークの片側を折り返すことで非合同なフレームワークが得られる．
対する多項式時間アルゴリズムが存在すれば，分割問題に対する多項式時間アル
ゴリズムも存在してしまうことがわかります．
定理 2.2 から，フレームワークの大域剛性を簡潔に特徴づけることは (P=NP でない限り) 不可能ということがわかります．しかし実のところ，定理 2.2 の難しさ
は，座標値 p の数値的な”偶然性”に起因しており，各グラフ G の一般的振る舞い
は簡潔に理解できることが知られています．例えば，分割問題において，入力が十分大きな範囲内の自然数から一様ランダムに生成された場合，問題の解は高確率で No であり，上記の証明における閉路フレームワーク (G, p) も高確率で大域剛であります．
では一次元フレームワークの大域剛性に，本質的に関わる組合せ的性質とはなんでしょうか? 例えば，グラフ G に切断点が存在する場合 (図 6)，その切断点を起点にフレームワークの片側を折り返すことで，辺長を保持しながら合同ではないフレームワークが得られます．つまり，グラフ G 内に切断点が存在する場合は，
フレームワーク (G, p) は大域剛にはならないというわけです．実は，一次元大域剛性の一般的な性質は，この切断点の存在性で特徴づけられます．
定理 2.3. 点配置 p が一般的 2 な一次元フレームワーク (G, p) において，(G, p) が大域的に剛である必要十分条件は，G 内に切断点が存在しないことである．
一般に，高々 k − 1 個の点を取り除いて未だ連結性が保たれるグラフのことを k
連結グラフと呼びます．この言葉を用いて上記の定義を言い換えると，一般的な一次元フレームワーク (G, p) が大域的剛である必要十分条件は G が 2 連結である
こと，となります．
グラフの k 連結性は，最大流問題に対するアルゴリズムなどを利用することで効率的に判定可能であることが知られています．

グラフの剛性や自由度

3

定理 2.1 では，一次元フレームワークの局所的剛性が連結性によって特徴づけらることを紹介しました．しかし二次元以上の場合は，状況は遥かに複雑になります．まず図 4 に例示したとおり，二次元フレームワーク (G, p) の局所的剛性は p に依存します．実際，二次元フレームワークの局所的剛性の判定問題は NP 困難であることが知られおり，定理 2.1 のような簡潔な特徴づけを二次元以上で展開するこ2

フレームワーク (G, p) の点配置 p が一般的とは，頂点の座標値の集合が有理数体上で代数的に独立と定義します．定理 2.3 は，より弱い仮定でも成立しますが，以降の議論を簡単にするためこ
こでは一般性の仮定を利用したいと思います．

とは難しいと考えられています．よって一次元大域剛性の場合と同様に，配置 p が一般的なフレームワークに着目し，その組合せ的性質を探りたいと思います．

3.1

剛性と無限小剛性

ここではまずフレームワークの剛性解析において中心的な役割を果たす無限小
剛性の概念を導入します．構造力学などの工学分野では，式 (2) のような二次方程式系を直接解析するのではなく，剛性の一次近似の概念である無限小剛性を解析するのが通常であります．頂点数 n，辺数 m のグラフ G = (V, E) に対する剛性写
像 fG : Rdn → Rm を

fG (p) = (. . . , ∥pi − pj ∥2 , . . . , ) ∈ Rmと定めます．つまり fG は (G, p) の辺長の 2 乗のリストを返します．このときフ−1
レームワーク (G, p) が剛であるとは，p が fG
(fG (p))/E(d) の孤立点であることと等価であります．ここで E(d) は d 次元ユークリッド空間の等長写像の集合を表します．
この剛性写像の点 p でのヤコビ行列 Dp fG ∈ Rm×dn を (G, p) の剛性行列とよび()ます．d 次元ユークリッド空間での回転運動の自由度は d2 ，平行移動の自由度は( )d であることから，E(d) の次元は d+1
であり，
2
(
)
d+1
rank Dp fG ≤ dn −2が常に成立します．フレームワーク (G, p) が無限小剛とは，()
d+1
rank Dp fG = dn −2が成立することと定義します 3 ．定義より，無限小剛性は剛性行列の階数を計算することで判定可能であり，無限小剛性は剛性の十分条件であることが知られているため，フレームワークの剛性を解析したい場合は，まず無限小剛性を確認することが定石であります．

3.2

自己応力

フレームワーク (G, p) の剛性行列 Dp fG の転置行列の解は，構造力学で利用される軸応力の概念に対応しています．つまり ω : E(G) → R に対し，ω ⊤ Dp fG = 0
を書き下すと∑ω(uv)(pu − pv ) = 0(u ∈ V (G))(3)
v:uv∈E(G)フレームワークの点集合のアフィン次元が d − 2 以下の場合，この定義は正確ではないが，簡単のため本項では常に点集合のアフィン次元が d と仮定しておく．
3

となり，各 ω(uv)(pu − pv ) を 2 点 u, v 間の棒材が点 u に作用する内力と考えると，
式 (3) は点 u での力の釣合条件を表していることがわかります．つまり無限小剛性
は，構造力学における静的な安定性の概念に対応していることがわかります．このような背景から，(3) を満たす ω : E(G) → R を (G, p) の自己応力と呼びます．
実は，この自己応力の概念は，局所的な剛性だけでなく大域的な剛性の解析においても重要な役割を果たします．
ω をグラフ G の重みと考えると，自己応力条件は p : V (G) → Rd が離散調和関数であることと等価であります．しかし調和関数の文脈とは異なり，ここでは ω は
正値とは限らない点が重要です．

3.3

グラフの剛性2.2 節で述べたように，微小剛性は効率的に判定可能な剛性の十分条件ですが，一般に必要とは限りません．しかしながら p が一般的な配置の場合，p は fG の特−1
異点ではなく，陰関数定理から Dp fG の階数によって p が fG
(fG (p))/E(d) の孤立点であるかを確認できます．つまり点配置 p の一般性の仮定のもと，無限小剛性と剛性の概念は一致し，以下の代数的特徴づけが成立します．
命題 3.1 (Asimow-Roth [1]). 頂点数 n ≥ d + 1 の一般的な d 次元フレームワーク( )(G, p) が剛であるための必要十分条件は rank Dp fG = dn − d+1が成立すること
2である．
このことから一般性の仮定のもと，フレームワーク (G, p) の剛性は p に依存しないグラフ G の性質であることがわかり，(任意の) 一般的 d 次元フレームワーク(G, p) の剛性をグラフ G の d 次元剛性として定義することができます [1]．より一
般に，
(
)
d+1
dn −
− Dp fG2をグラフ G の (d 次元) 自由度と定義すると，G の自由度は G をグラフとする d 次
元リンケージやトラス構造の一般的な自由度を表していると考えられます．

4

剛性の組合せ的特徴づけ

前節では，フレームワークやリンケージの一般的な静力学的性質を捉える概念としてグラフの剛性や自由度を定義しました．これらはグラフの性質であることから，剛なグラフや自由度 k のグラフを簡潔な組合せ的条件で特徴づけできるかという問いが自然に考えられます．例えば，1 次元フレームワークの場合，定理 2.1
より，グラフ G が 1 次元 k 自由度である必要十分条件は，G の連結成分数が k − 1
であることがわかります．このような組合せ的特徴づけを高次元剛性に対し導出することが，この節の目標であります．

4.1

Maxwell の条件

d 次元空間において剛なグラフ G を考えます．G からどの辺を取り除いても剛でなくなるとき，G は極少剛なグラフといいます．どの剛グラフも極少剛な全域部分グラフを有することから，極少剛なグラフを理解できれば剛なグラフも理解できます．よってここでは極少剛なグラフの特徴づけを導くことを目標とします．
フレームワークの無限小剛性とグラフ理論的性質の関係に関して，最も基本的な関係式を最初に指摘したのは James Clerk Maxwell [11] だと言われています．
Maxwell の議論をグラフ剛性の意味で解釈することで以下の条件が得られます．
命題 4.1 (Maxwell の条件). 頂点数 n ≥ d + 1 のグラフ G が d 次元空間において極少剛ならば，以下が成立する．
( )• |E(G)| = dn − d+1
2 ;• 任意の G の部分グラフ H に対し，|V (H)| ≥ d ならば |E(H)| ≤ d|V (H)| −
(d+1)
2 .
この命題は，命題 3.1 と単純な線形代数的議論で証明可能ですが，ここでは条件
式の直感を解説したいと思います．d 次元空間において，各頂点の自由度は d であり，n 頂点合計で dn の自由度があります．辺を一つ追加することで高々 1 の自由度を減らすことができます．また剛なグラフであっても，回転や平行移動などの( )等長写像によって合同な図形にうつることができ，その次元が d+1であります．
2( )よってグラフ G が剛になるためには，少なくとも dn − d+1
本の辺が必要である
2
ことがわかります．また極少剛ならば，冗長な辺が存在しないことから，辺数は丁( )( )度 dn − d+1
本となります．２つ目の条件は，dn − d+1
本の辺をグラフ全体に
2
2
上手く分散させるための条件であり，我々の直感が有している，上手く辺を全体に配置してやれば全体が剛になる，という感覚を定式化したものになります．
この Maxwell の条件ですが，d = 1 の場合はグラフが木であることと等価であります．よって Maxwell の条件から，グラフ H が 1 次元空間で剛となる必要条件
は，H が全域木を有すること，つまり H が連結であることとなります．また定理
2.1 は，命題 4.1 の逆が d = 1 の場合に成立していることを意味しています．

4.2

二次元剛性

まずは例題として，二次元で剛なグラフを帰納的に構成する方法を考えてみま
しょう．まず図 7(a) のような二次元剛なグラフ G を考えます．G に新たな頂点を追加し，サイズが一つ大きな剛グラフを作りたいと考えます．ここで図 7(b) のよ
うに，新たに追加する頂点と G の間を一辺で繋ぐだけではグラフ全体は剛にはなりません．一方で，図 7(c) のように二辺で繋ぐと，得られるグラフは剛となります．この操作は，Henneberg 操作 1 と呼ばれています．つまり

(a)

(b)

(c)

(d)

図 7: (a)(b)(c): 2 次元剛グラフ．(d)2 次元剛ではないグラフ．(a) から (c) がHenneberg 操作 1，(a) から (d) が Henneberg 操作 2．

Hennberg 操作 1: 頂点を追加し，追加した点と元のグラフを二辺で繋ぐという操作を三角形から繰り返していくことで，サイズの大きな極少剛グラフを生成することができます．一方，任意の極少剛グラフが，三角形から Henneberg
操作 1 の繰り返しで構成できるわけではありません．図 7(d) は，2 次元極少剛グ
ラフですが，全ての頂点の次数が 3 以上であるため Henneberg 操作 1 の繰り返しで構成することはできません．このような極少剛グラフを構成する操作として，Henneberg [7] は以下の操作を提案しました．

Hennberg 操作 2: 既存の辺を 1 つ取り除き，新たな頂点を追加し，追加した点と元のグラフの三点を繋ぐ．ただし，三点のうちの二点は，取り除いた辺の両端点とする．
例えば，図 7 の (a) から (d) へ移る操作は Henneberg 操作 2 です．
Henneberg 操作 1 と同様，Henneberg 操作 2 も 2 次元極少剛性を保持することが知られています．(こちらは非自明です．) さらに面白いことに，任意の Maxwell
条件を満たすグラフは，三角形より Hennberg 操作 1 と Henneberg 操作 2 の繰返
しで構成可能であることが証明できます．つまり 2 次元剛性に対し，以下の組合せ的特徴づけが成立します．
定理 4.2 (Pollaczek-Geiringer [12], Laman [10]). グラフ G に対し，以下が等価．

(i) G が 2 次元極少剛．
(ii) G が d = 2 に対する Maxwell 条件を満たす．つまり以下が成立する．
• |E(G)| = 2|V (G)| − 3;
• G の任意の部分グラフ H に対し，|V (H)| ≥ 2 ならば |E(H)| ≤ 2|V (H)|−3.
(iii) G は三角形より，Henneberg 操作 1 と Henneberg 操作 2 の繰返しで構成可能．
例えば図 7(d) のグラフは，図 8 のように三角形から Henneberg 操作の繰り返しで構成できることから，極少剛であることがわかります．また任意の 2 次元極少剛なグラフに対して，このような Henneberg 操作列が存在します．

図 8: Henneberg 操作列．

4.3

三次元剛性

三次元の場合も命題 4.1 の逆が成り立つことを期待してしまいますが，Maxwell
条件は剛性の十分条件とはならず，三次元剛性の簡潔な組合せ的特徴づけは未だ知られていません．定理 4.2 の三次元版を示すことは，長年未解決な難問であります．
2 次元剛性の場合，定理 4.2 を利用することで，G が 6 連結ならば剛であることが知られています [13]．この事実は，各節点が十分な本数の棒材に繋がっていれ
ば，トラス構造やリンケージは堅いという我々の直感を厳密に証明したものです．
Lovász-Yemini [13] は，同様な事実が任意の次元で成り立つ，つまりある f : N → N
が存在し，G が f (d) 連結ならば G は d 次元剛であると予想しました．この予想は，三次元においても未解決であり，我々の直感が 3 次元において常に正しいかはわ
かっておりません．
三次元剛性の特徴づけは難しい問題ですが，グラフの族を限定する事でいくつかの部分的成果が知られています．ここでは二乗グラフの例を紹介したいと思います．本稿の導入で，辺の等長性に関する三角形の合同条件に触れました．皆さんご存知のとおり，合同条件には他に二つあり，ここでは『二辺とその間の角がそれぞれ等しければ合同』という条件をグラフへ拡張することを考えます．つまり d次元フレームワーク (G, p) に対し，各辺の長さと二辺に挟まれる角の角度を一定に保ちながら (G, p) を非合同な図形へ変形可能かを判定したいということです．
このような例は，実はタンパク質の挙動解析などの応用分野において実在する話題であります．実際，分子の挙動を解析する際，最も単純なモデルとして共有結合のみを考慮した場合でも，２つの隣接する共有結合は一定の角度を有するため，
通常の 2 点間の距離の制約に加え，角度制約を有するシステムの自由度を計算する必要があります．
しかしながら実は各角度制約は点間の距離制約に置き換えることができます．例
えば原子 i と j および j と k 間が共有結合で結ばれているとき，線分 ij と線分 jk
間の角度制約を i, k 間の距離制約に置き換えても (三角形の合同条件より) 等価なシステムが得られます．よって結局は距離制約のみのシステムに帰着可能で，さらに結果として得られるグラフは特殊な構造を有します．つまり分子の各原子を頂点と各共有結合を辺として得られるグラフ G に対し，角度制約を距離制約に置き換えて得られるグラフは，G の二乗グラフ G2 と呼ばれるものになります．ここで G2 = (V (G), E(G) ∪ {ik : ∃j ∈ V (G), ij, jk ∈ E(G)})．(図 9)．
実は G2 の三次元剛性に対しては簡潔な特徴づけが知られています．

(a)

(b)

図 9: (a) 分子構造をモデル化したグラフと (b) 対応する二乗グラフ．
定理 4.3 (Katoh-Tanigawa [9]). グラフ G 内に頂点次数が 1 以下の頂点は存在しないとする．このとき G2 が三次元剛である必要十分条件は 5G が 6 つの辺素な全域木を有することである．ここで 5G とは G の各辺を 5 本の平行辺に置き換えて得られる多重グラフである．
グラフ内に辺素全域木を詰め込む問題はグラフ理論や組合せ最適化における古典的話題であり，定理 4.3 の条件を確認するための高速アルゴリズムが多数提案され，タンパク質の力学的性質の解析に利用されています．

5

大域剛性の組合せ的特徴づけ

5.1

一般大域剛性判定問題

ここでは前節の局所剛性理論に対応する大域剛性理論を解説します．剛性写像
fG に対し，局所剛性は fG−1 (fG (p))/E(d) が孤立点であるかを判定する問題であり，p が一般的な場合は p でのヤコビ行列 Dp fG の階数を見ることで判定できました．
−1
一方，大域剛性は fG(fG (p))/E(d) が 1 点のみで構成されているかを問う問題であり，p が一般的であってもかなり非自明な問いとなります．
一次元の場合は一般性の仮定のもとで大域剛性が簡潔に特徴づけられることを定理 2.3 で紹介しました．このような簡潔な特徴づけが二次元以上でも可能か，特に前節の定理 4.2 に対応する定理を大域剛性に対し導けるか，という問いがこの文脈における 2000 年代の中心的話題であります．その進展の柱となったのが，Connellyによる一般大域剛性予想です．命題 3.1 に示した通り，一般的フレームワークの剛性は p の座標値を不定元にもつ剛性行列の階数によって特徴づけられます．このことから，一般的点配置において剛性はグラフのみに依存することがわかります．
Connelly は同様に，一般的な d 次元フレームワークの大域剛性はそのグラフのみに依存すると予想し，予想の解決に向け自己応力を利用した証明プログラムを提案しました [4]．特にグラフラプラシアンを用いた大域剛性の十分条件を示し，その逆が成り立つことを予想しました．
頂点数 n のグラフ G と辺重み ω : E(G) → R に対し，そのラプラシアン Lω と

は大きさ n の対称行列で

∑ k:ik∈E(G) ω(ik) (i = j)Lω [i, j] = −ω(ij)(i ≠ j, ij ∈ E(G))



0
(i =
̸ j, ij ∈/ E(G))と定義されます．d 次元フレームワーク (G, p) の自己応力 ω に対し，そのラプラシ
アン Lω を考えると，力の釣合条件 (3) から

dim ker Lω ≥ d + 1
が導かれます [3]．この下限を達成する自己応力の存在性によって大域剛性が特徴づけられることを Connelly は予想し，その後 2010 年に Gortler-Healy-Thurston [5]によって肯定的な証明が与えられました．
定理 5.1 (Gortler-Healy-Thurston [5]). d 次元一般的フレームワーク (G, p) が大域的に剛である必要十分条件は G が完全グラフまたは dim ker Lω = d + 1 となる自己応力 ω が存在することである．
このことから剛性の場合と同様に，一般性の仮定のもとフレームワークの大域剛性はそのグラフのみに依存し，グラフ G の d 次元大域剛性を任意の d 次元一般
的フレームワーク (G, p) の大域剛性として定義することが可能になりました．

5.2

組合せ的特徴づけ

大域剛性の組合せ的特徴づけの鍵となる最初の成果は Connelly 予想より古く，
Hendrickson によって以下の必要条件が示されました．
定理 5.2 (Hendrickson [6]). (G, p) を d + 1 頂点以上の一般的な d 次元フレーム
ワークとする．(G, p) が大域的に剛ならば，G が完全グラフまたは以下の (i)(ii) が成立する:(i) G が d + 1 点連結;(ii) 各 e ∈ E(G) に対し，G − e が局所的に剛．

d = 1 の場合，Hendrickson の定理の条件は二連結性と等価であり，Hendricksonの定理の逆が成立することがわかります．Connelly は上記の一般大域剛性予想の
d = 2 の場合の証明プログラムとして，Hendrickson の定理の逆をグラフ理論的議論によって証明するアイデアを提案しました．
Connelly はまず Henneberg 操作 2 が大域剛性を保つこと，つまり G が二次元大域的に剛ならば Henneberg 操作 2 で生成される G′ も二次元大域的に剛であることを証明しました．さらに Connelly は，Hendrickson の定理の条件 (i)(ii) を満た

すグラフは四頂点の完全グラフ K4 から Henneberg 操作 2 と辺の追加の操作を繰
り返し適用することで常に生成可能と予想しました．例えば，図 2(b) のグラフは，
K4 から Henneberg 操作 2 の繰り返しで生成可能なため大域的に剛であることが確認できます．Connelly の予想は，Berg-Jordán [2] によって重要な特殊ケースが解決され，その後 Jackson-Jordán [8] によって完全に解決されました．これらの成果
から Hendrickson の定理の逆が d = 2 においても成り立つことが示されました．
定理 5.3 (Jackson-Jordán [8]). グラフ G に対し，以下が同値．

(i) G は二次元大域剛．
(ii) G は d = 2 の場合の Hendrickson 条件を満たす．つまり以下が成立する．
• G が三連結;• 各 e ∈ E(G) に対し，G − e が (局所的に) 剛．
(iii) G は，四頂点の完全グラフ K4 から Henneberg 操作 2 と辺の追加操作を繰り返しことで構成可能.
つまりこの定理は，導入で提示した性質 (1) を有する任意のグラフが K4 から
Henneberg 操作 2 と辺の追加の操作を繰り返しで得られることを示しています．
剛性の場合と同様に，三次元以上の大域的剛グラフの特徴づけは重要な未解決問題であります．Connelly によって K5,5 は Hendrickson の必要条件を満たすが三次元大域的剛ではないことが指摘され，その後も Hendrickson の条件を満たす大域的剛でないグラフが多数報告されています．現在のところ，三次元以上の大域的剛グラフの組合せ的特徴づけは予想すら存在しない状況であります．

参考文献[1] Asimow , L. and Roth, R., The rigidity of graphs, Transactions of the American Mathematical Society, 245 (1978), 279–289.
[2] Berg, A. R. and Jordán, T., A proof of Connelly s conjecture on 3-connectedcircuits of the rigidity matroid, Journal Combinatorial Theory Series B, 88(2003), 77–97.
[3] Connelly, R., Rigidity and energy, Inventiones Mathematicae, 66 (1982),
11–33.
[4] Connelly, R., Generic global rigidity, Discrete and Computational Geometry,
33 (2005), 549–563.

[5] Gortler, S, Healy, A, and Thurston, D., Characterizing generic global rigidity, American Journal of Mathematics, 132 (2010), 897–939.
[6] Hendrickson, B., Conditions for unique graph realizations, SIAM Journal
on Computing, 21 (1992), 65–84.
[7] Henneberg, L.: Die Graphische Statik der Starren Systeme, Leipzig (1911),
Johnson reprint (1970).
[8] Jackson, B. and Jordán, T., Connected rigidity matroids and unique realizations of graphs, Journal of Combinatorial Theory Series B, 94 (2005),
1–29.
[9] Katoh, N, and Tanigawa, S., A proof of the molecular conjecture, Discrete
and Computational Geometry, 45 (2011), 647–700.
[10] Laman, G., On graphs and rigidity of plane skeletal structures, Journal ofEngineering Mathematics, 4 (1970), 331–340.
[11] Maxwell, J. C., On the calculation of the equilibrium and stiﬀness of frames,
Philos. Mag., 27 (1864) 294–299.
[12] Pollaczek-Geiringer, H., Über die Gliederung ebener Fachwerke, Zeitschriftfür Angewandte Mathematik und Mechanik, 7 ( 1927), 58–72.
[13] Lovász, L. and Yemini, Y., On generic rigidity in the plane, SIAM Journal
on Algebraic Discrete Methods, 3 (1982), 91–98.