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本となります。

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

Search

Information

花鳥風月

Calendar

11月 « 2018年12月 » 01月
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ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。