跳轉到

1736 歐拉與哥尼斯堡七橋問題：一個實際問題催生圖論#

案發現場#

1736 年，普魯士的哥尼斯堡（Königsberg，今加里寧格勒）。普雷格爾河穿城而過，把城市分成四塊陸地：兩岸河灘與河中兩座島。七座橋把四塊陸地連成一體——市民茶餘飯後流傳著一個懸案：

能否從某地出發，每座橋恰好走一次，再回到（或走到）出發點？

市民真的試過，沒有人成功。有人歸咎於橋的設計，有人說得看時辰。這是一個典型的「實驗」懸案——真實世界裡反覆嘗試的結果擺在眼前，卻無人能解釋為什麼不可能。當時的萊昂哈德·歐拉（Leonhard Euler, 1707–1783）已是聖彼得堡科學院最有名的數學家，他聽聞此案後，決定用全新的眼光偵查。

偵查過程#

歐拉的偵查手法是抽象——他做了一件前無古人的事：把地圖上的一切無關細節全部扔掉。

  1. 抽象出節點與邊：陸地的形狀、面積、距離都與此案無關；唯一的關鍵是「哪些陸地被哪幾座橋連接」。他把四塊陸地化約為四個節點（A、B、C、D），七座橋化約為七條邊——史上第一張「圖」（graph）就這樣誕生。
  2. 計數奇點：接著他證明了一個一般性的判準：一筆畫路線經過每個節點時，必是「進一次、出一次」成對出現（起訖點除外）。因此，連接邊數為奇數的節點（奇點）超過兩個，一筆畫必不可能。哥尼斯堡四個節點的度數分別為 5、3、3、3——四個奇點，鐵證如山：不可能。
  3. 解釋了「為什麼」：市民的無數次失敗不是運氣不好，而是結構上不可能。歐拉在 1736 年提交聖彼得堡科學院的論文〈位置幾何之解〉宣告：這個問題不屬於測量長短大小的「量」的數學，而屬於「位置」的數學——拓撲學的思想在這篇論文裡第一次現形。

結案報告#

七橋問題的結案報告，寫成了兩門數學與一整個技術時代的基礎：

  1. 圖論誕生：節點與邊的抽象成為一門新數學。日後哈密頓的環遊世界問題、樹與生成樹、四色問題（1976 年由電腦輔助證明）、最短路徑演算法（Dijkstra, 1959）接連出現。
  2. 拓撲學的先聲：「位置」的數學最終發展成拓撲學，成為二十世紀數學與相對論（1854-黎曼幾何.md）的深層基礎。
  3. 數學⇒技術的引擎：積體電路的晶片佈線本質上是圖的嵌入問題；網際網路的封包路由（1969-ARPANET.md）是最短路徑演算法的日常運轉；GPS 導航、社會網絡分析（六度分隔）、生物網路分析，全部踩在歐拉的節點與邊上。今日 Google 的 PageRank 本質上就是對網頁之「圖」做線性代數。

促進鏈分析#

  • 實驗⇒數學：哥尼斯堡市民的真實嘗試（實際問題）催生圖論——歐拉把「能不能走完」抽象成奇點計數，證明不可能。
  • 數學⇒數學：「位置」的數學發展成拓撲學，成為現代數學的基礎分支。
  • 數學⇒技術：圖論成為晶片佈線、網路路由、導航與社會網絡分析的設計引擎（1969-ARPANET.md、1965-摩爾定律.md 所代表的積體電路時代）。
  • 數學⇒實驗：圖論讓網路拓撲成為可分析的科學對象——社會網絡、蛋白質交互作用網路的實驗研究皆賴於此。

證據與工具#

# 用 Python 的圖論驗證哥尼斯堡七橋問題：奇點計數

from collections import defaultdict

# --- 第一部分：重建歐拉的圖 ---
bridges = [   # 七座橋：(陸地1, 陸地2)
    ("A", "B"), ("A", "B"),   # A-B 兩座橋（北岸連島）
    ("A", "C"), ("A", "C"),   # A-C 兩座橋（北岸連南岸）
    ("A", "D"),               # A-D 一座橋（北岸連東島）
    ("B", "D"), ("C", "D"),   # 島間兩座橋
]
graph = defaultdict(set)
deg = defaultdict(int)
for u, v in bridges:
    graph[u].add(v); graph[v].add(u)   # 無向圖
    deg[u] += 1;     deg[v] += 1       # 節點度數（連接的橋數）

print("--- 哥尼斯堡七橋：節點度數 ---")
for node in sorted(deg):
    parity = "奇點" if deg[node] % 2 else "偶點"
    print(f"節點 {node}：度數 {deg[node]} → {parity}")

# --- 第二部分：歐拉判準 ---
odd_nodes = [n for n, d in deg.items() if d % 2]
print(f"\n奇點數 = {len(odd_nodes)}（節點 {odd_nodes}）")
if len(odd_nodes) == 0:
    print("結論：0 個奇點 → 可一筆畫且可回到起點（歐拉迴路）")
elif len(odd_nodes) == 2:
    print("結論：恰 2 個奇點 → 可一筆畫，但起訖點必為這兩個奇點（歐拉路徑）")
else:
    print("結論：奇點 > 2 → 一筆畫不可能！哥尼斯堡市民的失敗是結構必然")

# --- 第三部分：一般性驗證——歐拉迴路判準在簡單圖上成立 ---
def has_euler_circuit(edges):
    g = defaultdict(int)
    for u, v in edges:
        g[u] += 1; g[v] += 1
    return all(d % 2 == 0 for d in g.values()) and len(g) > 0

square = [("a","b"),("b","c"),("c","d"),("d","a")]      # 四邊形：全偶點
print(f"\n四邊形一筆畫（回到起點）可行？ {has_euler_circuit(square)}")
tri_plus = square + [("a","c")]                          # 加一條對角線
print(f"加對角線後全偶？ {has_euler_circuit(tri_plus)} → 對角線產生兩個奇點，不可迴路")