哥尼斯堡七桥问题与欧拉路径

# 4 块陆地 A、B、C、D 由 7 座桥相连；两块陆地之间可能有不止一座桥，所以用多重图 MultiGraph。
# 计算每个节点的度与奇数度节点个数，用 Euler 判据（奇数度节点数为 0 或 2）判断是否存在欧拉路径。
# 输出：度为 A=5, B=3, C=3, D=3；奇数度节点 4 个；不存在欧拉路径。
# 再加一座连接 B 与 C 的桥后，B、C 变为偶数度，奇数度节点降为 2 个，欧拉路径随之存在。
import networkx as nx

bridges = [("A", "B"), ("A", "B"), ("A", "C"), ("A", "C"), ("A", "D"), ("B", "D"), ("C", "D")]

for label, edge_list in [("原始七桥", bridges), ("加一座 B–C 桥", bridges + [("B", "C")])]:
    G = nx.MultiGraph()
    G.add_edges_from(edge_list)
    n_odd = sum(1 for _, d in G.degree() if d % 2 == 1)
    print("【%s】节点的度: %s" % (label, dict(G.degree())))
    print("  奇数度节点个数: %d" % n_odd)
    print("  按 Euler 判据，存在欧拉路径吗？", n_odd in (0, 2))
    print("  NetworkX 的判断:", nx.has_eulerian_path(G))

# 作图：两种情形并排，奇数度节点标红；多重边用不同弧度的曲线区分
import matplotlib.pyplot as plt
from collections import Counter

xy = {"A": (0, 0), "B": (1, 1), "C": (1, -1), "D": (2, 0)}
fig, axes = plt.subplots(1, 2, figsize=(10, 4))
for ax, (label, edge_list) in zip(axes, [("original 7 bridges", bridges), ("add a B-C bridge", bridges + [("B", "C")])]):
    G = nx.MultiGraph(edge_list)
    for (u, v), m in Counter(tuple(sorted(e)) for e in edge_list).items():
        for j in range(m):
            rad = 0 if m == 1 else (-0.25 + 0.5 * j / (m - 1))
            ax.annotate("", xy=xy[v], xytext=xy[u], arrowprops=dict(arrowstyle="-", color="0.5",
                        lw=1.6, connectionstyle="arc3,rad=%.2f" % rad))
    for n, (x, y) in xy.items():
        odd = G.degree(n) % 2 == 1
        ax.scatter(x, y, s=700, color="#d6604d" if odd else "#4393c3", zorder=3)
        ax.text(x, y, "%s\nk=%d" % (n, G.degree(n)), ha="center", va="center", color="white", fontsize=9, zorder=4)
    n_odd = sum(d % 2 for _, d in G.degree())
    ax.set_title("%s: %d odd nodes, Euler path = %s" % (label, n_odd, nx.has_eulerian_path(G)), fontsize=10)
    ax.set_xlim(-0.4, 2.4); ax.set_ylim(-1.4, 1.4); ax.axis("off")
plt.tight_layout(); plt.show()