プログラミングで数学を楽しむ会(2)に行って来ました

10/14(日)に渋谷で開催された、「プログラミングで数学を楽しむ会(2)」に行って来ました。

内容はリンク先を参照してもらうとわかるのですが「グラフ理論」でした。

グラフ理論 wikipedia

私はプログラムでデータの探索をしたりするのにグラフ理論を使ったことはありますが、付け焼刃的な使い方で、ちゃんとグラフ理論として学んだことはありませんでした。

そんな時にたまたまtwitterでこの勉強会の情報が流れてきたので参加しました。

内容としては前半1時間ほどでグラフ理論の歴史と重要な定理、後半1時間でグラフアルゴリズム（探索、ダイクストラ等）の説明を受けました。
その後は自由時間で何をやってもOKという感じでした。

グラフ理論の歴史の中では有名な”ケーニヒスベルクの橋の問題”のケーニヒスベルクの場所の説明から始まりました。

実は非常に有名な方々を排出しているすごい場所でした。
カントやヒルベルト、ミンコフスキー等など、そうそうたるメンバーでした。

先に述べた”ケーニヒスベルクの橋の問題”が不可能であることの説明の前にグラフ理論で重要な言葉の説明がありました。

頂点、辺、無向・有向グラフ、歩道、小道、道、閉小道、閉路などの説明があり、それぞれの関係の中で小道の中に道があるというつまづきやすいポイントについての説明がありました。

その後に”握手補題”についての説明がありました。

握手補題というのは連結グラフ（孤立している頂点が存在しないグラフ）において以下の式が成り立つというものです。

次数の和＝2×(辺の数)

次数：頂点につながっている辺の数

言い換えると、全ての頂点の次数を合計は、辺の数の2倍に等しいということです。

考えてみれば当たり前のことですが、今まで全く気が付かなかったので新たな発見ができてすごく良かったです。
しかも辺の数の2倍と言うことは、どんな時でも次数の和は偶数ということが言えるので、なにか応用できそうな雰囲気がかなり漂ってきますね（数学では偶奇を気にすることが多い）。

勉強会の中ではこの性質から導ける結論を幾つか述べていました。
この時、講師の人が数学をめっちゃ好きそうな感じが凄く伝わって来ました。

この後はオイラーの定理の説明や2色定理の説明がありました。

”一筆書したものは必ず2色で塗り分けられる”というのは成る程！と思いました。

続く後半ではグラフアルゴリズム入門ということで、プログラムでどのようにグラフを表現するかという説明に始まり、探索の方法や、トポロジカルソート、ダイクストラ法の説明がありました。

トポロジカルソートは初耳でしたが、結構使われてそうな（実際使われている）ものですごく勉強になりました。

その後は自由時間となりサンプルコードをｶﾞﾘｺﾞﾘして遊んでいました。

全体として、グラフ理論で使用される言葉を多く知ることができてすごく良かったです。これを取っ掛かりにして自分でも色々調べて勉強できそうです。

後は、歴史的な背景や身近なところの数学を感じることができてよかったです。

こういうのは話のネタになるので楽しいです。