当前位置：首页 > news >正文

别再死记硬背欧拉公式了！用Python可视化平面图，5分钟搞懂n-m+r=2

news 2026/4/19 23:45:52

用Python可视化平面图：5分钟玩转欧拉公式的几何奥秘

第一次接触欧拉公式时，那个简洁的n-m+r=2让我既惊叹又困惑——为什么节点、边和面之间会存在如此精确的数学关系？直到我用代码亲手绘制出各种平面图，看着程序自动计算出的数值完美吻合公式时，一切突然变得直观起来。本文将带你用Python的NetworkX和Matplotlib，通过可视化实验揭开这个图论经典公式的神秘面纱。

1. 平面图可视化基础搭建

平面图（Planar Graph）这个看似高深的概念，本质上就是能在平面上画出且边不相交的图。理解它的最佳方式不是背诵定义，而是动手创建。我们先配置好Python环境：

# 必备库安装（已安装可跳过） !pip install networkx matplotlib

用NetworkX创建一个简单的平面图只需要几行代码。下面我们生成一个包含4个节点的环形图（cycle graph），这是最基础的平面图之一：

import networkx as nx import matplotlib.pyplot as plt G = nx.cycle_graph(4) pos = nx.planar_layout(G) # 自动计算平面布局 nx.draw(G, pos, with_labels=True, node_color='lightblue') plt.show()

运行后会看到一个完美的四边形，这就是C₄图的平面嵌入。关键点在于planar_layout函数，它会尝试找到不交叉的边排列方式。试着把节点数改为5（cycle_graph(5)），你会得到一个五边形——同样满足平面图定义。

注意：并非所有图都能用planar_layout处理，当图不是平面图时（如后文提到的K₅），这个函数会抛出异常。

2. 欧拉公式的代码验证实验

欧拉公式的魔力在于它将图的三个基本要素联系起来：节点数n、边数m和面数r。让我们设计一个实验来验证这个公式：

def verify_euler(G): n = G.number_of_nodes() m = G.number_of_edges() # 计算面数（外部面+内部面） embedding = nx.planar_layout(G) r = 2 - n + m # 由欧拉公式推导 print(f"节点数(n): {n}, 边数(m): {m}, 计算面数(r): {r}") print(f"验证n - m + r = {n} - {m} + {r} = {n - m + r}") # 可视化展示 nx.draw(G, embedding, with_labels=True, node_color='salmon') plt.show() return n - m + r == 2 # 测试不同平面图 graphs = { "三角形": nx.cycle_graph(3), "四边形": nx.cycle_graph(4), "三叉星": nx.star_graph(3), "立方体骨架": nx.cubical_graph() } for name, G in graphs.items(): print(f"\n测试图: {name}") assert verify_euler(G), "验证失败！"

运行这段代码，你会看到各种平面图的验证结果。以四边形为例：

节点数n=4
边数m=4
面数r=2（内部面+外部面）
验证：4-4+2=2

有趣的是，对于星形图（如三叉星），虽然看起来只有一个中心点，但面数计算时外部空间也算作一个面。这就是为什么即使是最简单的连通平面图也满足欧拉公式。

3. 非平面图的边界探索

不是所有图都能满足平面图条件。最著名的两个反例就是完全图K₅和完全二分图K₃,₃。让我们用代码尝试绘制它们：

def attempt_draw_non_planar(): try: K5 = nx.complete_graph(5) pos = nx.planar_layout(K5) # 这里会抛出异常 nx.draw(K5, pos, with_labels=True) plt.show() except nx.NetworkXException as e: print(f"K5绘制失败: {e}") try: K33 = nx.complete_bipartite_graph(3,3) pos = nx.planar_layout(K33) # 同样会失败 nx.draw(K33, pos, with_labels=True) plt.show() except nx.NetworkXException as e: print(f"K3,3绘制失败: {e}") attempt_draw_non_planar()

运行后会看到程序报错，这正是理论预期的结果——这些图无法在平面上无交叉地绘制。从欧拉公式的角度看：

对于K₅：

