最后更新: 2025-01-21 17:56 查看: 70 次反馈刷题

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

定义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}$ 也不是平面图。

刷题

做题，是检验是否掌握数学的唯一真理

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

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

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