電車の乗り換え案内と数学の意外な関係

最短の経路はどうやって見つけるか

A駅からB駅まで電車で行くのに、ケータイなどの経路検索システムで調べると、すぐに最も早い経路、最も安い経路などを教えてくれます。この便利な仕組みを支えているのが数学の一分野「グラフ理論」なのです。
ただし、グラフといっても対象となるのは棒グラフや折れ線グラフなどではありません。グラフ理論が研究対象とするグラフとは、いくつかの「点」とそれらを結ぶ「線」によって構成される図形です。

グラフと所要時間から最短経路を突き止める

電車の路線図を見れば、出発地のA駅、目的地のB駅の間に、いくつかの経路があることがわかります。グラフで考えるなら、出発地といくつかの乗換駅、そして目的地が「点」であり、各点を結ぶ路線が「線」です。こうして電車の路線図から点と線を抜き出して作ったグラフの線上に、隣り合う駅間の所要時間を書きこんでいくと、ある手順（アルゴリズム）でA駅からB駅までの最短経路がわかるのです。所要時間に運賃のデータを加えれば、最も安い経路を導き出すこともできます。

グラフの性質を考える

点と線の数が増えていくとグラフは複雑になり、面白い性質を持つものが出てきます。例えば、5点からなるグラフを考えてみましょう。まず、平面上に5つの点を書きます。この5点のうち、2点を選んで線で結んでみます。2点を選ぶ組み合わせは10通りありますので、10本順番に線を描いてみましょう。線は曲がっても構いません。先に書いた線と交差しないように頑張って書いてみましょう。実はこの5点10線からなるグラフは、交差なしに平面上に書けないという性質をもちます。5点9線までは書けるけれど、最後の1本の線はどうしてもほかの線と交差してしまうのです。
グラフは2次元の平面だけではなく、3次元の空間でも考えることができます。空間に置かれたグラフはどのような性質を持つのかを考えていくと、柔らかい幾何学とも呼ばれる位相幾何学の世界につながっていくのです。

※夢ナビ講義は各講師の見解にもとづく講義内容としてご理解ください。

※夢ナビ講義の内容に関するお問い合わせには対応しておりません。

先生情報 / 大学情報

関東学院大学理工学部情報ネット・メディアコース准教授本橋友江先生

興味が湧いてきたら、この学問がオススメ！

幾何学、情報科学　

メッセージ

私は学生時代、いろいろな講義を受けた中で、トポロジー（位相幾何学）に興味を持ちました。それがキッカケで、トポロジーやグラフ理論を研究するようになったのです。グラフ理論は数学の一分野ですが、絵を描きながら考える楽しい分野です。しかも、電車などの経路案内に代表されるような、多くの人に役立つソフト開発にも関わる学問です。おもしろい学問は高校の授業でもあるはずです。興味を持てるテーマを見つけて、ぜひ得意科目にしてください。さらに大学進学では、あなたの関心事を伸ばしていける進路を探しましょう。

関東学院大学に関心を持ったあなたは

1884年（明治17年）、関東学院は横浜山手に神学校として創立されました。長い歴史と伝統をもつ関東学院はキリスト教の優れた思想、芸術、奉仕の精神を礎に、校訓「人になれ　奉仕せよ」のもと広く世の中に貢献できる学問・知識を身につけた有能な人材の育成を目指してきました。現在では、文理にわたる学部を擁する総合大学へと発展。伝統に裏打ちされたキャンパスライフサポート、学修サポート、キャリアサポートの3つのサポート体制で学生一人一人に合わせた支援をこれからも行っていきます。