ガイリンガー-ラマンの定理

Geiringer-Laman_theorem
。 Geiringer – Lamanの定理は、 2 { 2}-バージョイントフレームワークに関する次元ユークリッド空間。この定理は、1927年にヒルダポラチェクガイリンガーによって最初に証明されました。 その後、1970年にジェラルドレーマンによって証明されました。 ペブルゲームと呼ばれる効率的なアルゴリズムを使用して、このクラスのグラフを識別します。この定理は、一般化されたPebbleゲームを使用する他のタイプのフレームワークの多くのGeiringer-Lamanタイプの結果のインスピレーションとなっています。

コンテンツ
1 定理のステートメント
2 証明の概要
2.1 一般的な剛性と一般的な微小剛性の同等性 2.2 マクスウェル方向 2.3 一般的な微小剛性とHenneberg構造の同等性 2.4 Hennebergの構成可能なグラフは、一般的に非常に厳密です。 2.5 参考文献

定理のステートメント
この定理は、構造剛性のページにある一般性の定義に依存しています。させて V （（ E ）。 { V（E）}

 一連のエッジの頂点セットを示します E { E}

 。
ガイリンガー-ラマンの定理。 グラフG =（（ V E ）。 { G =（V、E）}

 で一般的に堅い 2 { 2}

 -バージョイントフレームワークに関する寸法 G { G}

 スパニングサブグラフがありますG ′ =（（ V E ′ ）。
{ G’=（V、E’）}

 そのような| E ′
| 2 | V | 3 { | E’| = 2 | V | -3}
  すべてのサブセットF ⊂ E ′
{ F subset E’}
、 | 2 | V（（ F ）。 | 3
{ | F | leq 2 | V（F）| -3}

 。

  図1.（a）と（c）は、 2 { 2}

 -寸法。（b）は一般的に柔軟なグラフです 2 { 2}

 -寸法。
スパンサブグラフG ′
{ G’}

 定理の条件を満たすことは、Geiringer-Laman、または最小剛性グラフと呼ばれます。2番目の条件を満たすグラフは、スパースマトロイドの独立集合を形成し、と呼ばれます。（（ 2 3 ）。 {（2，3）}

 -スパース。両方の条件を満たすグラフは、（（ 2 3 ）。 {（2，3）}

 -タイトなグラフ。一般的に剛体のグラフは次のようになるという定理の方向（（ 2 3 ）。 {（2，3）}

 -タイトはマクスウェル方向と呼ばれます。これは、ジェームズクラークマクスウェルが同様の必要な条件を与えたためです。（（ d （（ d +1 2 ）。）。
{ left（d、{d + 1 choice 2} right）}

 -グラフが独立しているためのスパース性 d { d}

 -次元の一般的な剛性マトロイド。定理のもう一方の方向は、証明するのがより難しい方向です。寸法についてd ≥ 3
{ d geq 3}

 、であるグラフ（（ d （（ d +1 2 ）。）。
{ left（d、{d + 1 choice 2} right）}

 -タイトは必ずしも一般的に最小限の剛性ではありません。つまり、マクスウェル方向の逆は真ではありません。
例。図1のグラフを考えてみましょう。（c）のグラフは一般的に最小剛性ですが、無限小ではありません。赤い速度ベクトルは、自明ではない微小な屈曲を表しています。（a）の赤いエッジを削除すると、一般的に最小剛性のスパニンググラフが生成されます。（b）に赤い破線のエッジを追加すると、グラフは一般的に最小限の剛性になります。
定理。させて G { G}

 グラフになります。次のステートメントは同等です。 G { G}

 一般的に最小限の剛性です。 G { G}

 は（（ 2 3 ）。 {（2，3）}

 -きつい; と G { G}

 3つのエッジが互いに素なスパニングツリーが含まれています
T 1 T 2 { T_ {1}、T_ {2}、}

 と 3
{ T_ {3}}

 （i）の各頂点 G { G}

 はこれらのスパニングツリーのちょうど2つに含まれており、（ii）これらのスパニングツリーの個別のサブツリーは同じ頂点セットを持っ
最初のステートメントと2番目のステートメントの同等性は、Geiringer-Lamanの定理です。最初と3番目のステートメントの同等性は、Geiringer-Lamanの定理を介して 、その後、より直接的なアプローチを介してによって最初に証明されました。

