平面图的基本概念及性质

前言：

内容来源这篇博客 原文链接
为了免去跳转麻烦，直接复制博客内容过来。

基本概念

平面图：设无向图G，若能将G画在一个平面上，使得任何两条边仅在顶点处相交，则称G是具有平面性质的图，简称平面图，否则称G是非平面图。

在平面图G中，G的边将其所在的平面划分成的区域称为面，有限的区域称为有限面或内部面，无线的区域称为无限面或外部面，包围面的边称为该面的边界，包围每个面的所有边组成的回路长度称为该面的次数（桥计算两次）。

由定义易知:

1. 如果一条边不是桥，那它必是两个面的公共边界
2. 桥只能是一个面的边界
3. 两个以一条边为公共边界的面称为相邻的

就有如下的定理：平面图G所有面的次数之和等于边数的两倍（类似于握手定理）。

欧拉公式

定理： 设G是一个面数为 f 的（n,m）平面图，则 $n-m+f=2$.
证： 用归纳法证明，对图的边数做归纳

1. m=0时，由于G是一个连通图，因此G只包含一个孤立顶点，具有一个外部面，1-0+1=2
2. 假设m=k时欧拉公式成立，对m=k+1做归纳。若存在悬挂边，则删去与之相连的悬挂边之后，边数和定点数都减少1而面数不变，因此n-m+f不变

若不存在悬挂边，每个顶点的度数都大于1，图中必定存在回路C，C上任一边都一定是两个面的公共边界，删去此边，这两个面合并为一个面。顶点数不变，边数减1，面数减1，因此n-m+f不变。

推论1： 设G是一个面数为 f 的（n,m）平面图，且有p个连通分支，则n-m+f = p+1
证： 对每个连通分支使用n-m+f即可，p=1时就是欧拉公式

推论2： 假设G是一个面数为 f 的（n,m）连通简单平面图，n≥3,每个面的次数至少是p(p≥3)，则$m\le (n-2)\times \frac{p}{p-2}$
证： 由之前的定理知，$f\times p\le 2m$,带入欧拉公式整理即可
应用： 利用该定理可以证明$K_{3,3}$是非平面图
假设$K_{3,3}$是平面图，其中最短的回路长度为4，应有9≤(6-2) * 4 / (4-2) = 6，产生矛盾

推论3： 设G是一个面数为 f 的(n,m)连通简单图且n≥3,则m≤3n-6.
证： 联通简单图不存在重边和自环，所以每个面的次数最少为3，带入定理2中的公式 $m\le (n-2)\times 3/1=3n-6$
应用： 利用该定理可以证明K₅是非平面图

假设 K₅ 是平面图，由于K₅中n=5,m=10,定理有m≤3n-6，即应有10≤3*5-6，产生矛盾。

推论4： 任何简单连通图平面图中，至少存在一个度数不超过5的顶点。
证： 若所有顶点的度数都大于5，由握手定理有6n≤2m,即m≥3n,与推论3 m≤3n-6矛盾

这些定理和推论只是图可平面性的必要条件，满足这些条件的图不一定是平面图。

库拉托夫斯基定理

库拉托夫斯基定理给出了判断一个图是否是平面图的充分必要条件
先学习一个概念——同胚

同胚：若图G1和G2是同构的，或者通过反复的插入或删除2度顶点，它们能变成同构，则称G1和G2是同胚的（或称在2度顶点内同构）

定理： 一个无向图是平面图当且仅当它不包含与$K_{3,3}$或K₅同胚的子图。 （证明比较复杂，略）

例如，证明下面的不是平面图

(1)删除一些2度顶点及相连的边（如图中虚线所示）

(2)发现这是一个$K_{3,3}$

(3)有由理知，不是平面图。

参考链接：
中国大学mooc 刘铎 离散数学