平成24年度(第34回)数学入門公開講座テキスト(京都大学数理解析研究所，平成24年7月30日～8月2日開催)

グラフの剛性とマトロイド
谷川眞一

はじめに
伸び縮みしない m 本の棒部材と n 個のジョイントで構成されたフレームワークが剛であるためには m ≥ 2n − 3 が必要である．この条件は J. C. Maxwell の時代から知られている古典的事実であるが，フレームワークの剛性がそのグラフ構造 (棒とジョイントの接続関係) に大きく依存している事を示唆している．実際，殆ど全てのジョイント配置においてフレームワークの剛性は対応するグラフ上の簡潔な組合せ的性質によって特徴付けされる事が，Maxwell の結果から約 100 年後の 1970 年に Laman [11] によって証明されている．
剛性の組合せ構造の解明は，剛性理論として離散幾何学の一分野を形成している．特に重要な話題として，多面体の剛性と上記のフレームワークの剛性 (グラフの剛性) がある．多面体の剛性に関しては，Euler の多面体剛性の予想から始まり，Cauchy の凸多面体に対する剛性定理の後，非凸な多面体が常に剛であるかは長年未解決であったが，1978 年に Connelly によって柔かな多面体が発見された事によって基本的な課題は解決に至っている．しかしながらグラフの剛性に関して
は，最も基本的問題である 3 次元一般剛性の組合せ的特徴付けの導出が未解決な状態である．
本講義は，一般剛性の特徴付け問題へのアプローチの基礎となる Laman の定理の条件を，マト
ロイド理論や劣モジュラ関数の立場から理解することを目標としている．Laman の定理の条件を一般化することで，計数マトロイドと呼ばれる広いクラスのマトロイドが定義出来る．このマトロイドは剛性の問題だけでなく，その他の離散幾何学の問題や，森分解等のグラフ理論の問題にも現れる重要なマトロイドである．講義ではこれらの話題も適宜紹介し，各問題における組合せ的特徴
付けや代数的特徴付けを解説したい．
剛性理論に関するより詳細な解説は [9, 19] を参照していただきたい．5 節で解説するグラフの再描画問題など，計数マトロイドの離散幾何への応用は [19] が詳しい．マトロイド理論に関しては[16] を，2 節で解説するポリマトロイドの多面体的解釈については [7, 17] を参考にした．3 節で紹介するマトロイド・ポリマトロイド構成法の幾何学的解釈に関しては [2, 14] が詳しい．4 節で紹介
する Laman の定理の証明は Lovász and Yemini [13] によるものである．

1 グラフの剛性
本節では，フレームワークの剛性，無限小剛性，一般剛性を定義し，一般剛性の組合せ的・離散的特徴付けについて解説を行う．
以降，有限集合 E とベクトル空間 W に対し，E から W への写像の集合を W E と書くことにする．また 2E は E の冪集合を表す．R は実数の集合，Z は整数の集合，R+ = {x ∈ R : x ≥ 0}，

Z+ = {x ∈ Z : x ≥ 0} とする．

平成24年度(第34回)数学入門公開講座テキスト(京都大学数理解析研究所，平成24年7月30日～8月2日開催)

1.1 剛性グラフ G = (V, E) と d 次元ユークリッド空間への写像 p : V → Rd のペア (G, p) をフレームワークとよぶ．p : V → Rd はジョイント配置と呼ばれている．議論を簡潔にするため，ここでは|V | ≥ d + 1 かつどの d + 1 点もアフィン独立で縮退していないジョイント配置のみを考える．
各辺の長さを変えないような各ジョイント p の連続的移動をフレームワークの動きといい，特に合同なフレームワークへの動きを自明な動きという．自明な動きのみが可能なフレームワークを剛(rigid) と定め，剛でないフレームワークを柔か (flexible) とよぶ (図 1)．

図 1 平面上で剛なフレームワークと柔かなフレームワーク

数学的には，フレームワークの剛性は以下のように定義される．グラフ G とジョイント配置

p, q ∈ (Rd )V に対し，||p(u) − p(v)||2 = ||q(u) − q(v)||2∀uv ∈ E(1)

ならば p ∼ q と定め，この制約が辺の両端点だけでなく全ての頂点対に対し成立するとき，p ≡ qと書く．フレームワーク (G, p) に対し，Re(G, p) = {q ∈ (Rd )V : q ∼ p} と C(G, p) = {q ∈(Rd )V : q ≡ p} を定める．p から q ∈ C(G, p) への変換は d 次元ユークリッド空間の等長写像へ一意に拡張可能であるため，C(G, p) は等長写像の集合，つまり d 次元ユークリッド群 E(d) と同一視することが出来る．
フレームワーク (G, p) が剛 (rigid) であるとは，p が Re(G, p)/E(d) 内において孤立点となることである．つまりある ε > 0 が存在して，ε 近傍 Nε (p) 内の任意の点 q ∈ Nε (p) において，p ∼ q
ならば p ≡ q が成立つ事である．

Re(G, p) 内の p からのパスを (G, p) の動き (motion) という．特に E(d) 内の p からのパスは自明な動きと呼ばれており，(G, p) が剛であるための必要十分条件は動きが全て自明なことである[1]．

1.2 無限小剛性
剛性を判定する問題は一般に co-NP 困難であることが知られている．そのため，剛性を一次近似した無限小剛性 (infinitesimal rigidity) の概念が有用となる．式 (1) を p について微分し，ṗ : V → Rd に対する線形方程式系⟨p(u) − p(v), ṗ(u) − ṗ(v)⟩ = 0∀uv ∈ E

(2)を得る．式 (2) の解 ṗ : V → Rd を (G, p) の無限小動き (infinitesimal motion) とよぶ．
フレームワークの動きと同様に無限小動きも自明な動きと非自明な動きに分けられる．無限小動
き ṗ : V → Rd がある d × d 歪対称行列 S と t ∈ Rd を用いて ṗ(v) = Sp(v) + t (v ∈ V ) と表現可能なとき，ṗ は自明な無限小動きとよばれる．例えば 2 次元の場合，x 軸方向，y 軸方向への平行平成24年度(第34回)数学入門公開講座テキスト(京都大学数理解析研究所，平成24年7月30日～8月2日開催)

移動および原点周りの回転ベクトル場の線形結合が自明な無限小動きに対応する．特に，無限小動
きの集合は

(d+1)
2

次元線形空間を形成している．可能な無限小動きが全て自明なフレームワークを無限小剛 (infinitesimally rigid) なフレームワークと定める．
線形方程式系 (2) を変数 ṗ に対し行列表現し得られる |E| × d|V | 行列は剛性行列 (rigidity
matrix) とよばれ，その性質は剛性理論において主要な研究対象である．以降，剛性行列を R(G, p)( )と記す．どのようなフレームワークに関しても自明な無限小動きの集合の次元は d+1
であること
2
(d+1)
から，dim ker R(G, p) ≥ 2 である. よって (G, p) が無限小剛であるためには，()
d+1
rank R(G, p) = d|V | −(3)
2
が必要十分条件となる．

1.3 一般剛性
無限小剛性と剛性は一般に異なる性質である．しかしながら，p が一般的 (generic) である場合
は 2 つの性質が一致することが知られている．ここで，p が一般的とは，各ジョイント間に代数的な依存関係がない状態，つまりジョイント座標値の集合が有理数体上で代数的に独立である場合を指す．
定理 1.1 (Asimov and Roth [1]). p が一般的なとき，(3) は (G, p) が剛であるための必要十分条件である．つまり (G, p) が剛であることと (G, p) が無限小剛なことは同値である．

