平面图

如果能把一个无向图的所有结点和边画在平面上，使得任何两边除了公共结点外没有其他交叉点，则称为平面图，否则称非平面图

每一个 连通分支 都是平面图

图需要改画验证

观察法验证

1. 找一个最长的 回路，连起来（标号后变成一个圈更好看）
2. 补上其他的边，讨论在回路内部和外部的情况，可以运用 鸽笼原理，讨论相交情况

这个方法判断小的图是平面图很好用

欧拉公式

设 G 是连通平面图，有 n 个结点，m 条边，r 个面

则有

$$n-m+r=2$$

---

在 平面图 的一个平面表示中：

由边所包围的内部不包含图的结点和边的区域称为 面

包围该面的边构成的 回路 称为 面的边界，边界的长度称为 次数

面积有限的面称为 有限面，反之称为 无限面

无限面只有一个

所有面的次数只和等于边数的两倍

证明

对边数 m 进行数学归纳：

当 $m=1$，分类有没有自环

证明递推：分类是不是树：是树好证明，不是树的话就去掉回路的一条边，面的个数也同样减少 1，递推得出

---

推论

设 G 为一个简单连通平面图，有 n 个结点，m 条边

则有

$$m\le 3n-6$$

运用：证明 $K_5$ 不是平面图（代入上面矛盾了）

---

设 G 为一个简单连通平面图，有 n 个结点，m 条边，每个面的次数至少为 k，则有

$$m\le \frac{k}{k-2}(n-2)$$

运用：证明 $K_{3,3}$ 不是平面图：每个面的次数不能小于等于 3（奇数了），那么都大于等于 4，代入上式得出矛盾

再推论：对于完全二分图来说至少要满足

$$e\le 2(v-2)$$ $$ab\le 2(a+b-2)$$

画图可得，要求任意一边的个数不能超过 2

指向原始笔记的链接

库拉托夫斯基定理

一个图是非平面图的充要条件是它存在一个能 收缩 为 $K_5$ 或 $K_{3,3}$ 的子图

将 $K_5$ 或 $K_{3,3}$ 称为 库拉托夫斯基图

指向原始笔记的链接