正方形の格子（たとえば３×３格子）からなる構造物を考える．辺は鋼材でできていて剛であるが，連結部はピン・ジョイントで柔軟である．そのため，構造物全体としては剛ではない．

　すべての格子に筋交いを入れて三角形に分割する補強をすれば堅牢な構造になるが，それでは費用が高くつく．ここでの関心は，この構造物を補強して剛にするのにできる限り少ない数の筋交いを入れることである．

　答を先にいうと３×３格子の場合の最少筋交い数は５である．６や７では多すぎ（冗長）だが，４では少なすぎ，すなわち筋交いを１カ所取り除くと構造物の剛性が損なわれてしまう．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

【１】冗長性あるいは不足数

　上の問題では，各頂点において力学的釣り合いが満たされなければならない．結論を先にいうと，ｖ頂点を抑え込むのに必要な最少の棒材数は

　　ｅ＝２ｖ−３

である．

　２次元では

　　ｅ≧２ｖ−３

によって，剛体か否かの判別が行われるのであるが，ｅ＝２ｖ−３を満たすにも関わらず剛体でない場合，棒材の組み替えによって，頂点の位置を動かさずに剛体に変換することができる．

　したがって，グラフの幾何学的安定性の指標として，冗長度ｒを

　　ｒ＝ｅ−２ｖ＋３

あるいは，不足している辺数

　　ｄ＝２ｖ−３−ｅ

によって定義することができる．

　なお，冗長度０（不足数０）は最少筋交い数を与えるものであるが，筋交いをどこに配置すべきか？という問題とは別問題である．

　同様に，３次元骨組みの場合，ｖ頂点を抑え込むのに必要な最少の棒材数は

　　ｅ＝３ｖ−６

であるから，

　　ｄ＝３ｖ−６−ｅ

ｎ次元骨組みの場合，

　　ｄ＝ｎｖ−ｎ（ｎ＋１）／２−ｅ

１次元骨組みの場合，

　　ｄ＝ｖ−１−ｅ　　（木グラフ）

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

【２】２次元ｎ×ｍ格子の不足数

　ｎ×ｍ格子の格子点数と辺数は

　　ｖ＝（ｎ＋１）（ｍ＋１）

　　ｅ＝ｎ（ｍ＋１）＋ｍ（ｎ＋１）

　したがって，不足している辺数は

　　２ｖ−３−ｅ＝ｎ＋ｍ−１

これを越える場合はいくつかの筋交いを削除することが常に可能である．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

【３】３次元ｎ×ｍ格子の不足数

［Ｑ］ユニバーサルジョイントでつながれた，ｎ×ｍ格子のすべての格子に筋交いを１本ずついれると剛性は保たれるだろうか？

［Ａ］３次元骨組みにおいて，ｖ頂点を抑え込むのに必要な最少の棒材数は

　　ｅ＝３ｖ−６

である．

　ｎ×ｍ格子のすべてに筋交いを１本ずついれた場合の格子点数と辺数は

　　ｖ＝（ｎ＋１）（ｍ＋１）

　　ｅ＝ｎ（ｍ＋１）＋ｍ（ｎ＋１）＋ｎｍ

　したがって，不足している辺数は

　　３ｖ−６−ｅ＝２（ｎ＋ｍ）−３

　１×１格子の場合であっても対角線に棒材を追加しなければならない．

−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−

［Ｑ］ユニバーサルジョイントでつながれた，ｎ×ｍ格子のすべての格子に筋交いを２本ずついれると剛性は保たれるだろうか？

　ｎ×ｍ格子のすべてに筋交いを２本ずついれた場合の格子点数と辺数は

　　ｖ＝（ｎ＋１）（ｍ＋１）

　　ｅ＝ｎ（ｍ＋１）＋ｍ（ｎ＋１）＋２ｎｍ

　したがって，不足している辺数は

　　３ｖ−６−ｅ＝２（ｎ＋ｍ）−３−ｎｍ＝１−（ｎ−２）（ｍ−２）

　ｎ＞２かつｍ＞２の格子ならば剛性は損なわれない．１×１格子でも同様．しかし，それ以外では剛性を保つことができない．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

【４】木グラフの不足数

　木グラフではｅ＝ｖ−１が成立するから，１次元関節下では常にｄ＝０であるが，

［１］２次元関節下

　　ｄ＝２ｖ−３−ｅ＝ｖ−２

［２］３次元関節下

　　ｄ＝３ｖ−６−ｅ＝２ｖ−５

［３］ｎ次元関節下

　　ｄ＝ｎｖ−ｎ（ｎ＋１）／２−ｅ＝（ｎ−１）ｖ−（ｎ−１）（ｎ＋２）／２

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

【５】完全グラフの不足数

　それでは完全グラフＫnではどうだろうか？

　　ｖ＝ｎ，ｅ＝ｎ（ｎ−３）／２＋ｎ＝ｎ（ｎ−１）／２

［１］２次元において，

　　２ｖ−３−ｅ

に代入すると

　　２ｖ−３−ｅ＝２ｎ−３−ｎ（ｎ−１）／２

　＝−（ｎ^2−５ｎ＋６）／２＝−（ｎ−２）（ｎ−３）／２

ｎ≧３では，不足している辺数が負となり，常に剛性条件が満たされる．

［２］任意のｎ次元についても

　　ｎｖ−ｎ（ｎ＋１）／２−ｅ

に代入すると

　　ｎ^2−ｎ（ｎ＋１）／２−ｎ（ｎ−１）／２＝０

となって，常に剛性条件が満たされる．

［３］完全グラフＫm

　　ｖ＝ｍ，ｅ＝ｍ（ｍ−１）／２

をｎ次元関節の下の幾何学的安定性条件

　　ｎｖ−ｎ（ｎ＋１）／２−ｅ

に代入する．

　　ｎｖ−ｎ（ｎ＋１）／２−ｅ

　＝ｎｍ−ｎ（ｎ＋１）／２−ｍ（ｍ−１）／２

　＝（２ｎｍ−ｎ^2−ｍ^2−ｎ＋ｍ）／２

　＝−（（ｎ−ｍ）^2＋（ｎ−ｍ））／２

　＝−（ｎ−ｍ）（ｎ−ｍ＋１）／２＝０

　　ｎ＝ｍ，ｎ＝ｍ−１

で０となる．一般的には不足数≦０が成り立つことがわかる．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

【６】完全二部グラフの不足数

　完全二部グラフＫn,mではどうだろうか？

　　ｖ＝ｎ＋ｍ，ｅ＝ｎｍ

［１］２次元において，不足している辺数は

　　２ｖ−３−ｅ＝２（ｎ＋ｍ）−３−ｎｍ＝１−（ｎ−２）（ｍ−２）

　ｎ＞２かつｍ＞２の完全二部グラフならば剛性は損なわれない．１×１でも同様．しかし，それ以外では剛性を保つことができない．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