金曜日, 3月 11, 2016

グラフ理論(ケーニヒスベルクの橋)関連:メモ


                 (リンク:::::::::数学論理学

グラフ理論(ケーニヒスベルクの橋)関連:メモ

http://nam-students.blogspot.jp/2016/03/blog-post_11.html(本頁)

◎〇20160310 AlphaGo◉ div style="line-height: 9pt;"

http://nam-students.blogspot.jp/2016/03/20160310-alphago.html



 /I\
/ I \
\ I  \
 \I___\
 /I   /
/ I  /
\ I /
 \I/



グラフ理論からネットワーク理論へ

エルデシュ数(エルデシュすう、Erdős number)またはエルデシュ番号とは、数学者同士、あるいはもっと広く科学者同士の、共著論文による結び付きにおいて、ハンガリー出身の数学者ポール・エルデシュとどれだけ近いかを表す概念である。エルデシュに共著論文が非常に多いことから、その友人たちによって、敬意とユーモアを込めて考え出された。今日では科学者のコミュニティにおいてよく知られており、エルデシュと近いことが名誉であるかのように半ば冗談めいて語られる。

問題編集

18世紀の初めごろにプロイセン王国の首都であるケーニヒスベルク(現ロシア連邦カリーニングラード)という大きな町があった。この町の中央には、プレーゲル川という大きな川が流れており、七つの橋が架けられていた。あるとき町の人が、次のように言った。

「このプレーゲル川に架かっている7つの橋を2度通らずに、全て渡って、元の所に帰ってくることができるか。ただし、どこから出発してもよい」

町の人が言ったことはできるだろうか。

グラフ理論との関連編集

1736年レオンハルト・オイラーは、この問題を以下のグラフに置き換えて考えた。

7 bridges.svg → Königsberg graph.svg

このグラフが一筆書き可能であれば、ケーニヒスベルクの橋を全て1度ずつ通って戻ってくるルートが存在することになる。

そして、オイラーは、このグラフが一筆書きできないことを証明し、ケーニヒスベルクの問題を否定的に解決した。

この問題は論理的に考えれば確かに不可能であるが、実は屁理屈気味だが解法が存在している。それは、「川の源流まで辿る、という大きな迂回ルートを通る」ことで経路を一本増やすことができ、解答可能になる。これは問題の文章には一切違反していないので正当な回答とみなせなくもないが、いわゆる「題意」からは外れる。

一筆書き可能かどうかの判定法編集

ある連結グラフが一筆書き可能な場合の必要十分条件は、以下の条件のいずれか一方が成り立つことである(オイラー路参照)。

  • すべての頂点の次数(頂点につながっている辺の数)が偶数 →運筆が起点に戻る場合(閉路
  • 次数が奇数である頂点の数が2で、残りの頂点の次数は全て偶数 →運筆が起点に戻らない場合(閉路でない路)

一筆書きの解法編集

  • すべての頂点の次数が偶数 →ある頂点から出発し、元の頂点に戻り、さらにその頂点から出発し、元の頂点に戻る順路を考える。もし、まだ通っていない経路があれば、先ほどの順路からある頂点を選び、そこから寄り道をしてその頂点に戻ってくる順路を付け足したものに修正する。その修正を繰り返せばよい。
  • 次数が奇数の頂点の数が2で、残りの頂点の次数は全て偶数 →ある奇点から出発し、もう一方の奇点へ抜ける順路を考える。もし、まだ通っていない経路があれば、先ほどの順路からある頂点を選び、そこから寄り道をしてその頂点に戻ってくる順路を付け足したものに修正する。その修正を繰り返せばよい。

グラフ理論(グラフりろん、graph theory)は、ノード節点[英 1]頂点[英 2])の集合とエッジ[英 3])の集合で構成されるグラフ[英 4]に関する数学の理論である。グラフ (データ構造) などの応用がある。


グラフ理論の基礎 | 高校数学の美しい物語

http://mathtrain.jp/graph

グラフ理論は組み合わせの問題を簡潔に記述するための道具です。

グラフとは

・グラフとは,点の集合 V と二点間を結ぶ辺 E の集合のペアで,GVE と表します。点のことを頂点,ノード(vertex,node),辺のことを枝(arc,edge)などと呼びます。

グラフ
  • グラフは組み合わせ的な構造を表すモデルです。そのため,図における二つのグラフは同じモデルとみなします。頂点の置き方やどのような曲線で結ばれているかは考えません(図では分かりやすくするために頂点に色をつけています)。
  • 辺に方向性があるようなグラフを有向グラフ,方向性がないようなものを無向グラフと呼びます。図は無向グラフです,有向グラフでは辺を矢印で表します。問題によって使い分けましょう。

グラフ理論と数学オリンピック

数学オリンピックではグラフ理論を使うとスッキリと記述できる問題が多く出題されています。これらの問題はグラフ理論を全く知らなくても解けるようになっており.グラフ理論の難しい定理を知っていて有利になる場面は少ないです。

しかし,グラフ理論を知っていると問題を簡潔な言葉で記述することができ,見通しがよくなります。「人間」とか「知り合い」などの日本語で議論するよりもグラフを描いて頂点と辺で議論した方が圧倒的に分かりやすいのです。