証明の概要
以下に示すガイリンガー-ラマンの定理の証明は、ラマンの証明に基づいています。さらに、以下の証明の詳細は、ここにある講義ノートに基づいています
バージョイントシステムを検討してください（（ G = （（ V E
）。 δ ）。 {（G =（V、E）、 delta）}

 とフレームワーク（（ G p ）。 {（G、p）}

 このシステムの、ここでp ： V R 2 |V |
{ p：V rightarrow mathbb {R} ^ {2 | V |}}

 の頂点を配置するマップです G { G}

 距離の制約があるように平面内で δ { delta}

 満足しています。便宜上、参照します p { p}

 のフレームワークとして G { G}

 。Geiringer-Lamanの定理の証明は、以下の概要に従います。
グラフ G { G}

 それが一般的に無限小に剛性である場合に限り、一般的に剛性です。
微小剛性はグラフの一般的な特性です。
剛性はグラフの一般的な特性です。
フレームワークの場合（（ G p ）。 {（G、p）}
 は非常に硬く、それから硬いです。
フレームワークの場合（（ G p ）。 {（G、p）}
 は、無限小の剛性と剛性に関して一般的であり、その後、微小に剛性が
グラフの場合 G { G}

 一般的な微小に剛性のあるフレームワークがあり、 G { G}

 Geiringer-Lamanグラフです。
グラフ G { G}

 はGeiringer-Lamanグラフであり、 G { G}

 ヘンネベルク構造です。
グラフの場合 G { G}

 ヘンネベルク構造を持っている、そして G { G}

 一般的な非常に堅いフレームワークを持っています。
ステップ1では、一般的な剛性の設定を設定して、一般的な剛性ではなく、一般的な微小な剛性に焦点を当てることができるようにします。微小剛性には、通常の剛性の場合の2次方程式ではなく、線形方程式のシステムが含まれるため、これはより簡単なアプローチです。特に、一般的なフレームワークの剛性マトリックスに関する構造特性を証明できます。これらの結果は、AsimowとRothによって最初に証明されました。 一般的に剛体のグラフの組み合わせ特性を参照してステップ1.4では、フレームワークは微小な剛性に関して一般的でなければならないことに注意して特に、フレームワーク（（ G p ）。 {（G、p）}

 つまり、剛性が高く、剛性に関して一般的であるとは限りません。ステップ2は、証明のマクスウェル方向です。これは、剛性マトリックスの単純なカウント引数から得られます。ステップ3は、一般的に最小剛性のグラフが、以下に定義する2つの簡単な操作を使用して単一のエッジから開始して作成できるグラフであることを示しています。ステップ4は、このタイプの構造のグラフが一般的に非常に硬いことを示しています。最後に、ステップ1が証明されると、ステップ2〜3はガイリンガー-ラマンの定理を証明します。

一般的な剛性と一般的な微小剛性の同等性
させてG =（（ V E ）。 { G =（V、E）}

 グラフになります。まず、微小剛性に関する一般的なフレームワークが、オープンで密なセットを形成することを示します。R 2 | V |
{ mathbb {R} ^ {2 | V |}}

 。フレームワークの1つの必要十分条件 p { p}

 の G { G}

 無限小に剛性であるということは、その剛性マトリックスのためです R （（ p ）。 { R（p）}

 のすべてのフレームワークで最大ランクを持つ G { G}

 。
命題1.あらゆるフレームワークについて p { p}

 の G { G}

 と近所 N （（ p ）。 { N（p）}

 、フレームワークが存在します q { q}

 の N （（ p ）。 { N（p）}

 剛性マトリックス R （（ q ）。 { R（q）}

 最大ランクが
証拠。剛性マトリックスの場合 R （（ p ）。 { R（p）}

 最大ランクがない場合は、エッジのサブセットに対応する一連の従属行がありますE ′ ⊂ E
{ E’ subset E}

 他の剛性マトリックスの場合 R （（ q ）。 { R（q）}

 、に対応する行E ′
{ E’}

 独立しています。させてXE ′
{ { mathcal {X}} _ {E’}}

 対応する行が対応するようなフレームワークのセットであるE ′
{ E’}

 それらの剛性マトリックスは依存しています。言い換えると、XE ′
{ { mathcal {X}} _ {E’}}

 フレームワークのセットです p { p}

 に対応する行のマイナーがE ′
{ E’}

 の R （（ p ）。 { R（p）}

 は 0 { 0}

 。したがって、XE ′
{ { mathcal {X}} _ {E’}}

 の曲線ですR 2 | V |
{ mathbb {R} ^ {2 | V |}}

 、マイナーは行列のエントリの多項式であるため。させてX
{ { mathcal {X}}}

 のエッジのすべてのサブセットにわたるこれらの曲線の和集合である E { E}

 。フレームワークの場合 R （（ p ）。 { R（p）}

 一部のフレームワークの最大ランクがありません p { p}

 、 それから p { p}

 に含まれていますX
{ { mathcal {X}}}

 。最後に、X
{ { mathcal {X}}}

 は有限の曲線のセットであり、命題が証明されます。