R(G, p) の 各 小 行 列 式 は ジ ョ イ ン ト 座 標 値 の 多 項 式 で あ る こ と か ら ，p が 一 般 的 な ら ば ，rank R(G, p) = max{rank R(G, q) | q ∈ (Rd )V } である. つまり一般的配置ならば剛性行列の階数は p に依らず一定である．一般的配置を仮定した際のフレームワークの剛性は一般剛性(generic rigidity) とよばれ，その性質は G のみに依存する．よって，殆ど全てのジョイント配置は一般的であることから，一般剛性をグラフの剛性として定義しようというのが Asimov and Rothのアイデアである．つまり一般的な p において (G, p) が剛となるグラフ G を剛なグラフ (rigid
graph) と定める．
剛なフレームワーク (G, p) のどの辺を取り除いても剛でなくなるとき，(G, p) は極小に剛とよばれる．(G, p) の極小無限小剛性と G の極小剛性も同様な定義で定まる．

1.4 組合せ的特徴付け
フレームワーク (G, p) が無限小剛であるためには |E| ≥ d|V | −

(d+1)
2

が必要である．この組合

せ的条件は，構造力学や機械工学分野において Maxwell の条件として知られている．無限小剛性の必要十分条件が (3) であることから Maxwell の条件は自明であるが，柔かなフレームワークを目視で判定する場合に非常に有用である．
さらに，任意の d 点以上の部分フレームワーク (G′ , p′ ) に対し，dim ker R(G′ , p′ ) ≥

(d+1)
2

が成

立つことから以下の条件が得られる：定理 1.2 (Maxwell の条件). d 点以上のフレームワーク (G, p) が極小に無限小剛ならば，G =( )(V, E) が以下の計数条件を満たす：|E| = d|V | − d+1
かつ，任意の |V (F )| ≥ d なる F ⊆ E に
2(d+1)
対し |F | ≤ d|V (F )| − 2 . ここで V (F ) は辺集合 F 内の辺の端点集合を表す．
この条件も剛性理論においては Maxwell の条件とよばれている．定理 1.2 の条件はグラフ

G = (V, E) が極小に剛であるための必要条件である．

平成24年度(第34回)数学入門公開講座テキスト(京都大学数理解析研究所，平成24年7月30日～8月2日開催)

(b)

(a)
図2

(a)Maxwell の条件を満たすが柔かなフレームワーク．(矢印は非自明な動きを表す．)(b)Maxwell の条件を満たすが無限小剛ではないフレームワーク．(矢印は非自明な無限小動きを表す．)

Maxwell の条件は極小無限小剛性の組合せ的な必要条件であるが，無限小剛性はジョイント配置に依存しているために，Maxwell の条件は一般に十分ではない．実際，図 2 に見られるように，
Maxwell の条件を満たすが無限小剛や剛でないフレームワークが存在する．しかしながら，ジョイ
ント配置が一般的ならば剛性・無限小剛性はともにグラフの性質であり，組合せ的特徴付けが期待出来る．実際，一次元剛性の場合，フレームワーク (G, p) が剛であるための必要十分条件は G が連結であることであり，この特徴付けは組合せ的である．2 次元剛性の場合，実は Maxwell の条件がグラフの剛性を特徴付ける．
定理 1.3 (Laman の定理 [11]). グラフ G = (V, E) が極小に剛であるための必要十分条件は，

G が以下の計数条件を満たすことである：|E| = 2|V | − 3 かつ非空な任意の F ⊆ E に対し，
|F | ≤ 2|V (F )| − 3.
3 次元剛性の場合，Maxwell の条件は一般的に十分ではない．図 3 にダブルバナナフレームワー
クとよばれる，Maxwell の条件を満たすが一般的に柔かなフレームワークの例を示す．実際，グラフの三次元剛性を組合せ的に特徴付ける問題はこの分野における最も重要な未解決問題であり，3次元一般剛性が決定的に多項式時間で判定可能であるかもまた未解決である．

図3

ダブルバナナフレームワーク

2 マトロイドとポリマトロイドの諸性質
本節ではマトロイドとポリマトロイドの基本性質を解説する．特に，Edmonds [6] によって提案された劣モジュラ関数によって誘導されるマトロイドを，ポリマトロイド多面体の視点から解説する．定理 1.3 の条件 (Laman の条件) を満たすグラフの族は，このようなマトロイドの基集合を形

平成24年度(第34回)数学入門公開講座テキスト(京都大学数理解析研究所，平成24年7月30日～8月2日開催)成している．

2.1 マトロイド
定義 1. 有限集合 E と E の部分集合の族 I のペア (E, I) が，以下の 3 つの公理を満たすとき，(E, I) をマトロイド (matroid) とよぶ：

(I1)
(I2)
(I3)

∅ ∈ I;∀X ⊆ Y ⊆ E, Y ∈ I ⇒ X ∈ I;
∀X, Y ∈ I, |X| < |Y | ⇒ ∃y ∈ Y \ X s.t. X ∪ {y} ∈ I.

I 内の集合を独立集合とよび，極大な独立集合を基とよぶ．各 F ⊆ E の階数とは，F 内の最大独立集合の要素数であり，階数を返す E 上の集合関数 r : 2E → Z を階数関数とよぶ．つまり，r(F ) = max{|I| : I ⊆ F, I ∈ I} (F ⊆ E) である．
例 1 (線形マトロイド). 体 F 上のベクトル空間内の m 個のベクトル v1 , . . . , vm に対し，E ={1, . . . , m}，I = {F ⊆ E : {ve : e ∈ F } は一次独立 }．
例 2 (一様マトロイド). 整数 k に対し，I = {F ⊆ E : |F | ≤ k}．
例 3 (グラフ的マトロイド). 無向グラフ G = (V, E) に対し，I = {F ⊆ E : F は森 }．(F がサイ
クルを含まないとき，森とよぶ．)
例 4 (bicircular マトロイド). 無向グラフ G = (V, E) に対し，I = {F ⊆ E : F は擬似森 }．(Fの各連結成分が高々 1 個のサイクルを含むとき，擬似森と呼ぶ．)
例 5 (横断マトロイド). 頂点集合 V ∪ E と V と E 間を結ぶ辺の集合 I から構成される 2 部グラ
フ G = (V, E; I) に対し，I = {X ⊆ E : X を被覆するマッチングが G に存在 }．(端点を共有していない辺の集合をマッチングと呼ぶ．)
例 6. (一般剛性マトロイド) 剛性行列 R(G, p) の各行は辺に対応していることから，剛性行列の行ベクトルマトロイドを考えることによって E 上のマトロイドが定まる．これを d 次元剛性マトロ
イドという．特に p が一般的である場合は d 次元一般剛性マトロイド Rd (G) とよばれ，これはグラフによって定まる E 上の線形マトロイドである．
定義 1 ではマトロイドを独立集合族の公理系で定めたが，基の集合族が満たす性質等，異なる等
価な公理からマトロイドを定義する事が可能である．その中で，階数関数を用いた定義が今回特に重要となる．
定理 2.1. 以下の条件は，有限集合 E 上の整数値集合関数 r : 2E → Z がマトロイドの階数関数であるための必要十分条件である:

(R0)
(R1)
(R2)
(R3)

r(∅) = 0;∀e ∈ E, r(e) ≤ 1;
∀X ⊆ Y, r(X) ≤ r(Y ) ( 単調性 );∀X, Y ⊆ E, r(X) + r(Y ) ≥ r(X ∪ Y ) + r(X ∩ Y ) ( 劣モジュラ性 ).

つまり，マトロイドとは定理 2.1 の条件を満たす有限集合 E と集合関数 r のペア (E, r) と定義
出来る．この時，I = {F ⊆ E : |F | = r(F )} によって独立集合族が定まる．かなり冗長な表現だが，以下の条件も E が独立集合である条件として |E| = r(E) と同値である:∀F ⊆ E,|F | ≤ r(F ).

