【１】筋交い問題

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

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

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

［Ｑ］一般に，ｎ×ｍ格子の最少筋交い数はいくつになるだろうか？　また，筋交いをどこに配置すべきか？

［Ａ］格子の補強は完全２部グラフＫn,mのサブグラフとして表現することができる．そして，

［定理１］サブグラフが互いに連結されている場合（かつその場合に限り）剛である．

［定理２］サブグラフが木である場合（回路を持たない場合）（かつその場合に限り）最少である．

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

【２】冗長性

　木グラフの頂点と辺の関係は

　　ｖ−ｅ＝１

で与えられる．また，ｖ＝ｎ＋ｍであるから，最少筋交い数は

　　ｎ＋ｍ−１

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

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

【３】木グラフ

　グラフとは点（頂点ｖ）とそれらを結ぶ線（辺ｅ）とからできている１次元図形のことであるが，そのうち，閉路を含まない連結グラフのことを木（グラフ）と呼ぶ．

　同型でない木グラフの総数をｇ（ｋ）とおくと

　　位数　　：１，２，３，４，５，６，　７，　８，　９，　１０，　１１，１２，　　　１３，・・・，ｋ，・・・

　　ｇ（ｋ）：１，１，１，２，３，６，１１，２３，４７，１０６，２３５，５５１，１３０１，・・・，ｇ（ｋ），・・・

となる．

　ここでは，木グラフの総数ｇ（ｋ）の数え上げでみることにするが，１８５７年，ケーリーは知り合いの化学者からの依頼でＣkＨ2k+2の構造異性体の数を数えようとしていたときに多くの「木グラフ」の性質を発見した．

　木の性質のひとつとして，木の頂点数をｖ，辺数をｅとすると

　　ｖ＝ｅ＋１

が成り立つが，これはオイラーの定理：ｖ−ｅ＋ｆ＝１においてｆ＝０としたものである．すなわち，連結でありかつ閉路を含まないという必要十分条件を満たしていて，飽和炭化水素の場合，ｖ＝３ｋ＋２であるからｅ＝３ｋ＋１で与えられるという意味にほかならない．

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