最后更新: 2025-01-22 09:32 ● 参与者查看: 37 次纠错分享参与项目词条搜索

平面图与欧拉公式

在现实生活中，常常要画一些图形，希望边与边之间尽量减少相交的情况，例如印刷线路板上的布线，交通道的设计等，由此引出了平面图的概念。

定义 9.1 （平面图）若一个图能画在平面上使它的边互不相交（除了在顶点处外），则称该图为平面图，或称该图为能嵌入平面的。

例如，图 9.1 （a）是平面图 $G$ ，它能嵌入到平面上，如图 9.1 （b）所示，记为 $G, G$ 是 $G$ 的平面嵌入。
 ![图片](/uploads/2025-01/23e4f5.jpg)
 
 并不是所有的图都是平面图。如图9．2 给出的（a）$K_{3,3}$ 和（b）$K_5$ 就不是平面图。
欧拉公式
在介绍关于连通平面图的欧拉公式之前，先给出平面图中面的概念。
定义9．2（面／外部面／内部面）平面图 $G$ 嵌入平面后将 6 分成若干个连通闭区域，每一个连通闭区域称为 $G$ 的一个面。其中恰有一个无界的面，称为外部面；其余的面称为内部面。

图9．3 是一个平面图的平面嵌入，它有 5 个面：$R_0, R_1, R_2, R_3, R_4$ ，其中 $R_0$ 是外部面，$R_1, R_2$ ， $R_3, R_4$ 是内部面。

定理 9.1 （欧拉公式）若连通平面图 $G$ 有 $n$ 个顶点，$e$ 条边和 $f$ 个面，则 $n - e + f = 2$ 。称该公式为欧拉公式。

证明：以边数为归纳变量，进行归纳证明。
 
归纳基础：对于一条边的连通平面图，欧拉公式显然成立。
归纳步骤：假设对于任意的 m−1 条边的连通平面图，欧拉公式均成立。现在考察 m 条边
的连通平面图 G，分两种情况
 ![图片](/uploads/2025-01/1a61ac.jpg)
 
 （1）若 $G$ 有度数为 1 的顶点，则删去该顶点及其关联边，便得到连通平面图 $G^{\prime} 。 G^{\prime}$ 满足欧拉公式，再将删去的点和边加回 $G^{\prime}$ ，得到原图 $G$ ，其顶点数加 1 ，边数加 1 ，而面数不变，所以 $G$ 也满足欧拉公式。
（2）若 $G$ 没有度数为 1 的顶点，则删去有界面边界上的任一边，便得到连通平面图 $G^{\prime}$ ， $G^{\prime}$ 满足欧拉公式，再将删去的边加回 $G^{\prime}$ ，得到原图 $G$ ，其面数加 1 ，边数加 1 ，而顶点数不变，所以 $G$ 也满足欧拉公式。

图9．3是平面图，但不是连通平面图，对于图9．3的每一个连通分支，欧拉公式成立。
推论 9.1 若 $G$ 是 $n(n \geqslant 3)$ 个顶点的平面简单图，则 $e \leqslant 3 n-6$ 。
证明：只证明连通的平面简单图的情况，$G$ 是 $n \geqslant 3$ 的平面简单图，每个面由 3 条或更多条边围成，每条边至多是两个面的公共边，所以 $G$ 中至少有 $3 f / 2$ 条边，即 $e \geqslant 3 f / 2$ 。根据欧拉公式，有 $n-e+2 e / 3 \geqslant 2$ 。所以 $3 n-6 \geqslant e$ 。

推论 9.2 若平面图的每个面由四条或更多条边围成，则 $e \leqslant 2 n-4$ 。
证明：类似推论 9.1 的证明。
推论 $9.3 K_5$ 和 $K_{3,3}$ 是非平面图。
证明：用反证法，若 $K_5$ 是平面图，由推论 9．1，当 $n=5, e=10$ 时， $3 n-6 \geqslant e$ 不可能。所以 $K_5$ 是非平面图。若 $K_{3,3}$ 是平面图，由推论 9．2，当 $n=6, e=9$ 时， $2 n-4 \geqslant e$ 不可能。所以 $K_{3,3}$ 是非平面图。

定理 9.2 在平面简单图 $G$ 中至少存在一个顶点 $v_0, d\left(v_0\right) \leqslant 5$ 。
证明：用反证法证明，假设简单平面图所有顶点度数大于 5 ，由推论 $9.1, e \leqslant 3 n-6$ ，所以
$K_5$ 是非平面图。若 $K_{3,3}$ 是平面图，由推论 9.2 ，当 $n=6, e=9$ 时， $2 n-4 \geqslant e$ 不可能。所以 $K_{3,3}$ 是非平面图。

定理 9.2 在平面简单图 $G$ 中至少存在一个顶点 $v_0, d\left(v_0\right) \leqslant 5$ 。
证明：用反证法证明，假设简单平面图所有顶点度数大于 5 ，由推论 $9.1, e \leqslant 3 n-6$ ，所以 $6 n-12 \geqslant 2 e=\sum_{v \in l} d(v) \geqslant 6 n$ ，导致矛盾。因此平面简单图中至少存在一个顶点 $v_0, d\left(v_0\right) \leqslant 5$ 。

上一篇：图论模型初步

下一篇：平面图的特征

本文对您是否有用？有用 (0) 无用 (0)