(4)平成24年度(第34回)数学入門公開講座テキスト(京都大学数理解析研究所，平成24年7月30日～8月2日開催)

一般に有限集合 E 上の集合関数 f : 2E → R に対し，(R2)，(R3) の条件を満たす f をそれぞれ単調関数，劣モジュラ関数とよぶ．
グラフ G = (V, E) に対する Laman の条件を考える．条件は ∅ ̸= ∀F ⊆ E, |F | ≤ 2|V (F )| − 3
であったことから，集合関数 f2,3 (F ) = 2|V (F )| − 3 (F ⊆ E) に着目しよう．より一般的に，整数 k, l に対し，fk,l : 2E → Z を

fk,l (F ) = k|V (F )| − l(F ⊆ E)(5)と定める．すると fk,l は単調劣モジュラ関数である．単調性は自明であり，劣モジュラ性は，任意の X, Y ⊆ E に対し，V (X ∪ Y ) = V (X) ∪ V (Y ) かつ V (X ∩ Y ) ⊆ V (X) ∩ V (Y ) であることか
ら従う．よって fk,l は (R2) と (R3) を満たすが，一般に fk,l は (R0) と (R1) を満たさないためマ
トロイドの階数関数ではない．fk,l 自体は階数関数ではないが，これから解説を行う Edmonds の定理 (定理 2.5) によって，fk,l も自然にマトロイドを誘導する．

2.2 ポリマトロイド
マトロイドの階数関数の自然な一般化として，ポリマトロイドが以下のように定義される．
定義 2. 有限集合 E 上の集合関数 f : 2E → R が (R0), (R2), (R3) を満たす時，(E, f ) はポリマ
トロイド (polymatroid) と呼ばれる．
マトロイド (E, r) はポリマトロイドである．またポリマトロイド (E, f ) が整数値かつ f (e) ≤1 (e ∈ E) のとき，(E, f ) はマトロイドである．
例 1 (線形ポリマトロイド). 体 F 上のベクトル空間 W 内の m 個の線形部分空間 A1 , . . . , Am ⊆ W
に対し，E = {1, . . . , m}，f (F ) = dim⟨Ae : e ∈ F ⟩ と各 F ⊆ E に対し定める．ここで ⟨·⟩ は線形包を表す．このとき (E, f ) はポリマトロイドである．
例 2 ((k, 0)-疎性). グラフ G = (V, E) と自然数 k に対し，(E, fk,0 ) はポリマトロイドである．
例 3 (ポリマトロイドの和). 台集合が共通のポリマトロイド (E, f1 ) と (E, f2 ) に対し，(E, f1 +f2 )はポリマトロイドである．
ポリマトロイドはマトロイドの階数関数を自然に一般化することで定義されたが，マトロイドの独立集合がポリマトロイドにおいて何に対応するかは明白でない．この点は，以下のポリマトロイ
ド多面体 P (f ) を導入することによって明らかとなる:

ただし x(F ) =∑P (f ) = {x ∈ RE
+ : ∀F ⊆ E, x(F ) ≤ f (F )}.

(6)e∈F x(e) とする．
(E, f ) がマトロイド，つまり f (e) ≤ 1 (e ∈ E) の場合，P (f ) は超立方体 [0, 1]E に含まれている．超立方体内の整数格子点は，E の各部分集合 F の特徴ベクトル χF に対応しており，(4) より F ∈ I である必要十分条件は χF ∈ P (f ) であることがわかる．よって一般のポリマトロイド(E, f ) に対しても P (f ) ∩ ZE の各点が独立集合に対応していると考えることが出来る．

組合せ最適化分野において次の定理は基本的である．
定理 2.2. f が整数値単調劣モジュラ関数ならば，ポリマトロイド多面体 P (f ) は整数多面体である．( つまり各頂点の座標値は整数．)
上記の通り，(E, f ) がマトロイドであるとは P (f ) が超立方体に含まれる場合であった．そこで一般のポリマトロイド多面体 P (f ) を超立方体へ制限することを考える．このとき，制限された多面体もまたポリマトロイド多面体となる：

平成24年度(第34回)数学入門公開講座テキスト(京都大学数理解析研究所，平成24年7月30日～8月2日開催)

定理 2.3. ポリマトロイド (E, f ) に対し，

f 1 (X) = min{|X \ Z| + f (Z) : Z ⊆ X}

(X ⊆ E)(7)

とおく．このとき，以下が成立つ．

(i)
(ii)
(iii)

f 1 は劣モジュラ．
P (f 1 ) = P (f ) ∩ [0, 1]E ．
f が整数値ならば (E, f 1 ) はマトロイドである．

証明. 任意の X ⊆ E に対し，(7) の最小値を与える部分集合を ZX ⊆ X と書くことにする．

(i). 任意の X, Y ⊆ E に対し，|X \ZX |+|Y \ZY | = |(X ∪Y )\(ZX ∪ZY )|+|(X ∩Y )\(ZX ∩ZY )|が成立つ．この関係式と f の劣モジュラ性から，f 1 (X) + f 1 (Y ) = |X \ ZX | + f (ZX ) + |Y \ZY | + f (ZY ) ≥ |(X ∪ Y ) \ (ZX ∪ ZY )| + f (ZX ∪ ZY ) + |(X ∩ Y ) \ (ZX ∩ ZY )| + f (ZX ∩ ZY ) ≥f 1 (X ∪ Y ) + f 1 (X ∩ Y ) となる．
(ii). 任意の X ⊆ E に対し，f 1 (X) ≤ min{f (X), |X|} であることから，P (f 1 ) ⊆ P (f ) ∩ [0, 1]Eである．逆に，x ∈ P (f ) ∩ [0, 1]E と F ⊆ E に対し，x(F ) = x(F \ ZF ) + x(ZF ) ≤ |F \ ZF | +f (ZF ) = f 1 (F ) となり，x ∈ P (f 1 ) が得られる．
(iii) は (i)(ii) から従う．
例 3 で述べたように (E, fk,0 ) はポリマトロイドであるが，一般にマトロイドではない．しかしながら定理 2.3 より，|F | ≤ fk,0 (F )(F ⊆ E)は，あるマトロイドにおいて E が独立であるための必要十分条件であることがわかる．k = 1 の場合，実は例 4 に挙げた bicircular マトロイドの独立性条件となっている．l > 0 の場合 (E, fk,l )は (R0) を満たさないためポリマトロイドではないが，以下の定理によってポリマトロイドとの関係が明らかにされる．
定理 2.4. 劣モジュラ関数 f : 2E → R に対し，

fˆ(F ) = min{∑f (X) : F の非空部分集合への分割 P}(F ⊆ E)(8)X∈Pと定める．ただし fˆ(∅) = 0 とする．このとき，fˆ は劣モジュラ関数である．
証明. 幾つかの用語を導入する．E の部分集合 X, Y が真に交差しているとは，X \Y ̸= ∅, Y \X ̸=∑∅ かつ X ∩ Y ̸= ∅ が成立つ場合をいう．E の多重部分集合族 F に対し，fˆ(F) = X∈F f (X) と定める．多重部分集合族 F に対し，ℓ(F) を F 内の部分集合の要素数を小さい順に並べた整数列と定め，2 つの多重部分集合族 F, F’ に対し，ℓ(F) が辞書式順の比較で ℓ(F ′ ) より小さいとき，ℓ(F) < ℓ(F ′ ) と記す．
これから X, Y ⊆ E に対する fˆ の劣モジュラ不等式を示す．X = ∅ または Y = ∅ の場合は自明であるので，X ̸= ∅ かつ Y ̸= ∅ とする．{X1 , . . . , Xk } と {Y1 , . . . , Yl } をそれぞれ fˆ(X) と fˆ(Y )を与える X と Y の分割とする．E の多重部分集合族 F を F = {X1 , . . . , Xk } ∪ {Y1 , . . . , Yl } で定める．(つまり Xi = Yj であっても Xi と Yj は異なる要素と考える．)
F 内の部分集合 A と B が真に交差しているとき，A と B を削除し，A ∩ B と A ∪ B を追加することで新たな多重集合族 F ′ を作る．この操作を交差解消と呼ぶ．交差解消によって得られたF ′ に対し，以下の 3 点が成立する:(1) 各 e ∈ E に対し，e を含む F 内の部分集合の個数と e を含む F ′ 内の部分集合の個数は等
しい．

