最后更新: 2025-01-21 17:56 查看: 358 次纠错评论(0) 课件开VIP

平面图的面与次数和欧拉公式

定义7－5．2 设图G是一个连通平面图，由图中的边所包围的区域称为G的一个面，其中面中包含结点和边。包围该面的各条边构成的回路称为面的边界。

定理7－5．1 一个有限平面图，面的次数之和等于其边数的两倍。

证明：因为任何一条边，只可能是两个面的公共边或者是一个面的内边界，则都会被重复计算两次，故面的次数之和等于边数的两倍。

![图片](/uploads/2025-01/ac55b1.jpg)

欧拉公式
定理7－5．2 设有一个连通的平面图G，内含有 n 个结点， m 条边和 r 块面，则欧拉公式成立，有 $n-m+r=2$ 。
证明：我们对边数 $m$ 用归纳法
$m=0$ 时，连通图只能是一个孤立点，则 $r =1$ ，满足当 $m=1$ ，即仅有一条边时，由于 $G$ 是连通图，故图 G 有下述两种情况：
－$n=1$ ，仅有一条自环，此时 $n=1, m=1, r=2$ ，命题成立。
$- n = 2$ ，此时 $G$ 有两个顶点及这二个顶点之间有一条边，则 $r =1$ ，命题也成立。所以，当 $m=1$ 时命题成立。

## 欧拉公式的证明
归纳假设 $m=k$ 时，命题成立。
当 $m=k+1$ 时，1）若 $G$ 中有一度顶点，设为 $v 0$ ，在 $G$ 中擦去顶点v0，得一个新图G＇。此时，新图G＇比G少了一条关联的边 ，即 $G ^{\prime}$ 有 $k$ 条边。由归纳假定 $n^{\prime}-m^{\prime}+r^{\prime}=2$ ，其中 $n^{\prime}$ 为 $G ^{\prime}$ 中顶点数，$m^{\prime}$＇为 $G ^{\prime}$ 中边数，$r^{\prime}$ 为 $G ^{\prime}$ 含有的区域数。显然，$n=n^{\prime}+1$ ,$m=m^{\prime}+1$ ，而 $r=r \prime$ 。所以有 $n-m+r=2$ ，即命题成立。
2）若 $G$ 中没有一度顶点，则 $G$ 中一定有圈。我们擦去圈中一条边，得一新图 $G^{\prime}$ ，则有 $n=n^{\prime}, m=m^{\prime}+1, r=r^{\prime}+1$ ，其中 $n^{\prime}, ~ m$＇与 $r ^{\prime}$ 分别为 $G ^{\prime}$ 的顶点数，边数与区域数。由归纳假定，在 $G ^{\prime}$ 中有 $n^{\prime}-m^{\prime}+r^{\prime}=2$ ，所以也有 $n-m+r=2$ ，即命题得证。

注意：用欧拉公式直接判定一个连通图是否是平面图是很难的，因为你在没有把这个图边不相交地画在一个平面上时，你无法知道面数是多少。

定理7－5．3
任何一个简单的连通平面图 $G=( V , E ),| V |= n$ ， $|E|=m$ ，则有 $m \leq 3 n-6$ 。

证明：由于 G 是简单图，则任何一个区域至少由三条边围成，所以 $2 m \geq 3 r$ ，其中 $r$ 是区域数。由连通平面图的欧拉公式： $n - m + r = 2$ ，得到 $3 n-3 m+3 r=6$ ，从而 $3 n-3 m+2 m \geq 6$ ，即 $3 n-m \geq 6$ ，故命题得证。

例7-5.1 判断K5和K3,3是否平面图。
 ![图片](/uploads/2025-01/2a3052.jpg)
 
 例7-5.2 证明K3,3不是平面图
  ![图片](/uploads/2025-01/7dac8d.jpg)
  
  证明：若 $K _{3,3}$ 是平面图，由于 $K_{3,3}$ 中最短回路的长度为 $l \geq 4$ ，于是边数 9 应满足

$$
9 \leq(4 /(4-2))(6-2)=8
$$

这又是矛盾的，所以 $K_{3,3}$ 也不是平面图。

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

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

免费注册

《高等数学》难点解析

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

《线性代数》难点解析

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

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

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

上一篇：平面图的基本概念

下一篇：同胚与库拉图斯基(Kuratowski)定理

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