グラフ理論

0.はじめに 大学でグラフ理論を勉強する機会があったので学んだことを書きなぐっていきます。グラフ理論は情報工学界隈に限らず、広く一般的に使われている学問領域です。また今回取り上げる内容は表題のとおり、入門中の入門ということで聞いたことがあるという方もいらっしゃることかもしれません。とはいえ、グラフ理論を勉強していくうちにその魅力にとりつかれ、しっかり学んで血となり肉としたいと思い、自分のために勉強したことを書き残していきます。 cf. 帝京大学理工学部(通信教育課程)の社会人大学生1年目をふりかえる | gkzz.dev 1.前提 グラフ理論を勉強する難しさをあげるとしたら、書籍やウェブサイトなど資料によって、「同じことを言っているが、使っている用語が異なる」、さらには「用語のスコープが異なる」こと e.g. ノードと同じ意味：節点、頂点、点 e.g. エッジと同じ意味：枝、辺、線 そこで、本ページではいわゆる用語の定義は参考資料を掲載する程度としたい 本書の位置づけは、「グラフ理論を勉強するとどういった用語を目にすることになるのか？」という、グラフ理論入門の入門とする 2.「グラフ理論」でいわれている「グラフ」とは？ ノードの集合とエッジの集合を用いて様々な現象をモデル化したもの ノードは節点、頂点、点ともいう エッジは枝、辺、線ともいう 株価チャートのようなものではない 数字が連続的ではなく、「飛び飛び（離散的）」 2-1.「グラフ」を使って抽象化された一例 電車の乗換案内アプリ 電車の乗換案内アプリを使う目的は、現在地から目的地までの最短経路を知ること ただし、「コスト（グラフ理論的には『重み』）」をキョリ、交通費、交通機関の乗り換え回数などどれにするか？ によって答えは変わる！ 2-2.グラフの構成要素であるノードやエッジは電車の乗換案内アプリでは、どれに該当するか ノード：駅 エッジ：線路や駅と駅を結ぶ道路 重み：移動コスト（キョリ、交通費、交通機関の乗り換え回数など） 参考: 例題で学ぶグラフ理論 | 安藤 清, 土屋 守正, 松井 泰子 |本 | 通販 | Amazon グラフ (離散数学) - Wikipedia 離散数学とは - コトバンク 3.「グラフ理論」を勉強するとなにがうれしいか 検討対象が膨れ上がってしまうような 「組み合わせ爆発」が起きてしまう問題に対する「向き合い方」 をおさえておくことができる！ 後述するオイラーグラフ、ハミルトングラフなど典型的なグラフ構造は、離散的アプローチをするうえでの武器となる いわゆる「一筆書きできるかどうか」の判断も、ルートをしらみつぶしに調べ上げることなくできる 4....