マスログ

2020/10/30

路線・ネットワークの数学~グラフ理論への誘い(前編)~


こんにちは。和からの数学講師の岡本です。今回は「路線設計」の問題をグラフ理論の言葉で置き換える話をします。以前「グラフ理論」に関連する記事を書いたので、こちらも併せてご覧ください。

一筆書きの数学からモノクロデザインへ

先手必勝!?戦略とゲーム理論(中級編)

次の問題を考えます。

5つの街をつなぐ道路を作ります。道路を作るにあたって、以下の条件があります。
(Ⅰ)1本の道路でどこにでも移動できる。
(Ⅱ)トンネルや橋、交差点を作らない。
このような条件を満たす道路(路線)は実現できるでしょうか?

1.単純な例を考える(3つの街の場合)

 このような複雑そうな問題はまず具体例を考えてみます。そこで、比較的イメージしやすそうな3つの場合について考察します。

3つの街の場合、単純に全ての街を以下のようにつなぐことで、条件は全て満たされます。

2.単純な例を考える(4つの街の場合)

次に、4つの街の場合を考えましょう。まず、単純に全ての街をつなぐことで、以下のような路線ができます。

しかしながら、このような設計では真ん中に交差点が必要になってしまいます。
そこで、対角線の道路を以下の図のように「外側にまわす」ことで、(Ⅰ),(Ⅱ)の条件を満たす路線が完成します。

3.グラフ理論の導入

複雑な場合でも統一的かつ簡潔に表現するために「グラフ」という概念を導入します。
街に対応するものを「頂点(vertex)」、道路に対応するものを「辺(edge)」と呼ぶことにします。上で考えた「路線」とは、「頂点と辺のつながりを表す図形」とみなすことができ、数学の世界ではこれを「グラフ(graph)」と呼びます。

また、\(n\)個の頂点全てを結んでできるグラフのことを「\(n\)次完全グラフ」と呼び、\(K_n\)と書きます。そして、頂点以外の点で、辺が交差しないように平面に描けるグラフのことを「平面グラフ」と呼びます。

 今回の条件(Ⅰ)はグラフ理論の言葉では「街をつなぐ路線が完全グラフである」と表現でき、条件(Ⅱ)は「街をつなぐ路線が平面グラフである」ことを意味しています。
 なお、街が3つ、4つの場合のグラフは「完全グラフかつ平面グラフ」であり、今回の問題はグラフ理論的に以下のように書き換えることができます。

5次完全グラフ\(K_5\)は平面グラフであるか?

グラフとは「頂点とそのつながりの情報そのもの」であり、実際は「上を通る」「下を通る」「交差点」などは関係ありません。この意味で「路線(道路)」と「ネットワーク」に違いがあわれます。グラフ理論に近い対象はどちらかというと「ネットワーク」です。「平面グラフ」という概念を持ってくることにより、物理的な「路線(道路)」のモデルをグラフ理論で考えることができるのです。

4.さいごに

いかがでしたでしょうか?今回は路線の問題を「グラフ理論」を使って表現してみました。
しかし、まだ問題に対する回答は得られていません。次回はグラフ理論を使って、5つの街に条件(Ⅰ),(Ⅱ)を満たす道路が作れるかどうかの結論を出します!しかもその議論の中では大数学者レオンハルト・オイラーの名前も登場します!(オイラーに関する記事はこちら↓)

数学の現人神(アラヒトガミ)の一人、レオンハルト・オイラー 一体何がすごいのか

次回もお楽しみに!

和からではご自身のペースで学びたいことを学びたいだけ学ぶことができます。算数や数学の苦手意識克服、お仕事で使う計算から実務に役立つデータ分析まで、幅広く対応いたします。ご興味がある方はぜひ一度無料セミナー、無料個別カウンセリングをご利用ください。

●和からのセミナー一覧はこちら
●お問い合わせフォームはこちら

<文/岡本健太郎>

カテゴリー

記事一覧

Instagram

Facebook

Twitter