グラフ理論とは（全体像）
グラフ理論は、ものとものの「つながり」を、点と線だけで表して扱う数学のこと。ここでの「グラフ」は棒グラフや折れ線グラフとは別物で、点（頂点）をつなぐ線（辺）の集まりを指す。
身近な例は路線図。駅が頂点、駅と駅を結ぶ線路が辺だ。辺に「距離」や「料金」などの重みをつければ、「いちばん安く行くには？」といった問題が解ける。
押さえる基本用語は3つ。
- 頂点 … 点（駅、地点、人など）
- 辺 … 点と点を結ぶ線（つながり）
- 次数 … その頂点につながっている辺の本数
詳しく：この3つのアルゴリズムだけ覚えれば戦える
ここが記事の心臓部。よく出る道具を整理する。
主要アルゴリズム
| 名前 | 何をする | ひとこと |
|---|---|---|
| ダイクストラ法 | 2点間の最短経路を求める | 重みが負でないときに使える |
| 最小全域木（MST） | 全頂点を最小コストでつなぐ | クラスカル法・プリム法で作る |
| 幅優先探索（BFS） | 近いところから順に探す | 最短のステップ数を求めるのに向く |
| 深さ優先探索（DFS） | 行けるところまで進んで探す | 迷路探索などに向く |
ダイクストラ法は、カーナビの「最短ルート探索」そのもの。スタートから各地点までの最短距離を順に確定していく。ただし辺の重みがマイナスだと使えない点に注意。
最小全域木（MST）は、「全部の頂点を、できるだけ少ないコストでつなぐ」問題。たとえば全部の家を最短の総延長で電線でつなぐイメージだ。クラスカル法（重みの小さい辺から順に足す）とプリム法（頂点を1つずつ取り込む）の2つの作り方がある。
次に、ひっかけ定番の2つの回路。
オイラー回路 vs ハミルトン回路
| オイラー回路 | ハミルトン回路 | |
|---|---|---|
| 1回ずつ通るのは | すべての辺 | すべての頂点 |
| イメージ | 一筆書き | 全部の地点を巡る |
| 見分けの条件 | すべての頂点の次数が偶数（連結） | 簡単な条件はなく難問 |
つまり、オイラーは「辺」を全部、ハミルトンは「頂点」を全部。一筆書き（オイラー回路）は「すべての頂点の次数が偶数なら描ける」という分かりやすい条件があるが、ハミルトン回路は簡単な判定法がなく難しい問題だ。
わかりやすく言い換えると
要するに、グラフは「点と線でかいた路線図」だ。
①ダイクストラ法 … カーナビの「最短ルートで案内」ボタン
②最小全域木 … 全部の家を最短の電線でつなぐ工事プラン
③オイラー回路 … 一筆書き（すべての線を1回ずつなぞる）
④ハミルトン回路 … すべての駅に1回ずつ立ち寄るスタンプラリー
試験のツボ
🔴 一番出る：オイラー回路とハミルトン回路の区別
①オイラー回路＝すべての辺を1回ずつ（一筆書き）
②ハミルトン回路＝すべての頂点を1回ずつ
🔴 次に出る：用途とアルゴリズムの対応
①最短経路＝ダイクストラ法（負の重みは不可）
②全頂点を最小コストでつなぐ＝最小全域木（クラスカル・プリム）
🟡 押さえると安定：探索の使い分け
①幅優先探索（BFS）＝最短ステップ数
②深さ優先探索（DFS）＝行けるところまで進む
よくある間違い
①「オイラー回路はすべての頂点を1回ずつ通る経路」→ ✗ オイラー回路はすべての「辺」を1回ずつ。すべての頂点を1回ずつはハミルトン回路。
②「ダイクストラ法は負の重みがあっても最短経路を正しく求められる」→ ✗ ダイクストラ法は重みが負でないことが前提。
③「最小全域木は2点間の最短経路を求めるためのもの」→ ✗ 最小全域木は全頂点を最小コストでつなぐもの。最短経路はダイクストラ法。
試験での出題パターン
実際の問題でたしかめてみよう。
オリジナル問題1（最短経路）
重み付きグラフで2地点間の最短経路を求めるアルゴリズムとして、正しいものはどれか。
- 辺の重みが負でないときに、最短経路を求められるダイクストラ法を用いる
- 全頂点を最小コストでつなぐ最小全域木を作るクラスカル法を用いて求める
- すべての辺を1回ずつ通れるかどうかを判定する、オイラー回路の理論を使う
- すべての頂点をちょうど1回ずつ通るハミルトン回路を求めることで解決する
解答は 1 だぜ。
2地点間の最短経路を求めるのはダイクストラ法。カーナビの最短ルート探索そのものだ。ただし辺の重みが負でないことが前提だぜ。
選択肢2の最小全域木は「全部を最小コストでつなぐ」別の問題。選択肢3のオイラー回路は一筆書きの判定。選択肢4のハミルトン回路は全頂点を巡る難問で、どれも最短経路の道具ではないぜ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✓ | 最短経路はダイクストラ法で正しい |
| 2 | ✗ | 最小全域木は全頂点をつなぐ問題 |
| 3 | ✗ | オイラー回路は一筆書きの判定 |
| 4 | ✗ | ハミルトン回路は全頂点を巡る問題 |
オリジナル問題2（オイラー回路）
オイラー回路に関する次の記述のうち、正しいものはどれか。
- オイラー回路はすべての頂点をちょうど1回ずつ通る経路のことを指している
- オイラー回路は2地点間の最短距離を求めるためのアルゴリズムのことである
- オイラー回路はすべての辺を1回ずつ通る経路で、いわゆる一筆書きにあたる
- オイラー回路は全頂点を最小コストでつなぐ木を作る方法のことを指している
解答は 3 だぜ。
オイラー回路はすべての辺を1回ずつ通る経路、つまり一筆書きだ。「すべての頂点の次数が偶数（かつ連結）」なら描ける、という分かりやすい条件があるんだ。
選択肢1は「すべての頂点を1回ずつ」でハミルトン回路の説明。選択肢2は最短経路、選択肢4は最小全域木で、どれも別物だぜ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | 全頂点1回ずつはハミルトン回路 |
| 2 | ✗ | 最短経路はダイクストラ法 |
| 3 | ✓ | 全辺を1回ずつの一筆書きで正しい |
| 4 | ✗ | 全頂点をつなぐのは最小全域木 |
オリジナル問題3（最小全域木）
最小全域木に関する次の記述のうち、正しいものはどれか。
- 最小全域木は2地点間の最短経路だけを求めるためのアルゴリズムである
- 最小全域木はすべての頂点を1回ずつ通る経路を求める方法のことである
- 最小全域木はすべての辺を1回ずつ通れるかどうかを判定するものである
- 最小全域木は全頂点を最小コストでつなぐ木で、クラスカル法などで作る
解答は 4 だぜ。
最小全域木は全頂点を最小コストでつなぐ木で、クラスカル法（重みの小さい辺から足す）やプリム法（頂点を順に取り込む）で作る。全部の家を最短の電線でつなぐイメージだ。
選択肢1の最短経路はダイクストラ法。選択肢2はハミルトン回路、選択肢3はオイラー回路の説明で、いずれも別物だぜ。
| 選択肢 | 判定 | 理由 |
|---|---|---|
| 1 | ✗ | 最短経路はダイクストラ法 |
| 2 | ✗ | 全頂点1回ずつはハミルトン回路 |
| 3 | ✗ | 全辺の一筆書きはオイラー回路 |
| 4 | ✓ | 全頂点を最小コストでつなぐ木で正しい |
まとめ
押さえどころ
- 🔴 2つの回路 ＝ オイラーは全部の「辺」（一筆書き）、ハミルトンは全部の「頂点」。
- 🔴 用途とアルゴリズム ＝ 最短経路はダイクストラ法（負の重み不可）、全頂点を最小コストでつなぐのは最小全域木。
- 🟡 探索 ＝ 幅優先（BFS）は最短ステップ数、深さ優先（DFS）は行けるところまで進む。
次に学ぶ
- アルゴリズムとデータ構造 ── グラフを探索するBFS/DFSは、キューやスタックといったデータ構造の上で動く。土台を知ると理解が深まる。
- 計算量（オーダー） ── ダイクストラ法などの「速さ」を表す考え方。アルゴリズムを選ぶ基準になる。
執筆: SikakuQuest編集部