6.6 平面图与欧拉公式

第六章图论6.6平面图与欧拉公式PlanarGraphsandEuler'sFormula目录CONTENTS01平面图的

基本概念平面图的定义、示例

以及非平面图的

典型反例展示。02面的概念面、边界与次数的

严谨数学定义

及其基础计算方法。03平面图的

性质与定理面的次数之和关系

欧拉公式及其

重要应用场景。04非平面图的判定利用必要条件

证明K₅和K₃,₃

为典型非平面图。05库拉托夫斯基

定理平面图判定的

终极理论方法与

核心准则。引言：为什么要学习平面图？现实世界的需求在工程设计与网络规划等诸多实际场景中，我们面临一个核心挑战：如何避免图的边在非端点处交叉？这直接关系到系统的稳定性与运行效率。印制电路板(PCB)电路板上的导线若发生交叉，极易引发短路故障，严重威胁电路安全与功能实现。建筑电气布线强弱电线缆的不规范交叉会产生电磁干扰(EMI)，导致信号失真或设备运行异常。交通网络设计减少道路的物理交叉点能有效优化路网结构，降低交通事故风险与通行延误。图：复杂的汽车电驱电控PCB电路板

高密度走线需严格遵循“无交叉”的平面性原则定义6.27：平面图(PlaneGraph)▌定义内容设图G=<V,E>是一个无向图，如果能够把G的所有结点和边都画在平面上，且使得任何两条边除了端点外，没有其它的交点，就称G是一个平面图，也称G可嵌入平面。关键在于“画法”一个图是否是平面图，取决于是否存在一种画法，使得边不交叉。即使图的某种画法存在边交叉，只要能找到一种画法避免交叉，它仍是平面图。同构不变性平面图是图的一个拓扑性质。如果一个图与某个平面图同构，那么它本身也是平面图。这意味着，无论图的顶点如何重命名或边如何重新排列，只要结构一致，平面性保持不变。平面图示例有些图的边看似相交，但通过改变画法（同构变换），可以消除所有交叉点，证明其是平面图。示例(a)看似有交叉的图，可以通过将部分边画成弧线，将交叉点“绕过去”。示例(b)方形内的对角线交叉，同样可以通过弧线重绘来避免，使其无交叉地存在于平面上示例(c)三维立方体的结构，也可以在二维平面上通过拓扑变换，画出无交叉的平面图。非平面图示例有些图无论如何改画，都无法消除边的交叉。它们被称为非平面图。完全偶图K3,3这是一个经典的非平面图。它有两组各3个结点，组内无边，组间全连接。完全图K55个结点中，任意两个结点之间都有边相连。这也是一个经典的非平面图，是所有非平面图的“基本构件”之一。定义6.28：面、边界与次数▍定义：设图G=<V,E>是一个无向连通图。由图中的边所围成的区域，区域内既不包含图的结点，也不包含图中的边，称这样的区域为图G的面(Face)。面的概念直观地描述了平面图被边分割后的区域属性。无限面(InfiniteFace)包含图外部的无限大的区域，是所有平面图都具备的外部面。有限面(FiniteFace)完全由图中的边所包围、面积有限的内部区域，是图的内部面。边界(Boundary)包围一个面的所有边构成的回路。对于无限面，其边界通常由图的外部边构成。次数(Degree)边界的长度，即构成边界的边的条数。面r的次数通常记为deg(r)。面的次数计算示例图(a)分析图(a)包含4个面，每个面的边界均由三角形构成，因此每个面的次数均为3。图(b)分析图(b)包含5个面。特别注意计算r₃的次数时，其内部的“桥”被计算了两次，故该面的次数最终为5。关键结论：一条边无论作为两个面的公共边，还是作为一个面边界的“桥”，在计算所有面的次数之和时，都会被计算两次。定理6.16：面的次数之和定理内容一个有限平面图中，面的次数之和，等于其边数的两倍。证明思路任何一条边，在图中存在两种情况：1.作为两个面的公共边：分别计入这两个面的次数。2.作为一个面的边界（即桥）：在这个面的边界中被计算两次。结论：无论哪种情况，每条边都被计算了两次。因此，面的次数之和等于边数的两倍。示例验证•图6.50(a)：边数e=6，面的次数之和为3+3+3+3=12=2×6。•图6.50(b)：边数e=9，面的次数之和为3+3+5+4+3=18=2×9。以上两个例子直观地验证了定理的正确性。定理6.17：欧拉公式(Euler'sFormula)定理内容Statement设有一个连通简单平面图G，共有v个结点，e条边和r个面，则一定有：v-e+r=2起源与背景Origin该公式最初是欧拉在研究凸多面体时发现的。利用球极投影的几何变换，任何凸多面体的表面都可展开为一个连通的平面图，从而使该公式的应用范围得到了极大推广。图：凸多面体与平面展开图的拓扑同胚欧拉公式的证明(数学归纳法)01/基础步骤(BaseCase)•孤立结点：v=1,e=0,r=1→1-0+1=2(成立)•两个结点一条边：v=2,e=1,r=1→2-1+1=2(成立)•一个结点一个环：v=1,e=1,r=2→1-1+2=2(成立)归纳假设(InductiveHypothesis)假设：对于任意一个连通的平面图G，当边数为e=k时，欧拉公式v-e+r=2成立。注：k为任意正整数，图需保持连通性。递推证明(InductiveStep)1.增加一个新结点(保持连通):v+1,e+1,r不变。公式仍成立：(v+1)-(e+1)+r=v-e+r=2。2.连接两个已有结点(增加面):v不变,e+1,r+1。公式仍成立：v-(e+1)+(r+1)=v-e+r=2。定理6.18：平面图的必要条件定理内容：设G是一个有v个结点、e条边的连通简单平面图，若v≥3，则e≤3v-6。01.面次数分析连通简单平面图中，每个面的边数至少为3。由握手定理，所有面的次数之和等于边数的两倍，故2e≥3r，即r≤2e/3。02.代入欧拉公式将面数的上界代入欧拉公式v-e+r=2，可得不等式：

2≤v-e+(2e/3)。03.整理推导将上一步的不等式移项并整理，消去分数项，最终可得到边数e的上界：

e≤3v-6。这是一个必要非充分条件。其逆否命题具有极强的实用价值：

若一个图不满足e≤3v-6，则它一定不是平面图。例题6.21：证明K5

不是平面图待证命题请证明：在图论中，拥有5个顶点的完全图\(K_5\)无法被画在一个平面上，使得任意两条边都不会在非顶点的位置相交。证明逻辑(基于必要条件)1.确定参数：在K5中，顶点数v=5，边数e=102.代入定理：根据平面图必要条件公式，计算得

3v−6=3×5−6=9。3.比较结果：10>9，不满足上述必要条件。4.结论：K5不是平面图。完全图K5

的结构示意每个顶点均与其他4个顶点相连，边的密集程度

导致无法避免在平面上的交叉。例题6.22：证明

K3,3

不是平面图初步分析：必要条件的局限性在完全二部图K3,3

中，顶点数和边数分别为：顶点数v=6，边数e=9根据平面图的必要条件e≤3v−6进行验证：3v−6=3×6−6=12，满足9≤

12。结论：无法仅通过该不等式判定其非平面性，需引入更强的判定方法。严格证明：反证法1.假设：假设K3,3

是平面图。2.面次数推导：K3,3是偶图，不含奇圈，故每个面的次数至少为4。3.推导新不等式：由2e>4r

得r≤e/2，代入欧拉公式v-e+r=2，可推导出新的必要条件：e≤2v−44.验证矛盾：代入数据得2v-4=8，但K3,3

的边数e=9>8，与上述必要条件矛盾。5.结论：假设不成立，故K3,3

不是平面图。定义6.29：2度结点内同构▍定义内容给定两个图G1和G2

，如果它们是同构的，或者通过反复插入或除去度数为2的结点后，使G1

与G2同构，则称该两图是在2度结点内同构的。核心思想：在一条边上插入或删除一个度数为2的结点，不会改变图的平面性。这一性质是判定图的平面性的关键依据之一。定理6.19：库拉托夫斯基定理(Kuratowski'sTheorem)▌定理内容(TheoremStatement)一个图G是平面图，当且仅当G中不包含与

K5

或

K3,3在2度结点内同构的子图。充分必要条件(Criterion)这是判断一个图是否为平面图的“终极判定工具”。它将复杂的几何嵌入问题转化为纯粹的图论结构识别问题。本质(Essence)任何非平面图，其结构中必然“隐藏”着一个可以通过边收缩操作还原为\(K_5\)或\(K_{3,3}\)的子图。本章总结：平面图与欧拉公式平面图(PlanarGraph)定义：若一个图能画在平面上，且除顶点外，任意两边没有交叉点，则称该图为平面图。面(Face)平面图被边分割出的连通区域。它包含一个特殊的、包含无穷远点的“无限面”(OuterFace)，其余被边完全包围的区域为“有限面”。欧拉公式(Euler'sFormula