平成24年度(第34回)数学入門公開講座テキスト(京都大学数理解析研究所，平成24年7月30日～8月2日開催)(2) fˆ(F) ≥ fˆ(F ′ ).
(3) ℓ(F) > ℓ(F ′ ).
性質 (1) は，F ′ の構成法より自明である．性質 (2) は，fˆ(F) − fˆ(F ′ ) = f (A) + f (B) − f (A ∪B) − f (A ∩ B) であるから，f の劣モジュラ性より従う．性質 (3) は，|X ∩ Y | < min{|X|, |Y |}より従う．

X と Y の分割から定まった F に対し，真に交差しているペアがなくなるまで交差解消を繰り返し行う．交差解消の性質 (3) より，有限回の交差解消で真に交差しているペアのない多重部分集合族 F ′′ が得られる．この時，性質 (2) より fˆ(F) ≥ fˆ(F ′′ ) である．さらに真に交差しているペアがないことと性質 (1) より，F ′′ 内において包含関係に対し極大な部分集合の族は X ∪ Y の分割であり，F ′′ 内の残りの部分集合は X ∩ Y の分割を形成している．よってfˆ(X) + fˆ(Y ) = fˆ(F) ≥ fˆ(F ′′ ) ≥ fˆ(X ∪ Y ) + fˆ(X ∩ Y )となり，fˆ が劣モジュラ関数であることが示された．
上記の fˆ は，f の Dilworth 打切りとよばれている．単調劣モジュラ関数 f : E → R に対し，多面体 P ′ (f ) を導入する：

P ′ (f ) = {x ∈ RE
+ : ∅ ̸= ∀F ⊆ E, x(F ) ≤ f (F )}.

(9)P ′ (f ) は F = ∅ に対する条件を無視しているため，一般にポリマトロイド多面体になるとは限らないが，f (e) ≥ 0 (e ∈ E) のとき，fˆ に対するポリマトロイド多面体と一致している．つまりP ′ (f ) = P (fˆ)

(10)

が容易に確認出来る．結果として以下が得られる．
定理 2.5 (Edmonds [6]). 有限集合 E と単調劣モジュラ関数 f : 2E → Z に対し，If = {I ⊆E : ∅ ̸= ∀X ⊆ I, |X| ≤ f (X)} と定める. このとき，(E, If ) はマトロイドである．
証明. E ′ = {e ∈ E : f (e) ≥ 0} とする．定義より If 内の各集合は E ′ の要素から構成されている
ため，E ′ = E の場合に対し証明すれば十分である．
定理 2.4 より，fˆ は単調劣モジュラ関数で fˆ(∅) = 0 あるため，(E, fˆ) はポリマトロイドである．
よって定理 2.3 より，(E, fˆ1 ) はマトロイドである．
また定理 2.3 (ii) と式 (10) より，P ′ (f ) ∩ [0, 1]E = P (fˆ) ∩ [0, 1]E = P (fˆ1 ) ∩ [0, 1]E が成り立
つが，定義より P ′ (f ) ∩ [0, 1]E 内の整数格子点の集合は If と一対一対応している．つまり If は(E, fˆ1 ) の独立集合族と一致する．
注意. 定理 2.2，定理 2.3，定理 2.4 等，この節で解説した性質はポリマトロイドだけでなく一般の劣モジュラ関数に対し成立する．詳しくは [7] を参照してほしい．

2.3 マトロイド合併
2 つの劣モジュラ関数の和は劣モジュラ関数であることから，台集合が共通のポリマトロ
イド (E, f1 ) と (E, f2 ) に対し (E, f1 + f2 ) はポリマトロイドであり，定義より P (f1 + f2 ) =P (f1 ) + P (f2 ) が成立つ．(右辺の “+” はミンコフスキー和を表す．) f1 と f2 が整数値の場合，P (f1 + f2 ) 内の整数点は P (f1 ) 内の整数点と P (f2 ) 内の整数点の和で書ける事が知られている．
この性質は組合せ最適化分野の幾つかの重要な結果の基礎であるが，証明は省略する．

平成24年度(第34回)数学入門公開講座テキスト(京都大学数理解析研究所，平成24年7月30日～8月2日開催)

特に M1 = (E, f1 ) と M2 = (E, f2 ) がマトロイドの場合，P (f1 + f2 ) をさらに超立方体内に制限し得られるマトロイド (E, (f1 + f2 )1 ) は M1 と M2 の合併 (union) と呼ばれている．上記の整数点分解性より，I ⊆ E が (E, (f1 + f2 )1 ) 内で独立であるための必要十分条件は I が M1 と M2の独立集合 I1 と I2 に分解可能なことである．
例題として Nash-Williams の森分割定理を紹介しよう．
定理 2.6 (Nash-Williams [15]). グラフ G = (V, E) が k 個の森に分解可能であるための必要十分
条件は，任意の非空な F ⊆ E に対し，|F | ≤ k|V (F )| − k が成立つことである．
証明. G 上のグラフ的マトロイドの階数関数は，g(F ) = |V (F )| − c(F ) (F ⊆ E) である．ここで c(F ) はグラフ (V (F ), F ) の連結成分の個数である．よってグラフ的マトロイドの k 個のコ
ピーの合併を考えると，G が k 個の森に分割可能であるための必要十分条件は F ⊆ E に対し|F | ≤ (kg)1 (F ) が成立つことである．この右辺の (kg)1 (F ) を k|V (F )| − k に置き換えても条件は等価である．

3 線形表現に対する操作
マトロイド (E, I) の体 F 上の線形表現とは，各 e ∈ E に対するベクトル ve ∈ F の割当てで，I = {F ⊆ E : {ve : e ∈ F } が線形独立 } となるものである．本節では前節で導入した (ポリ) マト
ロイド構成法に対する幾何学的解釈を与え，前節で紹介したマトロイド M(fk,l ) の線形表現を与える．(k = 2, l = 3 の場合が Laman の条件から誘導されるマトロイドである．) 本節の結果は，体を適宜拡大してくことで有限体上においても成立する事が知られているが，ここでは簡単のため
実数体上で話を進める．詳細は [2] 等を参照してほしい．

R 上のベクトル空間 W 内に表現されたポリマトロイド (E, f ) を考える．つまり，各 e ∈ E に対し付随する W 内の線形部分空間 Ae が存在し，f は f (F ) = dim⟨Ae : e ∈ F ⟩ で定義される．このとき，各 Ae から代表ベクトル xe ∈ Ae を取り出し，r(F ) = dim⟨xe : e ∈ F ⟩ と r : 2E → Z を定める事で E 上の線形マトロイド (E, r) が得られる．当然このマトロイドは代表ベクトルの取り方に依存しているが，次の定理 3.1 は殆ど全ての取り方に対し (E, f 1 ) が得られることを示している．
代表点集合 {xe : e ∈ E} が一般的とは，任意の X ⊆ E と f ∈ E \ X に対し，xf ∈ ⟨xe : e ∈ X⟩
ならば Af ⊆ ⟨xe : e ∈ X⟩ が成立つことである．ランダムに代表点を選んだ場合，確率 1 で一般的な代表点集合が得られることから，ほとんど全ての代表点集合は一般的である．さらに代表点集合に対し以下が成立する．
定理 3.1. 代表点集合 {xe : e ∈ X} が一般的なとき，