命題2.微小剛性は、グラフの一般的な特性です。
証拠。微小剛性に関する1つの汎用フレームワークが微小剛性である場合、すべての汎用フレームワークが微小剛性であることを示します。フレームワークの場合 p { p}

 グラフの G { G}

 非常に硬いので、 R （（ p ）。 { R（p）}

 最大ランクが剛性マトリックスの核は、フレームワークの微小運動の空間であり、次元を持っていることに注意して（（ 3 2 ）。
{ {3 choice2}}

 非常に堅固なフレームワーク用。したがって、階数退化定理により、1つの一般的なフレームワークが微小に剛性である場合、すべての一般的なフレームワークは微小に剛性が
命題3.フレームワークの場合 p { p}

 グラフの G { G}

 は非常に硬く、それから硬いです。
証拠。と仮定する p { p}

 厳密ではないので、フレームワークが存在します q { q}

 近所で N （（ p ）。 { N（p）}

 そのような ρ （（ p
）。= ρ（（ q ）。 { rho（p）= rho（q）}

 と q { q}

 の些細な動きでは取得できません p { p}

 。以来 q { q}

 にあります N （（ p ）。 { N（p）}

 、存在するd e l t a
>> 0 { delta> 0}
0}””>
 と‖ h ‖ < δ
{ | h | < delta}

 そのようなq = p + h
{ q = p + h}

 。いくつかの代数を適用すると、次のようになります。 ρ （（ p
）。I j − ρ（（ q
）。I j = ‖ p I− p j ‖
2− ‖ q I − qj ‖
2= ‖ h I − hj ‖
2− 2（（ pI − p j ）。 （（ hI − h j
）。= 0。
{ { begin {aligned} rho（p）_ {ij}- rho（q）_ {ij}＆= | p_ {i} -p_ {j} | ^ {2}- | q_ {i} -q_ {j} | ^ {2} \＆= | h_ {i} -h_ {j} | ^ {2}-2（p_ {i} -p_ {j}）（ h_ {i} -h_ {j}）\＆=0。end {aligned}}}

したがって、‖ h I
−h j ‖ 2 ‖ h‖ = 2（（ p I − p j）。（（h I − h j）。‖ h ‖ = 0。
{ { frac { | h_ {i} -h_ {j} | ^ {2}} { | h |}} = 2（p_ {i} -p_ {j}）{ frac { （h_ {i} -h_ {j}）} { | h |}}=0。}

シーケンスを選択できますδ n
{ delta _ {n}}

 そのようなδ n+1 δ n
{ delta _ {n + 1} < delta _ {n}}

 と
リム n ∞δ n 0
{ lim _ {n rightarrow infty} delta _ {n} = 0}

 。これは〜をひき起こす
リム n ∞‖ h n = 0 { lim _ {n rightarrow infty} | h_ {n} | = 0}

 と
リム n ∞‖ h
n 私
−h n j ‖ 2 ‖ h n ‖ = （（ hI ⋆ − h j ⋆ ）。 { lim _ {n rightarrow infty} { frac { | h_ {n、i} -h_ {n、j} | ^ {2}} { | h_ {n} |}} =（h_ {i} ^ { star} -h_ {j} ^ { star}）}

 。したがって、 2 （（ pI − p j ）。 （（ hI ⋆ − h j ⋆
）。 = リムn ∞ 2（（ pI − p j
）。‖ h
n 私− h n j ‖
2‖ h n ‖ =
リムn ∞ ‖ h
n 私− h n j ‖
2‖ h n ‖ = 0。
{ { begin {aligned} 2（p_ {i} -p_ {j}）（h_ {i} ^ { star} -h_ {j} ^ { star}）＆= lim _ {n rightarrow infty} 2（p_ {i} -p_ {j}）{ frac { | h_ {n、i} -h_ {n、j} | ^ {2}} { | h_ {n} |}} \＆= lim _ {n rightarrow infty} { frac { | h_ {n、i} -h_ {n、j} | ^ {2}} { | h_ {n} |}} \＆=0。end {aligned}}}

