七桥问题：一支远征队的诞生

七桥问题：一支远征队的诞生

普雷格尔河穿城而过，把哥尼斯堡分成互不相连的岸与岛，桥就架在这些岸与岛之间。市民们散步时争论出一个悬赏题目：存不存在一种走法，把每座桥恰好走过一遍，又能回到出发的地方？这道题在城里流传了很久，谁也说服不了谁，直到欧拉把它接到手上。他没有去现场踩点，而是做了一件在那个年代近乎大胆的事——把陆地压缩成点，把桥压缩成线，问题立刻露出了骨架。本节是全册的起点：我们要完整重演这次抽象与论证，因为"把问题化成图"正是图论远征队的第一步行军。

一、欧拉看到了什么

先看原始地形。哥尼斯堡的两道河湾围出四块陆地：北岸、南岸、河心岛与大岛。桥连接着这些陆地，有些陆地之间架了不止一座桥。市民的问题用今天的语言说就是：找一条经过每条边恰好一次的回路。

欧拉的洞察分两层。

第一层：桥的长度、陆地的形状、街道的曲直，通通与问题无关。散步者只关心"从哪块陆地出发、过哪座桥、到达哪块陆地"。于是四块陆地压缩成四个顶点，桥压缩成连接顶点的边，多座桥变成多重边——原来的城市地图变成了一个由四个顶点、若干条边构成的多重图。

第二层：一旦进入图的世界，问题就与几何无关了。顶点画成三角形还是圆点、边画成直线还是弧线，都不影响答案。剩下的只有连接结构。这种"只看连接、不看度量"的眼光，正是图论与几何学的分水岭，也是它后来能通吃社交网络、芯片布线、分子结构的原因。

抽象前后的对照

二、论证：为什么不可能

现在用图的语言推理。设想真的存在一条回路，把每条边恰好经过一遍。考察任意一块陆地对应的顶点：散步者每次"进入"这块陆地，必须紧接着"离开"（因为要回到起点，途中的每次到达都得再出发）。换句话说，与该顶点相连的桥必须成对出现——进一次配出一次。所以回路存在的必要条件是：每个顶点连接的桥数都是偶数。

哥尼斯堡的实际结构里，四块陆地连接的桥数分别是奇数、奇数、奇数、奇数——全部不满足。结论：这样的散步路线不存在。欧拉的论证没有构造任何路线，却回答了所有可能的路线，这正是数学证明的力量；而"每个顶点度数为偶"这个条件，后来被证明也是回路存在的充分条件，构成欧拉回路判定定理，我们会在第 9 章的欧拉图一节正式立卷。

这段论证还送给全册一件武器：顶点的度。下一节会把度系统化，并用"所有顶点度数之和等于边数的两倍"这一定理做数据校验。

三、把七桥装进 Python

用 networkx 重建这张多重图，验证历史结论。注意用 MultiGraph 而不是普通 Graph，因为两岸之间存在并行的多座桥。

import networkx as nx

# 顶点：四块陆地；边：桥（平行边用 MultiGraph 保留）
G = nx.MultiGraph()
lands = ["北岸", "河心岛", "大岛", "南岸"]
G.add_nodes_from(lands)
bridges = [
    ("北岸", "河心岛"), ("北岸", "河心岛"),      # 北岸与河心岛之间的桥
    ("南岸", "河心岛"), ("南岸", "河心岛"),      # 南岸与河心岛之间的桥
    ("河心岛", "大岛"),
    ("北岸", "大岛"), ("南岸", "大岛"),
]
G.add_edges_from(bridges)

print("陆地数:", G.number_of_nodes(), " 桥数:", G.number_of_edges())
for land in lands:
    print(f"{land} 的度 = {G.degree(land)}")
​

运行后各顶点的度依次为奇数、奇数、奇数、奇数，与史料记载一致。接着写一个判定函数，把欧拉的必要条件变成可复用的工具：

def has_eulerian_circuit(G):
    """回路判定：每个顶点的度都必须是偶数（这里同时要求图连通）"""
    if not nx.is_connected(G):
        return False, "图不连通，不可能有经过全部边的回路"
    odd = [v for v in G.nodes if G.degree(v) % 2 == 1]
    if odd:
        return False, f"存在奇度顶点 {odd}，回路不存在"
    return True, "所有顶点度数均为偶数，回路存在"

ok, msg = has_eulerian_circuit(G)
print(msg)
# 奇度顶点过多，散步者的悬赏无人能领

# 反例：把其中一座桥拆掉改成偶度会怎样？构造一个满足条件的迷你图验证判定器
H = nx.MultiGraph([(1, 2), (2, 3), (3, 4), (4, 1), (1, 3), (2, 4)])
print(has_eulerian_circuit(H))   # 全偶度且连通 → 回路存在
print(nx.has_eulerian_path(G))   # networkx 还能判定"不回起点"的欧拉通路
​

第二个函数展示了同一定理的另一半：若恰有两个奇度顶点，则存在从其中一点出发、到另一点结束的欧拉通路（不回到起点）。市民们退一步的愿望——不回家也行，只要每座桥走一遍——倒是可以在合适的桥数组合下实现。

四、这次抽象留下了什么

七桥问题的价值远超一道趣题。它确立的范式贯穿全册：把研究对象抽象成顶点与边，把问题翻译成图的性质，再用推理或算法作答。后来的化学家数分子里的环、电信工程师规划线路、社会学家分析人际网络，走的都是同一条路。

值得再咀嚼一遍的是欧拉面对"无限多种走法"时的姿态。愚公式的做法是列清单：把每条候选路线挨个检验，理论可行、实际上毫无希望——走法的数量随桥数呈指数膨胀，列举到地老天荒也算不完。欧拉反其道行之，问了一个关于"结构"的问题：假如真有这样的路线，图必须长什么样？答案（人人偶度）是一个可以逐一核对的局部条件，四块陆地点验完毕，全局的判决就下了。这种"从枚举对象转向刻画结构"的转身，是全册反复出现的思维母题：后面的握手定理、割的定理、Hall 条件，走的都是同一条路——找到守恒量或必要条件，一击定乾坤。

⚠️ 常见误区：把七桥问题当成"最短路"问题。它要求每条边恰好用一次，与路程长短无关；如果边带长度且要求总程最短，那是另一个问题（第 9 章的旅行商 cousin，第 5 章的最短路家族）。

💡 关键直觉：判断"存在不存在"往往不需要枚举所有走法——找到守恒量（这里是"进出配对"）就能一击致命。这种思维在后面的匹配与割的定理里还会反复出现。

远征队此刻已经学会了把世界看成图。下一节把地图语言补全：顶点、边、度、通路、子图，这些词汇是所有后续战役的通用语。