dim⟨xe : e ∈ E⟩ = min{|E \ X| + dim⟨Ae : e ∈ X⟩ : X ⊆ E}.

(11)

証明. 任意の X ⊆ E に対し，dim⟨xe : e ∈ E⟩ ≤ dim⟨xe : e ∈ E \ X⟩ + dim⟨xe : e ∈ X⟩ ≤|E \ X| + dim⟨Ae : e ∈ X⟩ より，“(左辺)≤(右辺)” が成立つ．
よって，ある X ⊆ E に対し等号が成立つことを示せばよい．E の要素数に対する帰納法で証明する．まず xf ∈/ ⟨xe : e ∈ E −f ⟩ なる f ∈ E が存在する場合を考える．E −f に対し帰納法の仮定から，dim⟨xe : e ∈ E −f ⟩ = |(E −f )\X|+dim⟨Ae : e ∈ X⟩ が，ある X ⊆ E −f に対し成立する．
dim⟨xe : e ∈ E⟩ = dim⟨xe : e ∈ E − f ⟩ + 1 より，dim⟨xe : e ∈ E⟩ = |E \ X| + dim⟨Ae : e ∈ X⟩が成立つ．
もしそのような f が存在しないならば，一般性の仮定より，Af ⊆ ⟨xe : E − f ⟩ が各 f ∈ E について成立つ．つまり，⟨Ae : e ∈ E⟩ = ⟨xe : e ∈ E⟩ となり，X = E に対して (11) の等号が成立
つ．

平成24年度(第34回)数学入門公開講座テキスト(京都大学数理解析研究所，平成24年7月30日～8月2日開催)

マトロイド M1 = (E, r1 ) と M2 = (E, r2 ) の合併を (E, (r1 + r2 )1 ) と定義した．よって各 Miに対し，ベクトル空間 Wi 内の線形表現 {xie : e ∈ E} が存在するならば，W1 ⊕ W2 内の 2 次元部
分空間 ⟨x1e ⟩ ⊕ ⟨x2e ⟩ から一般的なベクトルをとることで合併の線形表現が得られる．
次に線形ポリマトロイドの表現に対し，Dilworth 打切りに対応する操作を紹介する．ベクトル空間 W 内の (dim W − 1) 次元線形部分空間を W の超平面とよぶことにする．
定理 3.2 (Lovász [12]). {Ae : e ∈ E} を W 内の線形部分空間の集合とする．殆ど全ての超平面

H ⊂ W に対し，
dim⟨Ae ∩ H : e ∈ E⟩ = min{∑(dim⟨Ae : e ∈ X⟩ − 1) : E の非空部分集合への分割 P} (12)

X∈P

が成立つ．
証明. まず超平面 H ⊂ W を，以下が成立つように選ぶ: 任意の X ⊆ X に対し，

dim⟨Ae : e ∈ X⟩ ∩ H = dim⟨Ae : e ∈ X⟩ − 1.

(13)

つまり，H は ⟨Ae : e ∈ E⟩ と横断的に交わる．E が有限であることから，殆ど全ての超平面 H に対し，(13) は成立する．さらにこのような H の中で，各 F ⊆ E に対し dim{Ae ∩ H : e ∈ F } が最大となるように H を選ぶ．詳細は省略するが，E が有限であることから，殆ど全ての H に対しこの性質も成立する．(H = {x ∈ W : ⟨λ, x⟩ = 0} と H を表現したとき，dim{Ae ∩ H : e ∈ F } が最大でなければ，λ の座標値がある多項式の根になる．E が有限なので，このような多項式の個数は有限個であり，殆ど全ての λ に対し H は上記の性質を有する．)∑k(13) から，任意の分割 {E1 , . . . , Ek } に対し，dim⟨Ae ∩ H : e ∈ E⟩ ≤ i=1 dim⟨Ae ∩ H : e ∈∑k∑kEi ⟩ ≤ i=1 dim⟨Ae : e ∈ Ei ⟩ ∩ H = i=1 (dim⟨Ae : e ∈ Ei ⟩ − 1)．つまり，(12) の “≤” が成立している．逆方向を証明するために等号が成立する E の分割の存在性を証明する．
X ⊆ E に対し，X の非空部分集合への 2 分割 {X1 , X2 } で ⟨Ae ∩ H : e ∈ X1 ⟩ ∩ ⟨Ae ∩ H : e ∈X2 ⟩ = {0} となるものが存在する時，X は (表現 {Ae ∩ H : e ∈ E} に対し) 非連結とよび，非連結
でない X を連結とよぶことにする．
{E , . . . , Ek } を E の連結成分分割とする．つまり各 Ei は連結で dim⟨Ae ∩ H : e ∈ E⟩ =∑k 1
i=1 dim⟨Ae ∩ H : e ∈ Ei ⟩ が成立している．よって E の要素数に関する帰納法によって，E が
表現 {Ae ∩ H : e ∈ E} に対し連結な場合において，
dim⟨Ae ∩ H : e ∈ E⟩ = dim⟨Ae : e ∈ E⟩ − 1(14)を示せば十分である．

H が各 Ae と横断的に交わることから，xe ∈ Ae \ H に対し，
Ae = ⟨(Ae ∩ H) ∪ {xe }⟩(15)である．これから任意の xf ∈ Af \ H に対し，⟨Ae : e ∈ E⟩ = ⟨{Ae ∩ H : e ∈ E} ∪ {xf }⟩ が成り立つことを示す．これを示すために，ある f, g ∈ E に対し，ある xf ∈ Af \ H と xg ∈ Ag \ H が存在し，⟨{Ae ∩ H : e ∈ E} ∪ {xf }⟩ ̸= ⟨{Ae ∩ H : e ∈ E} ∪ {xg }⟩(16)が成立つと仮定し矛盾を導く．ある xf ∈ Af \ H と xg ∈ Ag \ H で (16) ならば，(15) より，任意の xf ∈ Af \ H と xg ∈ Ag \ H で (16) が成立つ．

E は表現 {Ae ∩ H : e ∈ E} に対し連結であることから，ある yf ∈ Af ∩ H と yg ∈ Ag ∩ H を含む極小に線形従属なベクトル集合 Y が {Ae ∩ H : e ∈ E} 内に存在する．{Ae ∩ H : e ∈ E} 内の平成24年度(第34回)数学入門公開講座テキスト(京都大学数理解析研究所，平成24年7月30日～8月2日開催)

要素を加え，Y \ {yg } を ⟨Ae ∩ H : e ∈ E⟩ の基 Z へ拡張する．(16) より，Z ∪ {xf , xg } は線形独立．よって，

dim⟨Z \ {yf } ∪ {xf , xg }⟩ = dim⟨Z⟩ + 1

が得られる．さらに Z の構成法より，yg ∈/ ⟨Z \ {yf }⟩ なので，

{yf , yg } ̸⊂ ⟨Z \ {yf } ∪ {xf , xg }⟩.
もし，dim⟨Z⟩ = dim⟨W ⟩ − 1 ならば，(16) は明らかに不成立．よって