上記の式の最初と最後の式は、次のように述べています。h ⋆
{ h ^ {star}}

 フレームワークの微小な動きです p { p}

 。間に些細な動きがないので p { p}

 と q { q}

 、h ⋆
{ h ^ {star}}

 些細な微小な動きではありません。したがって、 p { p}

 無限小ではありません。
命題4.フレームワークの場合 p { p}

 グラフの G { G}

 は、微小な剛性に関して剛性があり一般的であり、 p { p}

 非常に硬いです。
証拠。これは、陰関数定理に基づいています。まず、の些細な動きをすべて除外します p { p}

 。以来 R （（ p ）。 { R（p）}

 最大ランク、いいえ 3 { 3}

 のポイント p { p}

 共線です。したがって、ピン留めできます 2 { 2}

 のポイント p { p}

 些細な動きを除外する：原点にある1つのポイントと、X
{ x}

 -すべての拘束と一致する原点からの距離にある軸。これにより、固定されたフレームワークが生成されます q { q}

 に住んでいるR 2 | V | − 3 { mathbb {R} ^ {2 | V | -3}}

 。これは、近隣のすべてのフレームワークに対して実行できます N （（ p ）。 { N（p）}

 の p { p}

 近所を取得するには N （（ q ）。 { N（q）}

 の q { q}

 固定されたフレームワークの。このようなフレームワークのセットは依然として滑らかな多様体であるため、剛性マップと剛性マトリックスを新しいドメインで再定義できます。具体的には、剛性マトリックス R （（ q ）。 { R（q）}

 固定されたフレームワークの q { q}

 もっている2 | V | − 3
{ 2 | V | -3}

 列とランクが等しい R （（ p ）。 { R（p）}

 、 どこ p { p}

 に対応する固定されていないフレームワークです q { q}

 。この固定された設定では、フレームワークが剛性マップの唯一の近くのソリューションである場合、フレームワークは剛性になります。
ここで、固定されていないフレームワークを想定します p { p}

 は無限小ではないので、r a n k（（ R（（ p ）。 ）。= k < 2 | V| − 3
{rank（R（p））= k <2 | V | -3}

 。そうしてr a n k（（ R（（ q ）。 ）。= k
{rank（R（q））= k}

 、 どこ q { q}

 の固定バージョンです p { p}

 。ここで、陰関数定理を適用するように設定します。私たちの継続的に微分可能な関数は剛性マップですρ ： R 2 | V| −
3R | E |
{ rho： mathbb {R} ^ {2 | V | -3} rightarrow mathbb {R} ^ {| E |}}

 。のジャコビアン ρ { rho}

 剛性マトリックスです。エッジのサブセットを検討するE ′ ⊂ E
{ E’ subset E}

 に対応する k { k}

 の独立した行 R （（ q ）。 { R（q）}

 、部分行列を生成します R （（ q
）。E ′
{ R（q）_ {E’}}

 。私たちは見つけることができます k { k}

 の独立した列 R （（ q
）。E ′
{ R（q）_ {E’}}

 。これらの列のエントリをベクトルで示しますy = y
1 … y k { y = y_ {1}、 dots、y_ {k}}

 。残りの列のエントリをベクトルで示しますX =X 1 … X2 | V | −
3 − k
{ x = x_ {1}、 dots、x_ {2 | V | -3-k}}

 。The k ×× k { k times k}

 の部分行列 R （（ q
）。E ′
{ R（q）_ {E’}}

 誘発 y 1 … y k { y_ {1}、 dots、y_ {k}}

 は可逆であるため、陰関数定理により、連続的に微分可能な関数が存在します。 g { g}

 そのようなy = g（（ X ）。 { y = g（x）}

 と ρ （（ X y
）。E ′ = ρ（（ q
）。E ′
{ rho（x、y）_ {E’} = rho（q）_ {E’}}

 。したがって、フレームワークq E ′ ）。 { q_ {E’}）}

 サブグラフのG ′ =（（ V E ′ ）。
{ G’=（V、E’）}

 剛体ではなく、 R （（ q
）。E ′
{ R（q）_ {E’}}

 の行スペースにまたがる R （（ q ）。 { R（q）}

 、 q { q}

 剛性もありません。これは私たちの仮定と矛盾するので、 p { p}

 非常に硬いです。