n=5，m=10
如果假设是平面图，根据推论m≤3n-6→10≤9不成立
所以K₅是非平面图

对于K₃,₃：

n=6，m=9
图中没有三角形，适用推论m≤2n-4→9≤8不成立
因此K₃,₃也是非平面图

4. 面数的可视化计算方法

理解面数r的计算是掌握欧拉公式的关键。我们可以通过以下方法直观地"看到"面的存在：

def visualize_faces(G): pos = nx.planar_layout(G) nx.draw(G, pos, with_labels=True, node_size=500) # 自动识别面（简化版） if G.number_of_nodes() > 2: faces = 2 + G.number_of_edges() - G.number_of_nodes() print(f"总面数: {faces} (包括外部面)") # 标记内部面 ax = plt.gca() ax.set_title(f"面数验证: {faces}个面", pad=20) plt.text(0.5, 0.95, f"欧拉公式: {G.number_of_nodes()} - {G.number_of_edges()} + {faces} = 2", transform=ax.transAxes, ha='center') plt.show() # 创建带内部面的图 G = nx.Graph() G.add_edges_from([(1,2),(2,3),(3,4),(4,5),(5,1),(1,3),(3,5)]) visualize_faces(G)

这段代码生成的图包含两个内部面（三角形1-3-5和四边形1-2-3-4-5）加一个外部面，共3个面。根据节点数5和边数7，确实满足5-7+3=1？等等，这里出现了问题！

实际上，面数计算需要更精确的方法。对于复杂图形，推荐使用：

from networkx.algorithms import planar_drawing def exact_face_count(G): embedding = planar_drawing.combinatorial_embedding(G) return len(embedding.faces) # 注意：仅适用于已确认的平面图

这个例子说明，手动计算面数时容易遗漏某些面。在算法竞赛中，通常使用欧拉公式反推r值更可靠。

5. 平面图判定的编程实现

如何用代码判断一个图是否是平面图？NetworkX提供了现成的方法：

def check_planarity(G): is_planar, _ = nx.check_planarity(G) print(f"图{'' if is_planar else '不'}是平面图") if is_planar: print(f"满足欧拉公式: {G.number_of_nodes()} - {G.number_of_edges()} + r = 2") else: print("违反平面图必要条件") return is_planar # 测试各种图 test_graphs = [ ("路径图P₃", nx.path_graph(3)), ("完全图K₄", nx.complete_graph(4)), ("二分图K₂,₃", nx.complete_bipartite_graph(2,3)), ("彼得森图", nx.petersen_graph()) ] for name, G in test_graphs: print(f"\n测试: {name}") check_planarity(G)

对于平面图判定，程序内部实际上使用了复杂的算法（如Boyter-Myrvold算法），但我们可以利用欧拉公式的推论快速筛选：

对于n≥3的简单连通图，检查是否满足m≤3n-6
对于没有三角形的图，检查是否满足m≤2n-4

这些条件虽然不是充分条件（如彼得森图满足m≤3n-6但实际是非平面图），但能快速排除大多数非平面图。

6. 从平面图到实际应用

平面图概念在电路板设计、交通规划等领域有重要应用。比如在PCB布线时，我们希望导线不相交：

def pcb_routing_example(): # 模拟电路元件连接 components = ["CPU", "RAM", "GPU", "SSD"] connections = [("CPU","RAM"), ("CPU","GPU"), ("GPU","SSD"), ("RAM","SSD")] G = nx.Graph() G.add_nodes_from(components) G.add_edges_from(connections) # 检查是否可平面布线 if nx.check_planarity(G)[0]: pos = nx.planar_layout(G) nx.draw(G, pos, with_labels=True, node_shape='s', node_size=1500) plt.title("PCB布线方案（无交叉）") plt.show() else: print("需要多层电路板解决交叉问题") pcb_routing_example()

这个简单例子展示了如何用平面图理论解决实际问题。当图不是平面图时，工程师就需要使用过孔（via）或多层板来实现交叉——这正是K₅和K₃,₃给我们的启示。

查看全文

http://www.jsqmd.com/news/668380/