dim⟨Z \ {yf } ∪ {xf , xg }⟩ ≤ dim⟨W ⟩ − 1
である．これらをまとめると，Z \ {yf } ∪ {xf , xg } を含み yf , yg を含まない超平面 H ′ が存在し，dim{Ae ∩ H ′ : e ∈ E} > dim{Ae ∩ H : e ∈ E} が成立している．yf ∈/ H ′ かつ yg ∈/ H ′ より，H ′は Af ，Ag と横断的に交わっている．さらに任意の xf ∈ Af \ H と xg ∈ Ag \ H でこれらの関係が成立つことから，(xf と xg の位置を調節することで) H ′ は他の Ae : e ∈ F とも横断的に交わる
ように取ってこれる．そのため H ′ の存在は H のとり方に矛盾する．
xf ∈ Af \ H を 1 つ選ぶと，xg ∈ ⟨{Ae ∩ H : e ∈ E} ∪ {xf }⟩ が任意の xg ∈ Ag に対し成立つことから，dim⟨Ae : e ∈ E⟩ = dim⟨{Ae ∩ H : e ∈ E} ∪ {xf }⟩ = dim⟨Ae ∩ H : e ∈ E⟩ + 1 となり，
(14) の証明が完了した．
この制限操作もまた Dilworth 打切りと呼ばれることがある．
これらの操作の例題として計数マトロイドの線形表現を与えよう．ハイパーグラフ G = (V, E)とは，有限集合 V とその部分集合の族 E の組である．fk,l を一般化して，ハイパーグラフ

G = (V, E)，k : V → Z+ , l ∈ Z+ に対し，∑
k(v) − lfk,l (F) =(F ⊆ E)(17)v∈V (F )と定める．ただし V (F) =∪e∈F e とする．この時，fk,l は単調劣モジュラ関数であり，E 上の計

数マトロイドと呼ばれるマトロイド M(fk,l ) を誘導する．

Mk,l の (R 上での) 線形表現は次のようにして得られる．まず各 v ∈ V に対し，k(v) 次⊕
e に対し，KV 内の線形部分空間v∈V Kv と定める．各
⊕∑Ke = v∈e Kv を定義すれば，dim⟨Ke : e ∈ F⟩ = v∈V (F ) k(v) = fk,0 (F) なので，{Ke : e ∈ E}
はポリマトロイド (E, fk,0 ) の線形表現を与えている．よって各 Ke から一般的に代表ベクトルを選んでくることで M(fk,0 ) の表現が得られる．
2 部グラフのハイパーグラフ表現を利用すれば，例 5 に挙げた横断マトロイドがあるハイパーグ
ラフと k によって定まる M(fk,0 ) であることが簡単に確認できる．つまり横断マトロイドもまた
線形マトロイドであり，2 部グラフの最大マッチングの大きさを代数的に求めることが可能である．
一般の l に対しては，l 個の一般的超平面 H1 , . . . , Hl を用意し，Ke′ = Ke ∩ H1 ∩ · · · ∩ Hl に元ベクトル空間 Kv を割当て，KV =平成24年度(第34回)数学入門公開講座テキスト(京都大学数理解析研究所，平成24年7月30日～8月2日開催)

よって (E, fk,l ) が表現されることが定理 3.2 よりわかる．実際，

dim⟨Ke ∩ H1 ∩ · · · ∩ Hl : e ∈ E⟩∑
= min{(dim⟨Ke ∩ H1 ∩ · · · ∩ Hl−1 : e ∈ X⟩ − 1) : E の分割 P}
X∈P= min{∑(min{= min{(dim⟨Ke ∩ H1 ∩ · · · ∩ Hl−2 : e ∈ X ′ ⟩ − 1) : X の分割 P ′ } − 1) : E の分割 P}

X ′ ∈P ′

X∈P

∑

∑

(dim⟨Ke ∩ H1 ∩ · · · ∩ Hl−2 : e ∈ X⟩ − 2) : E の分割 P}

X∈P

..
.
= min{∑(dim⟨Ke : e ∈ X⟩ − l) : E の分割 P}X∈P= fˆk,l (E).
よって各 Ke′ から代表ベクトルを一般的に選び M(fk,l ) の表現を得る．このような標準的な方法
で Laman の条件から定まるマトロイド M(f2,3 ) の表現を得ることが出来る．次節では，(等価だが) これとは異なる流れで M(f2,3 ) の表現を導出し，その表現が剛性行列になっていることを確認する．

4 組合せ的特徴付け定理の証明
4.1 グラフ的マトロイドと線形表現
有向グラフ D = (V, A) の接続行列とは，|A| × |V | の行列で e = (i, j) ∈ A に対応する行では iに対応する列の要素が 1，j に対応する列の要素が −1，その他の要素が 0 であるような行列である．無向グラフ G の各辺を任意に向き付けし得られる有向グラフの接続行列は，グラフ的マトロ
イド G(G) の線形表現を与えていることが容易にわかる．つまり，各 e = (i, j) ∈ E に対し，RV
内の 1 次元空間

Le = {x ∈ RV : x(i) + x(j) = 0 and ∀k ∈ V \ {i, j}, x(k) = 0}(18)を対応させることでグラフ的マトロイドの線形表現が得られる．

RV の d 個のコピーの直和空間 (Rd )V を考え，対応する Le の d 個のコピーの直和空間
Lde = {x ∈ (Rd )V : x(i) + x(j) = 0 and ∀k ∈ V \ {i, j}, x(k) = 0}(19)が得られる．定理 3.1 より，各 e ∈ E に対し Lde から一般的なベクトルを取ってくることでグラフ
的マトロイドの k コピーの合併 kG(G) に対する線形表現が得られる．このようにして G の k 個の森への分割可能性判定は，|E| 個のベクトルの線形独立性判定に帰着される．

4.2 2 次元一般剛性の特徴付け
1 次元の場合，剛性行列の e = (i, j) ∈ E に対応する行を p(i) − p(j) で割れば接続行列が得られる．そのため，1 次元剛性マトロイドとグラフ的マトロイドは等しく，剛性とグラフの連結性は等価である．

2 次元の場合，Laman の定理の条件と Nash-Williams の定理の条件を見比べ，2 次元一般剛性
マトロイド R2 (G) とグラフ的マトロイドの 2 つのコピーの合併 2G(G) は非常に強い関係がある

平成24年度(第34回)数学入門公開講座テキスト(京都大学数理解析研究所，平成24年7月30日～8月2日開催)

ことが予想できる．Lovász and Yemini [13] は，R2 (G) は 2G(G) の Dilworth 打切りになっているという点を指摘した．
実際，p ∈ (R2 )V に対し，p⊥ ∈ (R2 )V を各 v ∈ V に対し p⊥ (v) = Rπ/2 p(v) と定める．ただし

Rπ/2 は原点周りの π/2 回転を表す 2 × 2 行列である．(R2 )V 内の ⟨p⊥ ⟩ の直交補空間 H に対し，
L2e ∩ H = {x ∈ (R2 )V : ⟨p⊥ , x⟩ = 0, x(i) + x(j) = 0 and ∀k ∈ V \ {i, j}, x(k) = 0}
= {x ∈ (R2 )V : x(i) ∈ ⟨p(i) − p(j)⟩, x(i) + x(j) = 0 and ∀k ∈ V \ {i, j}, x(k) = 0}が成立つ．これは剛性行列において e に対応する行が張る空間と等しい．p が一般的な場合，H は一般的であることから，定理 3.2 が適用でき，R2 (G) の階数は

dim⟨Ae ∩ H : e ∈ E⟩ = min{∑(dim⟨L2e : e ∈ X⟩ − 1) : E の分割 P}

X∈P= min{∑(2(|V (X)| − c(X)) − 1) : E の分割 P}

