【アルゴリズム】すべての「枝」を1度だけ通る一筆書き！「オイラー回路」｜情報処理問題1000本ノック

アルゴリズムや離散数学における「グラフ理論」。すべての枝（エッジ）を重複なくちょうど1度だけ通って出発点に戻る「オイラー回路」の定義と成立条件を攻略しましょう。

1. 【 問題 】：アルゴリズムとデータ構造（グラフ理論）

【 問題 】 グラフ理論における回路（閉路）に関する記述です。与えられたグラフにおいて、すべての枝（エッジ）をちょうど1度だけ通って出発点に戻ってくる回路（一筆書き可能な閉路）を何と呼ぶでしょうか？

（ア）オイラー回路（Eulerian Circuit）
（イ）ハミルトン閉路（Hamiltonian Cycle）
（ウ）最短経路（Shortest Path）
（エ）完全グラフ（Complete Graph）

2. 正解：

正解：（ア）オイラー回路（Eulerian Circuit）

3. 解説：「一筆書きで元の場所に戻れるか？」

オイラー回路（Eulerian Circuit / オイラー閉路）は、数学者レオンハルト・オイラーが解決した有名な数学問題「ケーニヒスベルクの橋のパズル」に由来する概念です。
すべての「枝（線）」を残さず一筆書きで通り、なおかつ最後に出発点へ戻ってくるルートが存在するとき、そのグラフは「オイラーグラフ」と呼ばれます。

【オイラー回路が存在する定理（必要十分条件）】 ← ココが試験の応用ポイント！

連結な無向グラフにオイラー回路が存在するための条件は、

「すべての頂点の次数（つながっている枝の数）が偶数であること」

※1つでも枝の数が「奇数」である頂点が存在する場合、スタート地点に戻るオイラー回路は絶対に作れません！

【ハミルトン閉路との見分け方】

名称	対象（何を通るか）	条件
（ア）オイラー回路	すべての「枝（エッジ）」	すべての枝をちょうど1度だけ通りスタートへ戻る。
（イ）ハミルトン閉路	すべての「頂点（ノード）」	すべての頂点をちょうど1度だけ通りスタートへ戻る。

1. 理解のコツ: 「道路清掃車」に例えてみましょう。
・オイラー回路：街の中にある「すべての道路（枝）」を、重複なく綺麗に掃除しながら走り、最後に出発点の基地に戻ってくるルートです。同じ交差点（頂点）を何度通り抜けても問題ありません。
・ハミルトン閉路：すべての「チェックポイント（頂点）」を重なりなく巡るルートです。

2. 試験対策の視点: 基本情報技術者試験や応用情報技術者試験で頻出のキーワードです。
問題文に「すべての枝を1度だけ」「一筆書き」「オイラー」とあれば、迷わずオイラー回路（オイラー閉路）を選択してください。
また、知識問題として「全頂点の次数が偶数 ➔ オイラー回路が存在する」という性質が選択肢に組み込まれることもあるため、セットで覚えておきましょう！

---

4. まとめ

「すべての枝をちょうど1度だけ通って出発点に戻ってくる一筆書き回路」。これがオイラー回路です。すべての頂点を巡る「ハミルトン閉路」との対比を完璧にしておきましょう！