■筋交い構造(その4)

[Q]3×3格子の場合の最少筋交い数は5である.筋交いをどこに配置すべきか?

 最少筋交い数は5であるから,9C5組を虱潰しに調べればわかるだろうが,それでは労多くして益少なしである.

===================================

 格子の補強は完全2部グラフK3,3のサブグラフとして表現することができる.そして,サブグラフが木である場合(回路を持たない場合)(かつその場合に限り)最少であることがわかっている.

 また,位数kの同形でない木の総数g(k)を与える公式は知られていないが,位数6の同型でない木グラフの総数はg(6)=6であることがわかっている.(なお,位数6の同等でない木グラフの総数は1296である.)

 しかし,ここで必要となるのは,位数6の同型でない木グラフの総数ではなく,その完全2部グラフK3,3版であるから,話は込み入ってくる.

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

 筋交いをどこに配置すべきか,実際に検討してみることにするが,行列とグラフには強い関連があり,頂点番号の付け替えは各行(または各列)の置換に対応する.対称性を考えると第1行(列)と第2行(列),第3行(列)と第2行(列),その組み合わせについて調べてみることになる.

[1]3−1−1の置換

  ■■■   ■■■   □■□

  ■□□ → □■□   ■■■

  ■□□   □■□   □■□

  ■■■   ■■■   ■■■   □■□   ■□□

  ■□□ → □■□   ■□□   ■■■   ■■■

  □■□   ■□□   □□■   ■□□   □□■

[2]2−2−1の置換

  ■■□   ■■□   ■□■   □■■   ■■□

  ■□■ → □■■   ■■□   ■■□   ■□□

  □■□   ■□□   □□■   ■□□   □■■

  ■■□   ■□■

  ■□■   □□■

  □□■   ■■□

 しかし,これでとり漏らしがないかはまったく自信がもてない.

  □■□

  ■■■

  □■□

は剛であるが,

  ■□■

  □■□

  ■□■

は剛でないことに注意されたい.

===================================