X∈P= min{∑(2|V (X)| − 3) : E の分割 P}X∈P= fˆ2,3 (E)となる．つまり R2 (G) は f2,3 によって誘導されるマトロイドであり，Laman の定理が導かれた．

4.3 3 次元一般剛性の特徴付け
残念ながら 3 次元一般剛性マトロイド R3 (G) は，2 次元の場合のような単純な構造を持っておらず，その組合せ的特徴付けは未解決である．ここでは，3 次元一般剛性に関連する話題を 2 つ紹介する．
関数 fMaxwell : 2E → Z を fMaxwell (F ) = max{|F |, 3|V (F )| − 6} (F ⊆ E) と定義する．3 次元剛性の Maxwell の条件は任意の非空な F ⊆ E に対し，|F | ≤ fMaxwell (F ) であった．1 次元，2 次元の場合 Maxwell の条件がグラフの極小剛性の必要十分条件であったが，3 次元では図 3 のように十分ではない．R1 (G) がグラフ的マトロイドと等価であり，R2 (G) がグラフ的マトロイドの 2
合併の Dilworth 打切りであったことから，R3 (G) も Maxwell の条件に何らかの項を加えること
でその特徴付けが期待される．図 3 のような “暗に潜むヒンジ動き” の項を付加した関数が Dressら [5] によって提案された．ここではまず Dress らの階数関数予想と Jackson and Jordán[10] による反例を紹介する．

∪
E の被覆部分集合族 F = {F1 , . . . , Fk } とは，E = Fi ∈F Fi を満たす E の部分集合族である．
任意の異なる Fi , Fj ∈ F に対し，|V (Fi ) ∩ V (Fj )| ≤ 2 のとき，F は 2-thin と呼ばれる．2-thin
な F と異なる 2 頂点ペア {u, v} ⊆ V に対し，dF ({u, v}) = |{Fi ∈ F : {u, v} ⊆ Fi }| とし，∑∑val(F) =fMaxwell (F ) −(dF ({u, v}) − 1)
(20)
F ∈F

{u,v}⊂V,u̸=vと val を定める．このとき，Dress, Dreiding and Haegi[5](その後 Crapo, Dress and Tay[3]) は 3次元一般剛性マトロイドの階数がmin{val(F) : E の 2-thin な被覆部分集合族 F}(21)に等しいと予想した．この関数の定義は次の直感に基づいている．2 次元の場合 Dilworth 打切り

fˆ2,3 の値を与える E の分割は，剛な部分グラフへの分割を誘導することが知られている．よって，

平成24年度(第34回)数学入門公開講座テキスト(京都大学数理解析研究所，平成24年7月30日～8月2日開催)

3 次元の場合も剛な部分グラフへの分割を誘導するような E の被覆部分集合族を求めたい．3 次元の場合は 3 点以上を共有する 2 つの剛グラフの和もまた剛グラフであることから，そのような部分集合族は 2-thin である．さらに dF の項は，2 つの剛グラフが 2 点を共有している場合の相対的なヒンジ動きの自由度を考慮したものである．

Jackson and Jordán はブロックデザイン理論の代表的例題である biplane がこの予想の反例を与えてことを指摘した．n 要素の有限集合 V の biplane B とは，以下を満たす V の部分集合の族{V1 , . . . , Vm } である:
• 任意の異なる i, j に対して， |Vi ∩ Vj | = 2;
• 任意の異なる u, v ∈ V に対して， |{Vi ∈ B : {u, v} ⊆ Vi }| = 2.
これらの条件から各 Vi は同じ要素数であり，この要素数を k とすると，

( )
k
n=m=
+1
2
が成立つ．よって，各 i に対し Fi = {uv : {u, v} ⊂ Vi } とおくと，F = {F1 , . . . , Fk } は V 上の完
全グラフ Kn の辺集合に対する 2-thin な被覆部分集合族である．さらに k ≥ 3 ならば，∑∑

fMaxwell (Fi ) = m(3k − 6)Fi ∈F{u,v}⊂V,u̸=v( )n(dF ({u, v}) − 1) =2が成立つ．k = 11 に対し biplane が存在することが知られており，このとき val(F) < 0 であるた
め，Dress らの予想が正しくないことがわかる．Jackson and Jordán[10] はこの反例を克服する関数を定義し予想の修正を行ったが，その後この方面での進展は得られていない．
一般のグラフに対する 3 次元一般剛性の特徴付けは未解決であるが，平面グラフ, 完全 2 部グラ
フ，疎グラフ， 2 乗グラフ等，幾つかの特殊グラフクラスに対してはその性質が解明されている．
ここでは結果が重要でありかつ，証明が比較的簡単な Gluck の定理を紹介したい．
導入で紹介した通り，多面体の剛性に関する研究は古く，Cauchy の凸多面体の剛性定理以降，
非凸な多面体が常に剛であるかは長年未解決であった．1975 年，Gluck は殆ど全ての三角形分割された多面体が剛であることを証明した．この事もあり，1978 年の Connelly による柔かな多面体の発見は驚きの結果だったようである [4]．
多面体の辺と頂点の関係を表すグラフ (1-skelton) は平面グラフである事から，定理 1.1 より，Gluck の定理は一般剛性マトロイドにおいて以下のように解釈される．
定理 4.1 (Gluck[8]). G = (V, E) が平面グラフならば，E は R3 (G) の独立集合である．特に，極大平面グラフは極小に剛である．
証明. 以下は Whiteley[18] による証明である．
極大平面グラフ G = (V, E) に対し証明すれば十分である．まず点分割 (vertex-splitting) と呼ばれる操作を導入する．頂点 v と (任意にラベル付けされた)v の近傍 N (v) = {u1 , u2 , . . . , uk } を考える．v における点分割とは，直感的には図 4 のように v を中心に 2 辺 vu1 と vui を引き裂く操作である．正確には，1 < i ≤ k を満たす i に対し，G から v を削除し，新たな 2 点 v1 , v2 を追加，さらに辺 v1 v2 , v1 u1 , . . . , v1 ui , v2 ui , . . . , v2 uk , v2 u1 を追加する操作と定義される．
極大平面グラフの隣り合う 2 つの三角形に対し，この点分割操作の逆操作を行うことで小さなサイズの極大平面グラフが得られる．この事から，5 点以上の任意の極大平面グラフは K4 から点分

平成24年度(第34回)数学入門公開講座テキスト(京都大学数理解析研究所，平成24年7月30日～8月2日開催)

u1

u1
u7

u7
u2

u6

u2

v1 v2

u6

v

u3

u3
u5

u5

u4

u4

図4

点分割

