一筆書きとケーニヒスベルクの橋

Q: 一筆書きとケーニヒスベルクの橋とは何ですか？

**オイラー路（Eulerian trail）**：グラフ G = (V, E) のすべての辺（枝）をちょうど1度ずつ通る小道のこと。 **オイラー閉路（Eulerian circuit）**：始点と終点が一致するオイラー路（元の場所に戻ってくる一筆書き）。 **頂点の次数（Degree）**：ある頂点に接続している辺の本数。奇数本なら**奇頂点（Odd degree vertex）**、偶数本なら**偶頂点（Even degree vertex）**と呼ぶ。

Q: 一筆書きとケーニヒスベルクの橋は社会やプログラミングでどのように使われていますか？

Fleuryのアルゴリズム & Hierholzerのアルゴリズム: 与えられたグラフから一筆書きのルート（オイラー閉路）を計算量 O(|E|) で線形時間で見つけ出すアルゴリズム。ゴミ収集車や道路清掃車がすべての道路を重複なく走る最適配送計画（VRP）の基盤モジュール。

グラフ理論の夜明け — なぜこの橋は絶対に渡りきれないのか？

この単元の発見をシェア

3行要約（Key Takeaways / AIOサマリー）

1: 1736年、天才数学者オイラーが『ケーニヒスベルクにある7つの橋を1度ずつすべて渡れるか？』という難問を数学的に完全否定
2: 実際の川や島の形を捨て『頂点と辺（グラフ）』だけに抽象化したことで、現代のネットワーク理論とグラフ理論が誕生した
3: 一筆書きができる条件は『奇数個の線が集まる頂点（奇頂点）が0個または2個だけ』のとき

なぜこれを学ぶのか？ — 現実社会とテクノロジーでの価値

Purpose & Motivation

なぜ生まれたのか？

『地図の縮尺や方角などどうでもいい。つながり（接続関係）だけが本質だ』という幾何学のコペルニクス的転回。インターネットのルーティングやGoogleマップの経路探索の原点。

身につく武器・思考力

抽象化（モデリング）の威力、グラフ理論の基本概念（次数・パス・オイラー路）、アルゴリズム的思考

実社会・ITでの活躍現場

•除雪車・ゴミ収集車・郵便配達の最短巡回ルート（中国人郵便配達問題）
•集積回路（LSI / プリント基板）の配線パターン設計（交差なし・一筆描画配線）
•DNAシーケンシング（断片化された遺伝子配列をオイラー路で復元するアルゴリズム）
•インターネットのパケットルーティングとネットワーク冗長化設計

Layer 1 — 直感・シミュレーター

画面上のケーニヒスベルクの橋（4つの陸地と7つの橋）をタップして、橋を渡ってみよう。なぜどうしても最後の1本が残ってしまうのか？さらに『橋を1本追加』すると一筆書きが可能になる奇跡を実験できます。

歴史上最も有名な一筆書きパズル（1736年）

ケーニヒスベルクの7つの橋：すべての橋を「ちょうど1度だけ」渡るルートを見つけられるか？

プレーゲル川に浮かぶ2つの島と対岸を結ぶ7本の橋。街の人々が何十年も挑戦し誰一人解けなかった謎に、若きオイラーが数学的に終止符を打ちました。

スタート地点となる陸地（A, B, C, Dのいずれか）を選んでください。

なぜ絶対に渡り切れないのか？（オイラーの証明）

直感チェック！ミニクイズ

五芒星（☆のマーク）や封筒のマーク（長方形の上に三角屋根がついた形）は一筆書きできるでしょうか？

Layer 2 — 定義・受験・証明

定義

**オイラー路（Eulerian trail）**：グラフ $G = (V, E)$ のすべての辺（枝）をちょうど1度ずつ通る小道のこと。

**オイラー閉路（Eulerian circuit）**：始点と終点が一致するオイラー路（元の場所に戻ってくる一筆書き）。

**頂点の次数（Degree）**：ある頂点に接続している辺の本数。奇数本なら**奇頂点（Odd degree vertex）**、偶数本なら**偶頂点（Even degree vertex）**と呼ぶ。

公式・数理モデル