命題5.剛性はグラフの一般的な特性です。
証拠。させて p { p}

 の厳格なフレームワークであること G { G}

 それは剛性に関して一般的です。定義上、厳格なフレームワークの近隣があります N （（ p ）。 { N（p）}

 の p { p}

 。命題1によって、フレームワークがあります q { q}

 の N （（ p ）。 { N（p）}

 これは、微小剛性に関して一般的であるため、命題4によるものです。 q { q}

 非常に硬いです。したがって、命題2では、微小剛性に関して一般的なすべてのフレームワークは微小剛性であり、命題3ではそれらも剛性です。最後に、すべての近所 N （（ p ′ ）。
{ N（p’）}

 すべてのフレームワークのp ′
{ p’}

 剛性に関して一般的なものにはフレームワークが含まれていますq ′
{ q’}

 これは、命題1による、微小剛性に関して一般的です。 p { p}

 剛性がありますp ′
{ p’}

 剛性が

  図2.定理1の証明の両方向の視覚化。（a）は命題5の証明も示しています。
定理1.グラフ G { G}

 それが一般的に無限小に剛性である場合に限り、一般的に剛性です。
証拠。証明は、命題5の証明と同様の議論に従います。 G { G}

 一般的に堅固であり、一般的なフレームワークが存在します p { p}

 定義上剛性である剛性に関して。命題1および4により、 p { p}

 フレームワークがあります q { q}

 これは、微小剛性および微小剛性に関して一般的です。したがって、命題2によって。 G { G}

 一般的に非常に硬いです。
他の方向については、反対に G { G}

 一般的には微小に剛性がありますが、一般的には剛性ではありません。次に、一般的なフレームワークが存在します p { p}

 定義上剛性ではない剛性に関して。命題1により、 p { p}

 フレームワークがあります q { q}

 これは、微小な剛性に関して一般的です。仮定により q { q}

 は非常に硬く、命題3による q { q}

 剛性もしたがって、 p { p}

 剛性がなければならず、命題5により、剛性に関して一般的なすべてのフレームワークは剛性です。これは、私たちの仮定と矛盾します G { G}

 一般的に厳格ではありません。

マクスウェル方向
Geiringer-Lamanの定理のマクスウェル方向は、剛性マトリックスの単純なカウント引数から得られます。
マクスウェル方向。グラフの場合 G { G}

 一般的な微小に剛性のあるフレームワークがあり、 G { G}

 Geiringer-Lamanサブグラフが
証拠。させて p { p}

 の一般的な微小に堅固なフレームワークである G { G}

 。定義により、 R （（ p ）。 { R（p）}

 最大ランク、すなわち、r a n k（（ R（（ p ）。 ）。= 2 | V | − 3 {rank（R（p））= 2 | V | -3}

 。特に、 R （（ p ）。 { R（p）}

 もっている2 | V | − 3
{ 2 | V | -3}

 独立した行。の各行 R （（ p ）。 { R（p）}

 のエッジに対応します G { G}

 、したがって、部分行列 R （（ p
）。G ′
{ R（p）_ {G’}}

 独立した行だけでサブグラフに対応しますG ′ =（（ V E ′ ）。
{ G’=（V、E’）}

 そのような | E ′ |= 2 | V | − 3 { | E’| = 2 | V | -3}

 。さらに、任意のサブグラフH =（（ V ′ F ）。
{ H =（V’、F）}

 のG ′
{ G’}

 部分行列に対応します R （（ p
）。 H { R（p）_ {H}}

 の R （（ p
）。G ′
{ R（p）_ {G’}}

 。の行以来 R （（ p
）。G ′
{ R（p）_ {G’}}

 は独立しているので、 R （（ p
）。 H { R（p）_ {H}}

 。したがって、r a n k（（ R（（ p ）。 H）。= | F |
{rank（R（p）_ {H}）= | F |}

 、これは明らかに満足します| F | ≤ 2 | V （（ F
）。| − 3
{ | F | leq 2 | V（F）| -3}

 。

一般的な微小剛性とHenneberg構造の同等性
ここで、Geiringer-Lamanの定理の反対方向の証明を、一般的に最小剛性のグラフがHenneberg構造を持っていることを最初に示すことから始めます。ヘンネベルクグラフ G { G}

 次の再帰的定義が G { G}

 シングルエッジまたは G { G}

 Hennebergグラフから取得できます
G ′ { G’}

 次のいずれかの操作を介して
に頂点を追加しますG ′
{ G’}
 に接続します 2 { 2}
 の異なる頂点G ′
{ G’}
 
エッジの場合（（ u v ）。 {（u、v）}
 と頂点 w { w}
 のG ′
{ G’}
 、頂点を追加しますG ′
{ G’}
 、に接続します
u v { u、v、}