割操作の繰り返しで構築可能である．K4 は極小に剛なグラフであるから，点分割が剛性を保持することを証明すれば定理が証明される．
いま G が G′ = (V ′ , E ′ ) から v ∈ V ′ における点分割によって得られたとし，新たな頂点を v1 , v2とする．頂点数の帰納法からある p′ : V ′ → R3 が存在し，(G′ , p′ ) は無限小に剛である．つまりrank R(G′ , p′ ) = 3|V ′ | − 6．ここで p : V → R3 を，{ ′p (v) (w ∈ {v1 , v2 })p(w) =
p′ (w) (w ∈ V \ {v1 , v2 })(22)と定義する．このとき p′ (v1 ) = p′ (v2 ) となり，v1 v2 に対応する辺長は 0 となってしまう．しかしここでは仮想的に v1 v2 は長さ 0 で向き d ∈ R3 \ {0} を有すると仮定し，剛性行列 R(G, p) を解析
しよう．つまり R(G, p) の v1 v2 に対応する行の p(v1 ) − p(v2 ) を d に置き換える．

(22) の関係を利用しながら，R(G, p) 内において，v1 に対応する 3 列をそれぞれ対応する v2 の列に加え，さらに v1 u1 の行を v2 u1 の行へ，v1 ui の行を v2 ui の行へ加えることで，R(G, p) は以下の形に変形できる：





d
p
(v)
−
p′ (u1 ) p′ (v) − p′ (ui )



∗
′

0
R(G′ , p′ )







ここで左上ブロックは v1 に対応する 3 列と {v1 v2 , v1 u1 , v1 ui } に対応する 3 行から誘導される 3×3
部分行列である．特に，v2 と v を同一視することで右下ブロックが R(G′ , p′ ) となる．このため，dをd ∈/ ⟨{p′ (v)−p′ (u1 ), p′ (v)−p′ (ui )}⟩ と選ぶことで rank R(G, p) = 3+rank R(G′ , p′ ) = 3|V |−6が得られる．
最後に p(v1 ) = p(v2 ) の状態を解消するために，p(v2 ) を d の向きに連続的に移動させる．この時，R(G, p) の各要素の値は連続的に変化する点に注意してほしい．そのため p(v2 ) を d 方向に摂動させても，剛性行列の階数を保持される．

5 並行再描画問題
本節では並行再描画問題を紹介する．グラフ G と p : V → Rd に対し剛性の問題では (G, p) をフレームワークとよんでいたが，ここではグラフ G の描画と呼ぶことにしよう．描画 (G, p) の並
行再描画とは，対応する各辺が並行であるように p を連続的に移動させることで得られる描画のことである (図 5)．つまり q : V → Rd がq(i) − q(j) ∈ ⟨p(i) − p(j)⟩∀e = (i, j) ∈ E(23)

平成24年度(第34回)数学入門公開講座テキスト(京都大学数理解析研究所，平成24年7月30日～8月2日開催)

(a)

(b)

図5

(a) 自明な再描画．(b) 非自明な再描画．

を満たしているとき，(G, p + q) は並行再描画である．また逆に，並行再描画 (G, p′ ) に対し

q = p′ − p は式 (23) を満たす．どの描画 (G, p) に対しても拡大縮小と平行移動によって得られる
描画は並行再描画である．このような拡大縮小と平行移動の線形結合によって得られる並行再描
画を自明とよび，自明な並行再描画のみが可能な描画を頑健とよぶことにする．並行再描画問題とは，描画 (G, p) が頑健であるかを判定する問題である．
定理 5.1 (Whiteley[19]). グラフ G = (V, E) と埋込み p : V → Rd に対し，p が一般的ならば，描画 (G, p) が頑健であるための必要十分条件は

fˆd,d+1 (E) = d|V | − (d + 1).

(24)

証明. (23) は，各 e = (i, j) ∈ E に対し，

⟨q(i) − q(j), α⟩ = 0∀α ∈ Rd with ⟨p(i) − p(j), α⟩ = 0(25)と書ける．つまり

De = {x ∈ (Rd )V : ⟨p(i) − p(j), x(i)⟩ = 0, x(i) + x(j) = 0 and ∀k ∈ V \ {i, j}, x(k) = 0}と定義してやると，q ∈ (Rd )V が ⟨De : e ∈ E⟩ の直交補空間に含まれることが (G, p + q) が再描画であるための必要十分条件となる．自明な並行再描画に対応する q はこの直交補空間
内の d + 1 次元線形部分空間を形成しており，(G, p + q) が頑健であるための必要十分条件は

dim⟨De : e ∈ E⟩ = d|V | − (d + 1) となる．
よって fˆd,d+1 (E) = dim⟨De : e ∈ E⟩ を示せば良い．Laman の定理の証明と同じ流れで，一般的 p ∈ (Rd )V に対し，H を ⟨p⟩ の直交補空間とすると，
Lde ∩ H = {x ∈ (Rd )V : ⟨p, x⟩ = 0, x(i) + x(j) = 0 and ∀k ∈ V \ {i, j}, x(k) = 0}
= {x ∈ (Rd )V : ⟨p(i) − p(j), x(i)⟩ = 0, x(i) + x(j) = 0 and ∀k ∈ V \ {i, j}, x(k) = 0}
= Deが成立つ．よって定理 2.4 より

dim⟨De : e ∈ E⟩ = dim⟨Lde ∩ H : e ∈ E⟩∑
= min{(dim⟨Lde : e ∈ X⟩ − 1) : E の分割 P}
X∈P= min{∑(d|V (X)| − (d + 1)) : E の分割 P}X∈P= fˆd,d+1 (E)が得られる．

平成24年度(第34回)数学入門公開講座テキスト(京都大学数理解析研究所，平成24年7月30日～8月2日開催)

参考文献[1] L. Asimow and B. Roth. The rigidity of graphs. Transactions of the American Mathematical Society, 245:279–289, 1978.
[2] T. Brylawski. Constructions. In N. White, editor, Theory of Matroids (Encyclopedia of
Mathematics and its Applications), chapter 7. Cambridge University Press, 1986.
[3] H. Crapo, A. Dress, and T. S. Tay. Problem 4.2. Contemporary Mathematics, 197:414,
1996.
[4] E. D. Demaine and J. O’Rourke. 幾何的な折りアルゴリズム - リンケージ、折り紙、多面体. 近代科学社, 2009. 上原隆平訳.
[5] A. Dress, A. Dreiding, and H. Haegi. Classification of mobile molecules by category
theory. In Symmetries and Properties of Non-Rigid Molecules: A Comprehensive Survey:
Proceedings of an International Symposium, page 39. Elsevier, 1983.
[6] J. Edmonds. Submodular functions, matroids, and certain polyhedra. In Combinatorial
Structures and Their Applications,, pages 69–87, 1970.
[7] S. Fujishige. Submodular Functions and Optimization. Annals of Discrete Mathematics.
Elsevier, 2nd edition, 2005.
[8] H. Gluck. Almost all simply connected closed surfaces are rigid. In Geometric topology,
Lecture Notes in Mathematics, 438, pages 225–240. Springer, 1975.
[9] J. E. Graver, B. Servatius, and H. Servatius. Combinatorial Rigidity. Graduate Studies
in Mathematics,. AMS, 1993.
[10] B. Jackson and T. Jordán. The Dress conjectures on rank in the 3-dimensional rigidity
matroid. Advances in Applied Mathematics, 35(4):355–367, 2005.
[11] G. Laman. On graphs and rigidity of plane skeletal structures. Journal of Engineering
Mathematics, 4(4):331–340, 1970.
[12] L. Lovász. Flats in matroids and geometric graphs. In Combinatorial Surveys: Proceedingsof the Sixth British Combinatorial Conference, pages 45–86. Academic Press, 1977.
[13] L. Lovász and Y. Yemini. On generic rigidity in the plane. SIAM Journal on Algebraic
and Discrete Methods, 3:91–98, 1982.
[14] J. H. Mason. Matroids as the study of geometrical configurations. In M. Aigner, editor,
Higher Combinatorics (Proceedings NATO Advanced Study Institute, 1976), pages 133–
176, 1977.
[15] C. Nash-Williams. Decomposition of finite graphs into forests. Journal of the London
Mathematical Society, 1(1):12, 1964.
[16] J. Oxley. Matroid theory,. Oxford University Press, 2nd edition, 2011.
[17] A. Schrijver. Combinatorial optimization: polyhedra and eﬃciency. Springer, 2003.
[18] W. Whiteley. Vertex splitting in isostatic frameworks. Structural Topology, 16:23–30,
1990.
[19] W. Whiteley. Some matroids from discrete applied geometry. Contemporary Mathematics,
197:171–312, 1996.