\text{オイラーの定理（1736年）: 連結グラフ } G \text{ が一筆書き可能であるための必要十分条件} 1.\ \text{オイラー閉路（戻れる）が存在 } \iff \text{すべての頂点の次数が偶数（奇頂点数 } = 0\text{）} 2.\ \text{オイラー路（戻れない）が存在 } \iff \text{奇頂点の数がちょうど } 2 \text{ 個} \quad (\text{このとき必ず一方の奇頂点がスタート、もう一方がゴールになる})

証明・導出

**なぜ奇頂点は0個または2個でなければならないのか？**

ある頂点を『途中で通過する』とき、必ず「入る辺」で1本、「出る辺」で1本の合計2本の辺を消費する。したがって、スタートでもゴールでもない中継地点の頂点は、必ず接続する辺が偶数本（2の倍数）でなければならない。

- **始点**: 出ていく辺が1本余分に必要（奇数になりうる） - **終点**: 最後に入ってくる辺が1本余分に必要（奇数になりうる）

したがって、奇頂点は最大でも「始点」と「終点」の2個しか存在し得ない。

ケーニヒスベルクの4つの陸地の次数を調べると： - 陸地A: 5本の橋（奇数） - 陸地B: 3本の橋（奇数） - 陸地C: 3本の橋（奇数） - 陸地D: 3本の橋（奇数）

**4つの頂点すべてが奇頂点**であるため、どのように歩いても一筆書きで全橋を渡ることは絶対に不可能である（証明終了）。

押さえておきたいポイント

グラフ全体のすべての頂点の次数の総和は、必ず辺の数の2倍（偶数）になる（握手補題）
このため、いかなるグラフであっても奇頂点の個数は必ず『偶数個（0, 2, 4, 6...）』になる
一筆書きの可否を判定するだけなら、実際に線を引いて試す必要は一切なく、頂点の次数を数えるだけで一瞬で判定できる

参照基準・学習指導要領との対応

本トピックの内容・数理モデルは、文部科学省学習指導要領（算数・数学・情報）および国際標準カリキュラムに準拠し、エンジニアリング現場の実装事例と照らし合わせてMath World Lab編集部により検証・作成されています。

Layer 3 — 工学応用・現場実装

Fleuryのアルゴリズム & Hierholzerのアルゴリズム

与えられたグラフから一筆書きのルート（オイラー閉路）を計算量 $O(|E|)$ で線形時間で見つけ出すアルゴリズム。ゴミ収集車や道路清掃車がすべての道路を重複なく走る最適配送計画（VRP）の基盤モジュール。

1// グラフのオイラー路（一筆書き）判定と探索アルゴリズム
2export interface Graph {
3  vertices: string[];
4  edges: [string, string][];
5}
6
7/** 一筆書きが可能かどうかを判定 */
8export function canTraverseEulerian(g: Graph): {
9  possible: boolean;
10  type: "circuit" | "trail" | "none";
11  oddVertices: string[];
12} {
13  // 各頂点の次数をカウント
14  const degreeMap = new Map<string, number>();
15  g.vertices.forEach((v) => degreeMap.set(v, 0));
16
17  g.edges.forEach(([u, v]) => {
18    degreeMap.set(u, (degreeMap.get(u) || 0) + 1);
19    degreeMap.set(v, (degreeMap.get(v) || 0) + 1);
20  });
21
22  const oddVertices = g.vertices.filter(
23    (v) => (degreeMap.get(v) || 0) % 2 !== 0
24  );
25
26  if (oddVertices.length === 0) {
27    return { possible: true, type: "circuit", oddVertices };
28  } else if (oddVertices.length === 2) {
29    return { possible: true, type: "trail", oddVertices };
30  } else {
31    return { possible: false, type: "none", oddVertices };
32  }
33}
34
35// ケーニヒスベルクの7つの橋の定義
36export const KONIGSBERG_GRAPH: Graph = {
37  vertices: ["中州A", "北岸B", "南岸C", "東島D"],
38  edges: [
39    ["中州A", "北岸B"],
40    ["中州A", "北岸B"], // 2本目の橋
41    ["中州A", "南岸C"],
42    ["中州A", "南岸C"], // 2本目の橋
43    ["中州A", "東島D"],
44    ["北岸B", "東島D"],
45    ["南岸C", "東島D"],
46  ],
47};