スマートフォンで目的地を検索すると、数秒でおすすめのルートが表示されます。
SNSを開けば、知り合いかもしれない人や興味のありそうな情報が表示されます。
ネット通販で注文した商品は、たくさんの道路や配送拠点を通って自宅まで届きます。
これらはまったく別のサービスに見えます。
しかし、その裏側には共通する考え方があります。
それが、
「点」と「線」で関係を表すグラフ理論です。
数学の「グラフ」と聞くと、棒グラフや折れ線グラフを思い浮かべるかもしれません。
しかし、グラフ理論のグラフは少し違います。
人、駅、都市、ウェブページなどを「点」で表し、それらのつながりを「線」で表します。
たったこれだけの考え方が、地図、SNS、検索、物流、通信など現代社会のさまざまな場所につながっています。
今回は、これまで学んできたグラフ理論が私たちの生活でどのように使われているのかを見ていきましょう。
そもそもグラフ理論とは？
グラフ理論の基本はとてもシンプルです。
必要なのは主に、
頂点（vertex）
と
辺（edge）
です。
例えば鉄道路線なら、
駅 → 頂点
駅と駅を結ぶ線路 → 辺
と考えることができます。
SNSなら、
人 → 頂点
友達・フォローなどの関係 → 辺
道路なら、
交差点 → 頂点
道路 → 辺
と表すことができます。
複雑な現実を「点と線」に置き換えることで、数学として分析しやすくなるのです。
始まりは「橋を一度ずつ渡れるか？」
グラフ理論の歴史で有名なのが、18世紀のケーニヒスベルクの橋の問題です。
町には川が流れ、いくつかの陸地が7本の橋で結ばれていました。
人々は、
「すべての橋を一度ずつ渡って散歩できるだろうか？」
と考えました。
数学者レオンハルト・オイラーは、町の形そのものではなく、
陸地を「点」
橋を「線」
に置き換えて考えました。
すると、複雑な地図が非常にシンプルな図になりました。
重要なのは橋の長さや町の形ではありません。
「どことどこがつながっているか」
だったのです。
この考え方がグラフ理論の出発点の一つになりました。
地図アプリは「最短ルート」をどう考える？
現在地から目的地まで行く方法は一つとは限りません。
道路が多い都市では、何十、何百という候補が考えられます。
ここでも道路網をグラフとして表現できます。
交差点を頂点、道路を辺として考えます。
さらに各道路に、
距離
移動時間
通行条件
などの情報を持たせることができます。
すると、
「出発地点から目的地点まで、どの経路のコストが小さいか？」
という数学の問題になります。
実際のナビゲーションシステムは交通情報や道路条件なども扱うため、単純な教科書の問題よりずっと複雑です。
それでも基本にあるのは、
たくさんのつながりの中から良い経路を探す
という考え方です。
SNSも巨大なグラフ
SNSをグラフとして考えてみましょう。
あなたを一つの点とします。
友達やフォローしている人も点です。
人と人との関係を線で結びます。
すると、数百人、数万人、数億人がつながった巨大なネットワークになります。
ここから、
「どの人とどの人が近い関係にあるか」
「どこに強いつながりの集団があるか」
「情報がどのように広がっていくか」
などをネットワークとして考えることができます。
もちろん、実際のSNSの推薦システムはグラフ理論だけで動いているわけではありません。
利用履歴や機械学習など、多くの技術が組み合わされています。
しかし、
人と人のつながりをネットワークとして表す
という部分では、グラフの考え方が非常に重要です。
検索エンジンではウェブページも「点」になる
インターネットには膨大な数のウェブページがあります。
ここでもグラフを作ることができます。
ウェブページ → 頂点
ページから別ページへのリンク → 辺
です。
例えば、あるページから別のページへのリンクが張られていれば、その2ページの間に関係があると考えることができます。
このようにウェブ全体を巨大なネットワークとして見ることで、ページ同士の関係や重要性を分析する考え方が生まれます。
検索エンジンは現在、非常に多くの要素を使って検索結果を決めています。
それでも、
ウェブページ同士のリンク構造を分析する
という発想は、インターネット検索の歴史において重要な考え方の一つです。
配送にも「点と線」がある
ネット通販で注文した荷物は、倉庫から突然あなたの家へ瞬間移動するわけではありません。
倉庫、配送センター、道路、配達先などを通ります。
これもグラフとして考えることができます。
倉庫・配送拠点・配達先 → 頂点
道路や輸送経路 → 辺
です。
ここで重要になるのが、
「どの順番で配送するか」
「どの車がどの地域を担当するか」
「どの経路なら時間や距離を減らせるか」
という問題です。
前回学んだ**巡回セールスマン問題（TSP）**ともつながっています。
現実の物流では車両数、荷物量、配達時間、交通状況など多くの条件があります。
そのため実際の最適化問題はさらに複雑です。
通信ネットワークにも使われる
インターネット通信もネットワークです。
スマートフォンから送ったデータは、さまざまな通信機器やネットワークを通って目的地へ届きます。
機器や接続地点を頂点、通信経路を辺と考えることができます。
もし一つの経路が使えなくなったらどうするのか。
別の経路はあるのか。
どの経路を利用すれば効率よく情報を送れるのか。
こうした問題もネットワークの考え方と深く関係しています。
私たちが普段意識しないところでも、「点と線」の数学は働いているのです。
13回までの内容が全部つながる
ここまでのシリーズを振り返ってみましょう。
オイラー路
すべての「辺」を一度ずつ通れるか？
ハミルトン路
すべての「頂点」を一度ずつ訪れられるか？
巡回セールスマン問題
すべての場所を回るルートの中で、より短いルートはどれか？
四色定理
隣り合う頂点に同じ色を使わず、平面グラフを最大4色で塗り分けられるか？
一見すると違う問題ですが、すべて、
頂点と辺の関係を調べる数学
です。
一つの基本的な考え方から、まったく違う問題を扱えるのがグラフ理論の面白さです。
【1分チャレンジ】あなたならどの道を選ぶ？
小さな町を考えてみましょう。
AからEへ行きます。
道の移動時間は次の通りです。
A → B：4分
A → C：7分
B → C：2分
B → D：5分
C → D：1分
C → E：6分
D → E：3分
さて、
AからEまで最も短い時間で行けるルートはどれでしょうか？
少し考えてから答えを見てください。
答え
A → B → C → D → E
です。
必要な時間は、
4 + 2 + 1 + 3 = 10分
です。
A → C → D → Eなら、
7 + 1 + 3 = 11分。
A → B → D → Eなら、
4 + 5 + 3 = 12分です。
たった5地点でも複数のルートがあります。
これが数千、数百万の地点になったらどうでしょう？
コンピューターの力が必要になる理由が少し見えてきます。
グラフ理論の本当の面白さ
グラフ理論で大切なのは、難しい記号を覚えることだけではありません。
複雑なものから「つながり」だけを取り出して考えること
です。
駅の名前を消しても、
道路の景色を消しても、
SNSのプロフィール写真を消しても、
「何と何がつながっているか」という構造は残ります。
現実の余計な情報を取り除き、本当に必要な関係だけを見る。
これが数学の強力な考え方です。
30秒で復習
今日のポイントは5つです。
① グラフ理論では対象を「頂点」と「辺」で表す。
② 地図や道路はネットワークとして表現できる。
③ SNSでは人と人の関係をグラフとして考えられる。
④ ウェブページや通信、物流もネットワークとして考えられる。
⑤ 複雑な現実を「つながり」に変えると、数学で分析しやすくなる。
一つだけ覚えるなら、
「世界は点と線に置き換えると見え方が変わる。」
です。
まとめ
グラフ理論は、18世紀の橋の問題から始まったシンプルなアイデアが、現代のさまざまな技術につながっている数学分野です。
地図、交通、SNS、検索、物流、通信。
一見まったく違う世界でも、
「何と何がつながっているか？」
という視点で見ると共通した構造が見えてきます。
そして、これまで学んだオイラー路、ハミルトン路、巡回セールスマン問題、四色定理も一本の線でつながります。
次にスマートフォンでルート検索をするとき、少しだけ思い出してみてください。
画面の向こう側には、私たちには見えない巨大な「点と線」の世界があります。
次回予告
第15回｜最短経路問題とは？カーナビはどうやって一番近い道を見つけるのか
次回は「A地点からB地点まで一番短い道」を探す数学に一歩踏み込みます。
