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

用Python可视化平面图5分钟玩转欧拉公式的几何奥秘第一次接触欧拉公式时那个简洁的n-mr2让我既惊叹又困惑——为什么节点、边和面之间会存在如此精确的数学关系直到我用代码亲手绘制出各种平面图看着程序自动计算出的数值完美吻合公式时一切突然变得直观起来。本文将带你用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_labelsTrue, node_colorlightblue) plt.show()运行后会看到一个完美的四边形这就是C₄图的平面嵌入。关键点在于planar_layout函数它会尝试找到不交叉的边排列方式。试着把节点数改为5cycle_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_labelsTrue, node_colorsalmon) 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), 验证失败运行这段代码你会看到各种平面图的验证结果。以四边形为例节点数n4边数m4面数r2内部面外部面验证4-422有趣的是对于星形图如三叉星虽然看起来只有一个中心点但面数计算时外部空间也算作一个面。这就是为什么即使是最简单的连通平面图也满足欧拉公式。3. 非平面图的边界探索不是所有图都能满足平面图条件。最著名的两个反例就是完全图K₅和完全二分图K₃,₃。让我们用代码尝试绘制它们def attempt_draw_non_planar(): try: K5 nx.complete_graph(5) pos nx.planar_layout(K5) # 这里会抛出异常 nx.draw(K5, pos, with_labelsTrue) plt.show() except nx.NetworkXException as e: print(fK5绘制失败: {e}) try: K33 nx.complete_bipartite_graph(3,3) pos nx.planar_layout(K33) # 同样会失败 nx.draw(K33, pos, with_labelsTrue) plt.show() except nx.NetworkXException as e: print(fK3,3绘制失败: {e}) attempt_draw_non_planar()运行后会看到程序报错这正是理论预期的结果——这些图无法在平面上无交叉地绘制。从欧拉公式的角度看对于K₅n5m10如果假设是平面图根据推论m≤3n-6→10≤9不成立所以K₅是非平面图对于K₃,₃n6m9图中没有三角形适用推论m≤2n-4→9≤8不成立因此K₃,₃也是非平面图4. 面数的可视化计算方法理解面数r的计算是掌握欧拉公式的关键。我们可以通过以下方法直观地看到面的存在def visualize_faces(G): pos nx.planar_layout(G) nx.draw(G, pos, with_labelsTrue, node_size500) # 自动识别面简化版 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}个面, pad20) plt.text(0.5, 0.95, f欧拉公式: {G.number_of_nodes()} - {G.number_of_edges()} {faces} 2, transformax.transAxes, hacenter) 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-731等等这里出现了问题实际上面数计算需要更精确的方法。对于复杂图形推荐使用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_labelsTrue, node_shapes, node_size1500) plt.title(PCB布线方案无交叉) plt.show() else: print(需要多层电路板解决交叉问题) pcb_routing_example()这个简单例子展示了如何用平面图理论解决实际问题。当图不是平面图时工程师就需要使用过孔via或多层板来实现交叉——这正是K₅和K₃,₃给我们的启示。