最后更新: 2025-01-22 09:32 查看: 287 次纠错评论(0) 课件开VIP

平面图与欧拉公式

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

定义 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$ 。

科数题库(单机版) 会议室预约系统(book)

今日还可看 0 篇未注册用户每天查看4篇，注册用户每天8篇，开通VIP会员无限制查看。

免费注册

《高等数学》难点解析

高数教程 泰勒公式切线与法线切平面与法平面驻点·拐点·极值点·零点间断点渐进线瑕积分欧拉方程伯努利方程 Abel 收敛定理偏导数的几何意义偏导数的几何意义梯度数量场与向量场多元函数极值拉格朗日算子通量与散度环流量与旋度格林公式高斯公式斯托克斯公式三大公式比较傅里叶级数极坐标微元点法式方程变上限定积分 X型计算面积 Y型计算面积微分的意义渐近线间断点 y''+py'+qy=f(x)方程高斯黎曼傅里叶变换(复数) 拉普拉斯变换(复数)

《线性代数》难点解析

线代教程 近世代数对数学的整体思考线性的意义矩阵乘法(列视角) 矩阵乘法(行视角) 矩阵左乘矩阵右乘逆矩阵求解方程组阶梯形矩阵的求法方程组解的判定四阶行列式的计算线性变换的意义线性空间向量组的等价线性空间的几何意义基础解系的求法施密特正交化特征值与特征向量的意义矩阵相似的几何意义矩阵可对角化的理解秩的意义(向量版) 秩的意义(方程版) 二次型的意义

《概率论与数理统计》难点解析

概率教程 置信区间与上a分位数概率中的“取”与“放” 贝叶斯公式全概率公式泊松分布指数分布伽玛分布二维密度图的意义卷积的意义相关系数的意义 k阶矩是与矩母函数卡方分布的作用单正态区间估计理解假设检验理解切比雪夫不等式中心极限定理

上一篇：图论模型初步

下一篇：平面图的特征

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