用Python NetworkX实战图论从零图到哈密顿图的代码验证当数学公式遇上代码抽象概念突然变得触手可及。想象一下你只需几行Python命令就能让计算机自动生成各种图结构验证那些曾让你头疼的图论定理——这不是未来课堂的场景而是每个开发者现在就能掌握的技能。本文将带你用NetworkX这个神奇的图论工具包把教材上的定义变成可交互的视觉实验。1. 环境准备与基础图构建在开始图论探索之前我们需要搭建好Python环境。推荐使用Anaconda创建独立环境避免依赖冲突conda create -n graph_theory python3.9 conda activate graph_theory pip install networkx matplotlib ipythonNetworkX提供了超过20种图生成函数我们先从最基础的零图开始。零图(Empty Graph)是图论中最简单的结构只有孤立的顶点没有边import networkx as nx import matplotlib.pyplot as plt def draw_graph(G, title): plt.figure(figsize(6,4)) nx.draw(G, with_labelsTrue, node_colorlightblue, node_size800, font_weightbold) plt.title(title) plt.show() # 创建5个节点的零图 G_zero nx.empty_graph(5) draw_graph(G_zero, 零图示例)与之相对的是完全图(Complete Graph)其中每对不同的顶点都通过一条边连接。完全图的边数遵循公式无向完全图n(n-1)/2有向完全图n(n-1)用代码验证这个性质G_complete nx.complete_graph(6) print(f无向完全图边数: {G_complete.number_of_edges()}) # 输出15 DG_complete nx.complete_graph(6, nx.DiGraph()) print(f有向完全图边数: {DG_complete.number_of_edges()}) # 输出302. 图的性质验证与可视化2.1 度数定理验证图论中著名的握手定理指出无向图中所有顶点的度数之和等于边数的两倍。让我们用随机图验证G_random nx.erdos_renyi_graph(10, 0.3) degree_sum sum(dict(G_random.degree()).values()) edge_count G_random.number_of_edges() print(f度数之和: {degree_sum}) print(f边数两倍: {edge_count * 2})运行结果将完美验证这个定理。我们还可以直观地看到图的度数分布degrees [G_random.degree(n) for n in G_random.nodes()] plt.hist(degrees, binsrange(min(degrees), max(degrees)2)) plt.xlabel(度数) plt.ylabel(顶点数量) plt.title(随机图的度数分布) plt.show()2.2 连通性分析连通性是图的核心属性之一。NetworkX提供了多种方法检测图的连通性# 生成一个不连通图 G_disconnected nx.disjoint_union(nx.complete_graph(3), nx.cycle_graph(4)) print(是否连通:, nx.is_connected(G_disconnected)) # False print(连通分支数:, nx.number_connected_components(G_disconnected)) # 2 # 计算点连通度和边连通度 print(点连通度:, nx.node_connectivity(G_random)) print(边连通度:, nx.edge_connectivity(G_random))对于有向图连通性分为强连通、弱连通和单向连通DG nx.DiGraph([(1,2),(2,3),(3,1),(3,4)]) print(强连通:, nx.is_strongly_connected(DG)) # False print(弱连通:, nx.is_weakly_connected(DG)) # True3. 特殊图类的判定与生成3.1 欧拉图与欧拉回路欧拉图是指包含经过每条边恰好一次的闭合路径的图。根据欧拉定理无向图是欧拉图当且仅当所有顶点度数为偶数有向图是欧拉图当且仅当每个顶点入度等于出度def is_eulerian(G): if isinstance(G, nx.DiGraph): return all(in_deg out_deg for _, in_deg, out_deg in G.in_degree G.out_degree) else: return all(deg % 2 0 for _, deg in G.degree()) # 创建欧拉图示例 eulerian_graph nx.grid_graph([3,3]) print(是否是欧拉图:, is_eulerian(eulerian_graph)) # True # 查找欧拉回路 try: euler_circuit list(nx.eulerian_circuit(eulerian_graph)) print(欧拉回路:, euler_circuit) except nx.NetworkXError: print(该图没有欧拉回路)3.2 哈密顿图判定与欧拉图不同哈密顿图的判定至今没有找到简单的充要条件。我们可以用NetworkX实现几个常用的充分条件def hamiltonian_condition1(G): Dirac定理每个顶点度数≥n/2 n G.number_of_nodes() return all(d n/2 for _, d in G.degree()) def hamiltonian_condition2(G): Ore定理任意不相邻顶点度数之和≥n n G.number_of_nodes() for u in G.nodes(): for v in G.nodes(): if u ! v and not G.has_edge(u,v): if G.degree(u) G.degree(v) n: return False return True # 测试完全图K5 K5 nx.complete_graph(5) print(满足Dirac条件:, hamiltonian_condition1(K5)) # True print(满足Ore条件:, hamiltonian_condition2(K5)) # True虽然这些条件只能判定部分哈密顿图但结合可视化能帮助我们直观理解# 生成疑似哈密顿图 G nx.cycle_graph(10) G.add_edges_from([(0,2),(1,3),(4,7),(5,8)]) pos nx.spring_layout(G) nx.draw(G, pos, with_labelsTrue) plt.show() # 尝试寻找哈密顿回路 try: ham_cycle nx.find_cycle(G, len(G.nodes())) print(找到哈密顿回路:, ham_cycle) except: print(未找到哈密顿回路)4. 高级图论概念的代码实现4.1 平面图检测平面图是可以在平面上画出且边不相交的图。虽然平面图检测算法复杂但NetworkX提供了对Kuratowski定理的实现def is_planar_with_reason(G): is_planar nx.check_planarity(G)[0] if not is_planar: K nx.algorithms.planarity.kuratowski_subgraph(G) draw_graph(K, 非平面子图) return is_planar # 测试K5和K3,3 K5 nx.complete_graph(5) K33 nx.complete_bipartite_graph(3,3) print(K5是平面图:, is_planar_with_reason(K5)) # False print(K3,3是平面图:, is_planar_with_reason(K33)) # False4.2 图的同构判定两个图同构意味着它们具有相同的结构只是顶点标签不同。NetworkX使用VF2算法进行同构测试G1 nx.path_graph(4) G2 nx.Graph([(1,2),(2,3),(3,4)]) print(G1和G2是否同构:, nx.is_isomorphic(G1, G2)) # True # 生成同构映射 matcher nx.algorithms.isomorphism.GraphMatcher(G1, G2) if matcher.is_isomorphic(): print(同构映射:, matcher.mapping)4.3 树的性质验证树是连通的、无环的图具有许多独特性质def generate_random_tree(n): 生成随机树 return nx.random_tree(n) tree generate_random_tree(10) print(边数等于顶点数减1:, tree.number_of_edges() tree.number_of_nodes() - 1) # True print(是连通图:, nx.is_connected(tree)) # True print(无环:, not nx.cycle_basis(tree)) # True # 绘制树状结构 pos nx.nx_agraph.graphviz_layout(tree, progdot) nx.draw(tree, pos, with_labelsTrue) plt.show()在实际项目中我经常需要判断一个图是否包含特定子图结构。NetworkX的subgraph_isomorphisms方法非常实用它能找出所有满足条件的子图映射。例如检测图中是否包含4个顶点的完全子图target nx.complete_graph(4) matcher nx.algorithms.isomorphism.GraphMatcher(G_random, target) print(包含K4:, matcher.subgraph_isomorphisms())