そのような意味で,最低限のグラフ理論の概念と用語を知っていると数学オリンピックでは有利です。

他にもいくらでもあります!

グラフ理論で重要な用語

感覚的にはごく自然な用語たちです。いろいろな概念を簡潔に表現することができるので便利です。

  • (頂点の)次数:頂点から出ている辺の本数。
  • 連結:どの頂点からどの頂点へも辺を伝っていくことができるようなグラフ。
  • パス(道):隣接する頂点をたどったもの。ただし,「同じ頂点を二回通るのはダメ」とすることが多い。
  • サイクル(閉路):隣接する頂点をたどったもので,始点と終点が同じもの。ただし,同じ辺を二回通るのはダメ。

重要なグラフ

数学オリンピックの問題でもしばしば登場するグラフたちです。

・木:閉路が存在しない連結なグラフ。

様々なグラフ
  • 二部グラフ:頂点が二つのグループに分かれており,異なるグループの頂点間にのみ辺が引かれているグラフ。
  • 完全グラフ:全ての頂点間に辺が引かれているグラフ。頂点数 n の完全グラフを Kn と書く(図は K5)。
  • 完全二部グラフ:二部グラフで,異なるグループの頂点間には全て辺が引かれているグラフ。グループの頂点数がそれぞれ mn である完全二部グラフを Kmn と書く(図は K32)。

・オイラーグラフ:一筆書きできるグラフ。
→オイラーグラフの定理とその証明





1 Comments:

Blogger yoji said...

ガラスの「形」を数学的に解明
~トポロジーで読み解く無秩序の中の秩序~




 |           /
 |          /
 |         /
消|        /       重
滅|       /        複
 |      /         度
 |    。/  
 |  。。/
 |   /   液体
 |__/_______________
0       発生


 |           /
 |          /
 |      BO /
消|CP     。/       重
滅|   CO。。/        複
 |      /         度
 |    。/  
 |CT。。/
 |   /   ガラス
 |__/_______________
0       発生


CP  
    ●__●
   /   \
 ー●    /
|     ●
●    / 
|_●_●

CT

    O__O
   /   \
 ーO    /
|     O
●\   / 
|_●_O

CO

    O__O
   /   \
 ー●    /
|/|   O
●\|  / 
|_●_O


BO 
    O__O
   /   \
 ー●    /
|/ \  O
●\  \/ 
|_●_●

________________

参考:
http://stat.scphys.kyoto-u.ac.jp/pub/jps07.pdf



【数理物理学/固体物理学】ガラスの「形」を数学的に解明 トポロジーで読み解く無秩序の中の秩序 [無断転載禁止]©2ch.net
1 :
もろ禿HINE! ★@無断転載は禁止
2016/06/14(火) 12:23:18.75 ID:CAP_USER
共同発表:ガラスの「形」を数学的に解明~トポロジーで読み解く無秩序の中の秩序~
http://www.jst.go.jp/pr/announce/20160614/index.html


ポイント
東北大学 原子分子材料科学高等研究機構(WPI-AIMR)の平岡 裕章 准教授、中村 壮伸 助教を中心とした研究グループは、統計数理研究所(ISM)および科学技術振興機構(JST)と共同で数学的手法を開発することで、ガラスに含まれ る階層的な幾何構造を解明することに成功しました。

周期性を持たないガラスの原子配置構造は非常に複雑であり、その構造を理解するために、適切な記述法を開発することが長年求められていました。本研究グ ループは、トポロジー注1)を応用することでこの問題を解決することに成功しました。さらに、ここで開発された数学手法は物質に特化しない普遍的なもので あることから、情報ストレージや太陽光パネルなどのガラス開発に加え、マテリアルズインフォマティックス注2)なども含めた幅広い材料開発への応用が期待 されます。

本成果は、平成28年6月13日の週(米国東部時間)に、米国科学アカデミー紀要(PNAS)「Proceedings of the National Academy of Sciences」オンライン速報版に掲載されます。


(以下略)
名無しのひみつ@無断転載は禁止
2016/06/14(火) 12:40:45.21 ID:20q5TdAn
無秩序にも「秩序」がある。それを数学的に記述するんだね。
3 :
名無しのひみつ@無断転載は禁止
2016/06/14(火) 12:41:22.81 ID:dxSRlr6i
全然分からんがや
4 :
名無しのひみつ@無断転載は禁止
2016/06/14(火) 12:48:43.97 ID:iKII4TRq
材料系は東北大学強いなぁ
5 :
名無しのひみつ@無断転載は禁止
2016/06/14(火) 12:52:15.54 ID:4nJtOAw1
http://www.jst.go.jp/pr/announce/20160614/icons/zu1.jpg

意外に面白いな。

> 純粋に「データの形」を扱う今回の手法は、ガラスに限らないその他の材料やより一般のデータ解析への応用も可能とします。
> 膨大な原子配置データや実験画像データに対するマテリアルズインフォマティックスへの展開や、ビッグデータ解析へブレークスルーをもたらす手法に発展することが予想されます。

発展性もある。

1:29 午前  

コメントを投稿

Links to this post:

リンクを作成

<< Home