别再死记硬背了！用Python+NetworkX快速判断欧拉图和哈密顿图（附期末真题解析）-尧图网络科技

用Python+NetworkX自动化判断欧拉图与哈密顿图的实战指南

离散数学中欧拉图与哈密顿图的判定一直是让计算机专业学生头疼的考点。传统方法依赖死记硬背定理和手工绘图验证，既低效又容易出错。本文将展示如何用Python的NetworkX库构建自动化判定工具，让代码帮你完成这些繁琐的理论验证。

1. 理论基础与工具准备

在开始编码前，我们需要明确几个核心概念：

欧拉图：包含欧拉回路（经过每条边恰好一次且回到起点）的连通图。判定条件：
- 无向图：所有顶点度数为偶数
- 有向图：每个顶点入度等于出度
哈密顿图：包含哈密顿回路（经过每个顶点恰好一次且回到起点）的图。判定条件：
- 目前没有像欧拉图那样简洁的充要条件
- 常用充分条件：Ore定理、Dirac定理等

NetworkX是Python中强大的图论分析库，安装非常简单：

pip install networkx matplotlib

基础图创建示例：

import networkx as nx # 创建无向图 G = nx.Graph() G.add_edges_from([(1,2),(2,3),(3,1),(3,4)])

2. 欧拉图判定实现

NetworkX已经内置了欧拉图判定方法，但我们还是从原理出发完整实现一遍：

def is_eulerian(G): if not nx.is_connected(G): return False if G.is_directed(): return all(G.in_degree(n) == G.out_degree(n) for n in G.nodes()) else: return all(d % 2 == 0 for n, d in G.degree())

实际应用时，可以直接使用NetworkX的is_eulerian()函数：

# 创建著名的哥尼斯堡七桥问题图 Koenigsberg = nx.Graph() Koenigsberg.add_edges_from([(1,2),(1,2),(1,3),(1,3),(1,4),(2,4),(3,4)]) print(nx.is_eulerian(Koenigsberg)) # 输出: False

提示：欧拉通路（非回路）的判定只需允许恰好两个奇数度顶点

3. 哈密顿图判定策略

由于哈密顿问题属于NP完全问题，没有已知的多项式时间算法。我们实现几种常用判定方法：

3.1 基于度数的充分条件检查

def hamiltonian_conditions(G): n = len(G.nodes()) if n < 3: return False degrees = sorted([d for n, d in G.degree()]) # Dirac定理 if all(d >= n/2 for d in degrees): return True # Ore定理 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

3.2 回溯法搜索哈密顿回路

对于小型图，可以直接搜索：

def hamiltonian_cycle(G, path=None, start=None): if path is None: path = [] nodes = list(G.nodes()) start = nodes[0] if nodes else None if start is None: return None if len(path) == len(G.nodes()): if G.has_edge(path[-1], start): return path + [start] else: return None for neighbor in G.neighbors(path[-1] if path else start): if neighbor not in path: result = hamiltonian_cycle(G, path + [neighbor], start) if result is not None: return result return None

4. 真题实战解析

让我们用代码解决几个典型的考试题目：

题目1：判断完全图K4是否是欧拉图和哈密顿图

K4 = nx.complete_graph(4) print(f"K4是欧拉图: {nx.is_eulerian(K4)}") print(f"K4是哈密顿图: {hamiltonian_conditions(K4)}")

输出结果：

K4是欧拉图: True K4是哈密顿图: True

题目2：判断二分图K3,3的哈密顿性

K33 = nx.complete_bipartite_graph(3, 3) print(f"K3,3是哈密顿图: {hamiltonian_conditions(K33)}")

输出结果：

K3,3是哈密顿图: True

5. 可视化与进阶技巧

可视化能帮助我们直观理解图的性质：

import matplotlib.pyplot as plt def draw_graph(G, title): pos = nx.spring_layout(G) nx.draw(G, pos, with_labels=True, node_color='lightblue') plt.title(title) plt.show() # 绘制彼得森图（经典非哈密顿图） Petersen = nx.petersen_graph() draw_graph(Petersen, "Petersen Graph")

对于大型图，可以考虑以下优化策略：

使用网络流算法验证某些特殊图的哈密顿性
对图进行预处理，移除度数为1的顶点
利用图的对称性减少搜索空间

6. 常见错误与调试技巧

在实际应用中容易遇到的几个问题：

连通性检查遗漏：欧拉图必须是连通的

# 错误示范 G = nx.Graph([(1,2),(3,4)]) print(nx.is_eulerian(G)) # 可能返回True，但图不连通

有向图处理不当：有向图的欧拉性需要入度=出度

DG = nx.DiGraph([(1,2),(2,3),(3,1),(1,3)]) print(nx.is_eulerian(DG)) # 需要检查每个节点的入度和出度

自环和多边处理：NetworkX默认支持这些特性，但可能影响算法结果

调试建议：

先用nx.draw()可视化图结构
打印节点度数和图的基本属性
对小规模子图进行测试

资讯详情