FC2ブログ

年年歳歳花相似,歳歳年年人不同

自然や社会に対してふと考えてしまうときがあります。 そんな思いを少しだけ書き綴っていきたいと思います。

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。
このページのトップへ

グラフ理論の応用例

前回,グラフ理論の話題になったとき,やはり文字だけでは情報を的確に伝えるには限界があることを悟りました。無精なのはいけませんね。

グラフ理論の応用例として,わかりやすくて面白い例として次のようなものはどうでしょうか。

木造の家でゆれに対する強度を高めるために梁と梁の間に追加の梁を入れることがあります。これを筋交いといいます。筋交いが無い場合,下の図のように荷重がかかると矩形はゆがんでしまいます。


荷重によるゆがめられる枠組み



筋交いを入れるとゆがみが押さえられます。


筋交い



グラフ理論を用いると,コストを低く抑えるために必要な筋交いの最小本数を考えたり,どのように筋交いをいれると建物がつぶれてしまわないと簡単に知ることができます。

次の(A)と(B)の枠組みではどちらも筋交いは6本あります片方はゆがみが生じます。どちらがゆがむと思いますか?

(A)と(B)はどちらがゆがむでしょうか


梁の枠組みを行側から見て,それぞれr_1, r_2, r_3, r_4と呼び,列側から見てc_1, c_2, c_3と呼ぶことにします。これらをグラフの頂点とみなし,筋交いの入っている行と列の要素の組に辺を置くようにし,次のようなグラフ(2部グラフといいます)を描きます。たとえば,(A)のr_1行c_1列には筋交いがはいっていますので,2部グラフの頂点r_1とc_1は辺で接続されるように描画します。

(A)の2部グラフ



(B)の2部グラフ


ゆがまない枠組みは(A)の方で,そういう枠組みは2部グラフのすべての頂点が辺によって一つに連結して描けることが知られています。このようにすべての頂点が辺によってひとかたまりに連結しているグラフは連結グラフといいます。一方,(B)の方は接続はされていますが,2つの頂点グループに分けられてしまっていますね。こういうグラフは非連結グラフといいます。

また,最小の筋交い数は全域木(スパンニング木ともいいます)の辺の本数に等しく,すなわち

最小の筋交い数=頂点数-1

です。上の例の場合は6本となります。

グラフは,なかなかに便利だと思いませんか?
スポンサーサイト
このページのトップへ

コメント

なるほど

何となく分かりそうなそうでないような
何故、連結グラフが強いと定義されるのか?
建築で自分で家など立てた経験則で直感的には
Aになるのですが理由は説明が掛かるのです
さらに複雑になるときっと直感じゃ役に
立たないのも良く分かります。グラフ便利です。
この説明でやっと木が出てくるのか理解出来ました。
最小の定義は便利ですね。素人が家を建てると
大抵強度は必要以上になります。(能力が有る場合のみ)
小学生並みに、列と行を記号に変えるのかが
何故頂点にしないのか疑問として、、、?
あそうか、四角を一つの単位としてと書くと小学生
レベルでも理解可能です。

  • 2005/08/07(日) 18:08:50 |
  • URL |
  • 風 #-
  • [編集]

補足説明

風さん,こんにちは。

梁が折れたりジョイント部分が壊れたりすることが無いとすれば,三角形はゆがまない丈夫な形ですね。縦の柱と横の梁の部分の角度を90度に維持するためには,直角三角形を上手に利用することがよいわけです。

(A)の(r_3, c_3)には筋交いはありませんが,(r_3, c_2), (r_4, c_2), (r_4, c_3)に筋交いがあることでジョイント部分が不動となり,(r_3, c_3)に直角三角形が形成されたとみなされます。以下同様にすべての筋交いの入っていない行と列のペアにも直角三角形が形成されたとみなせますので,(A)は安定するわけです。

筋交いを入れることで直角三角形が形成されるということは,柱と梁との関係が垂直であることを保証することになります。つまり,2部グラフで接続されている頂点同士はそれらが互いに垂直であることが保証されていることを意味するといいかえてもよいでしょう。そうすると,すべての頂点が連結なグラフを描ける場合は,全体としてゆがまないことを表していることになるわけです。

ただ,今回,梁や筋交いのモデルの絵や2部グラフを描いて反省点も...。梁のモデルの方のジョイント部分と2部グラフの頂点を別の記号にすればよかったですね。同じ記号をついうっかり使ってしまい,見た方々が混乱されたのではと反省しました。

なかなかわかりやすい説明というのは難しいものですね。

  • 2005/08/09(火) 11:20:26 |
  • URL |
  • 花鳥風月 #He.JWYoo
  • [編集]

花鳥風月さん,はじめまして。
とても興味深い内容なので質問させて頂きたいのですが,なぜ(B)がゆがむのか今一理解できませんでした。具体的にどの部分がゆがむのか,ということです。
よろしければ教えてください。
あと,これに関連した参考文献などご存じでしたら,併せてお教え頂ければ幸いです。

  • 2006/07/12(水) 09:43:14 |
  • URL |
  • ban #Wq1M5Ep2
  • [編集]

返信,遅れました

banさん,はじめまして。ご質問を受けていたのを気づかず,返信が遅れてしまいました。すみません。最近,BLOGの更新もなかなか出来ず,注意散漫でした。

さて,(B)が何故ゆがむのかについてですが,直感的には筋交いのある四角形の部分を色などを塗って塗りつぶして,それ以外の部分を押しつぶすようにイメージされるとわかりやすいかもしれませんね。

(B)の例の場合,筋交いの入っている長方形は形を変えずに,筋交いの入っていない長方形だけを平行四辺形に歪ませて絵を描いてみてください。どのように歪ませることが出来るかがわかるかと思います。

参考文献についてのご質問ですが,英語ではありますが,ネットで閲覧できる参考となるであろう文献を以下に紹介しておきます。

Brigitte Servatiusさんの以下のSite
http://users.wpi.edu/~bservat/
の中の,Selected Articles にある9番目の
"Graphs, digraphs, and the rigidity of grids"
はいかがでしょうか。pdf形式のファイルをダウンロードできるようになっています。大変親切でわかりやすい説明だと思います。

  • 2006/07/21(金) 10:00:51 |
  • URL |
  • 花鳥風月 #785YtZ7g
  • [編集]

コメントの投稿

管理者にだけ表示を許可する

トラックバック

トラックバックURLはこちら
http://microcosm1996.blog12.fc2.com/tb.php/19-d8dad89c
このページのトップへ

Search

Information

花鳥風月

Calendar

09月 « 2018年10月 » 11月
Sun Mon Tue Wed Thu Fri Sat
- 1 2 3 4 5 6
7 8 9 10 11 12 13
14 15 16 17 18 19 20
21 22 23 24 25 26 27
28 29 30 31 - - -

Recent Entries

Recent Comments

Recent Trackbacks

Archives

Categories

Links

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。