用欧拉路径做 de Bruijn 图序列组装，并核对几条图论基本定理

# (1) 把一段 DNA 序列切成长度 k = 4 的重叠片段（k-mer），每个 k-mer 是一条从前 3 个碱基指向后
#     3 个碱基的有向边；拼回原序列就是在这张有向多重图中寻找欧拉路径。
# (2) 在随机图上核对：握手定理、二分图 ⇔ 无奇环、N 个节点的树恰有 N − 1 条边。
# 输出：重建的序列与原序列相同；三条定理的核对结果均为 True。
import networkx as nx

seq = "ATGGCGTGCAATGGCA"
k = 4
kmers = [seq[i:i + k] for i in range(len(seq) - k + 1)]
dbg = nx.MultiDiGraph()
for km in kmers:
    dbg.add_edge(km[:-1], km[1:])
print("k-mer 数 = 边数 =", dbg.number_of_edges(), "；(k-1)-mer 节点数 =", dbg.number_of_nodes())
print("存在欧拉路径吗？", nx.has_eulerian_path(dbg))
path = list(nx.eulerian_path(dbg))
rebuilt = path[0][0] + "".join(v[-1] for _, v in path)
print("重建序列:", rebuilt)
print("与原序列相同吗？", rebuilt == seq,
      "（序列含重复片段时，欧拉路径可能不唯一，此时组装结果存在歧义）")

G = nx.gnm_random_graph(200, 600, seed=7)
print("握手定理 Σk = 2M：", sum(d for _, d in G.degree()) == 2 * G.number_of_edges())

# 二分图 ⇔ 无奇环：环空间的基中若全是偶环，则所有环都是偶环（偶数条边的对称差仍为偶数）
T = nx.random_labeled_tree(50, seed=3)
for name, H in [("6 节点环", nx.cycle_graph(6)), ("5 节点环", nx.cycle_graph(5)), ("随机树", T), ("随机图", G)]:
    odd = any(len(c) % 2 == 1 for c in nx.cycle_basis(H))
    print("%-6s 二分图？%-5s 存在奇数环？%-5s 判据成立？%s" % (name, nx.is_bipartite(H), odd, nx.is_bipartite(H) == (not odd)))

print("树：N = %d，M = %d，M == N − 1？%s" % (T.number_of_nodes(), T.number_of_edges(),
                                         T.number_of_edges() == T.number_of_nodes() - 1))

# 作图：de Bruijn 图，边按欧拉路径的经过顺序着色（浅 → 深）
import matplotlib.pyplot as plt

fig, ax = plt.subplots(figsize=(6.4, 4.2))
pos = nx.kamada_kawai_layout(nx.DiGraph(dbg))
step = {}
for t, (u, v) in enumerate(path):
    step.setdefault((u, v), []).append(t)
simple = list(step)
nx.draw_networkx_edges(dbg, pos, ax=ax, edgelist=simple, edge_color=[min(step[e]) for e in simple],
                       edge_cmap=plt.cm.viridis, width=2, arrows=True, arrowsize=14, node_size=800,
                       connectionstyle="arc3,rad=0.12")
nx.draw_networkx_nodes(dbg, pos, ax=ax, node_color="#f7f7f7", edgecolors="0.4", node_size=800)
nx.draw_networkx_labels(dbg, pos, ax=ax, font_size=7)
ax.set_title("de Bruijn graph (k = %d); Euler path rebuilds sequence: %s" % (k, rebuilt == seq), fontsize=10)
ax.axis("off"); plt.tight_layout(); plt.show()