欧拉图与哈密顿图：一笔画与全程巡视

欧拉图与哈密顿图：一笔画与全程巡视

回到哥尼斯堡的河岸边——第 1 章埋下的伏笔在这里正式揭晓。欧拉当年回答的"每座桥恰过一次能否回到原地"是一类问题的鼻祖：欧拉回路要求把每条边恰好走一遍并回到起点。一个多世纪后，另一位数学家哈密顿发明的"绕行正十二面体、每座城市恰访一次"的游戏开创了形似神异的另一类：哈密顿回路要求把每个顶点恰好访问一遍。一问边、一问点，只一字之差，命运却一在天一在地：前者有干净利落的判定定理与线性时间的构造算法，后者至今没有通用的高效判法。本章整理地图档案，本节把这对"镜像双题"并置摊开，最能看清问题定义的细微改动如何翻转整个难度世界。

欧拉图：偶度定理与 Hierholzer 算法

判定定理一句话：连通图存在欧拉回路，当且仅当每个顶点的度数都是偶数；若恰有两个奇度顶点，则存在欧拉路径（从一奇到另一奇）。两个方向的证明都轻盈：必要性看"每次进入必离开"——回路上每个顶点的进出成对，度数自然成双；充分性是构造式的，从任一点出发任意走不重复边，偶度保证走进死胡同时必然恰好回到起点，得到一个圈；若还有边没走到，图连通保证这个圈与剩余边相连，从交点再拼一个圈接上去，环环相扣直到并完所有边。

这个"拼圈"的构造就是 Hierholzer 算法：深度优先地走，走投无路（无未用边）时回退，回退路径倒序拼接即为欧拉回路。

import networkx as nx

def hierholzer(G, start):
    """Hierholzer 算法：返回欧拉回路（需先通过偶度判定）"""
    stack = [start]
    circuit = []
    while stack:
        u = stack[-1]
        unused = [v for v in G[u] if G[u][v].get("used") is None]
        if unused:
            v = unused[0]
            G[u][v]["used"] = True               # 无向边两端同标记
            G[v][u]["used"] = True
            stack.append(v)
        else:
            circuit.append(stack.pop())            # 走投无路，收进回路
    return circuit[::-1]                          # 回退序倒排

def euler_check(G):
    """欧拉判定：返回 回路/路径/均无"""
    if not nx.is_connected(G):
        return "不连通，先分块再说"
    odd = [v for v in G.nodes if G.degree(v) % 2 == 1]
    if not odd:
        return "有欧拉回路", []
    if len(odd) == 2:
        return "有欧拉路径（两端为奇度点）", odd
    return "既无回路也无路径", odd

# 哥尼斯堡的抽象图：四块陆地，奇度点过多
konigsberg = nx.Graph([("北岸","克奈普岛"),("北岸","东岸"),
    ("南岸","克奈普岛"),("南岸","东岸"),("南岸","西岸"),
    ("北岸","西岸"),("克奈普岛","西岸")])
print("七桥:", euler_check(konigsberg))

# 加一座桥把奇度配平：欧拉路径现身
fixed = konigsberg.copy()
fixed.add_edge("北岸","南岸")
status, odd = euler_check(fixed)
print("加桥后:", status, "奇度点:", odd)
circuit = hierholzer(fixed.copy(), "北岸")
print("试走一遍:", " → ".join(circuit))
​

七桥图里奇度点远超两个——欧拉当年断言"不存在"的现代复述就是这行输出。加桥配平奇度后判定翻转，算法立即给出可行的走法。工程上欧拉路径的身影密集：DNA 测序的碎片拼接把读段重叠建成图，拼接序列正是一条欧拉路径；邮递员扫街、除雪车清路的"中国邮递员问题"是它的加权变体（需要给重复路段加权配平奇度点）。

哈密顿图：镜像世界的难

把"每边一次"换成"每点一次"，世界立刻翻转。哈密顿回路是经过每个顶点恰一次的圈；存在者称哈密顿图。判定"给定图是否哈密顿"与第 8 章的着色、独立集同属难解家族——没有已知多项式算法，也没有简洁的充要刻画。旅行商问题是它的加权版：在完全图里找总权最小的哈密顿回路，运筹学的旗舰难题。

难归难，工具箱里有三样常备品。必要条件做快速排除：删去任何一组顶点，剩下的连通块数不得超过这组顶点的个数（哈密顿回路删点是链，链连通块数受限）；奇度之类的"奇偶指纹"在这里帮不上忙。充分条件做快速确认：Dirac 条件承诺，每个顶点的度数不小于顶点数一半时，哈密顿回路必然存在——条件强但验证廉价，随机稠密图轻松达标。两者之间的灰色地带交给回溯搜索：

def hamilton_path(G, start):
    """回溯搜索哈密顿路径：返回路径或 None"""
    n = len(G.nodes)
    path = [start]
    def extend(u):
        if len(path) == n:
            return True                        # 路径版：访齐全部顶点即可
        for v in G[u]:
            if v not in path:
                path.append(v)
                if extend(v):
                    return True
                path.pop()                                # 回溯
        return False
    return path if extend(start) else None

def hamilton_cycle(G, start):
    """回溯搜索哈密顿回路"""
    p = hamilton_path(G, start)
    if p and G.has_edge(p[-1], start):
        return p + [start]
    return None

dodeca = nx.Graph()                        # 一个已知哈密顿的小图（五棱柱）
dodeca.add_edges_from([(0,1),(1,2),(2,3),(3,4),(4,0),
                       (5,6),(6,7),(7,8),(8,9),(9,5),
                       (0,5),(1,6),(2,7),(3,8),(4,9)])
print("哈密顿回路:", hamilton_cycle(dodeca, 0))
​

回溯的代价在最坏情形是指数级，但配合"度数剪枝"（度数小于二的顶点直接出局，除非做端点）与"必经边推理"（度数为二者的两条边必入回路），几十个顶点的实例往往几毫秒收工——难解不等于不可解，只是没有规模化的通行证。

两题并置的方法论启示

把双题并排放在档案柜同一格，启示有二。其一，复杂度不由"长得像"决定：两题的表述几乎对偶，可解性天差地别——评价一个新问题该走哪条路，不能靠类比外观，只能靠归约证明。其二，结构条件的力量：欧拉问题被"度数奇偶"这个局部可验证的条件完全刻画，哈密顿问题的已知充分条件（如 Dirac）却强到近乎苛刻——有干净刻画的结构问题多半有多项式算法，没有的则多半沉入难解深海，这条经验规律是算法学家的地质图。

⚠️ 常见坑：对哈密顿问题硬找"充要条件"。市面流传的各种"判定法"多是必要或充分条件的误传；写代码时老实用回溯加剪枝，做理论时老实用归约，别把充分条件当判据。

💡 关键直觉：欧拉问"路怎么修才能每条都走到"，哈密顿问"人怎么走才能每处都访到"——修路看边、看度数；访点看点、看组合。视角差之毫厘，难度谬以千里。

档案的第一格归档完毕。下一格存放另一种"规整地形"：能在平面上画得不交叉的图——平面图，欧拉公式等着为它清点户口。