Graph Theory and Network Algorithm 6 平面图

发表于 2020-11-22 更新于 2022-04-08 分类于 UCAS ， Courses 阅读次数：

图论与网络算法 (070105M04003H)，平面图。

平面图

1950-1990火，现在不火了（作为选题丰富），因为：

能做的都做完了；

老的没传承；

和四色猜想密切相关。

厉害的人：刘彦佩

概念

可嵌入曲面：若$G$能画在曲面$S$上，使得任意两边互不交叉，则称$S$为可嵌入曲面。
可平面图（planar graph）：能嵌入平面的图。
- 不可平面图（nonplanar graph）：不能嵌入平面的图。
- 平面嵌入（planar embedding）：可平面图在平面上画出的无交叉边的图示。
- 平面图（plane graph）：可平面图的任何一个平面嵌入。

想办法把图拍到沙滩上；

可平面图的平面嵌入一般不唯一，因此可平面图对应的平面图一般也不唯一；

面（face）：平面图$G$，$G$的边将平面划分出的区域；
- 外部面/无限面（exterior face）：面积无限的面；
- 内部面/有限面（interior face）：面积有限的面；
- 边界（boundary）：包围一个面的所有边；
- 面的度数（degree of face）：一个面的边界上的边数（割边按两次计），面$f$的度数记为$deg(f)$。
极大可平面图（maximal planar graph）：简单图、可平面图$G$，若在$G$任意不相邻顶点间加边后成为不可平面图。
- 极大平面图（maximal plane graph）：极大可平面图的任何一个平面嵌入。
极小不可平面图（minimal nonplanar graph）：不可平面图$G$，任意删除一边后成为可平面图。

$K_1,K_2,K_3,K_4,K_5-e$都是极大可平面图。

剖分（edge subdivision）：
收缩（edge contraction）：

对偶图：以$G$的面作为顶点的图$G^*$，面面有公共边界就相连，面上有割边就连环边（自环）。
- $G^*$是平面图、连通图，多数情况有重边；
- 环边$\longleftrightarrow$割边；
- 两个同构的平面图，其对偶图不一定同构。

定理

Theorem 7.1.1 可平面图$G\Longrightarrow G$的任何子图都是可平面图。

Theorem 7.1.2 不可平面图$G\Longrightarrow$任何含有$G$作为子图的图都是不可平面图。

Theorem 7.1.3 不可平面图$G\Longrightarrow$在$G$添加重边或环边后所得之图仍是可平面图。

$K_n(n\le4),K_{1,n}(n\ge1)$及其所有子图都是可平面图；

环边和重边不影响图的可平面性；

讨论可平面性时，总假定图时简单图。

Theorem 7.1.4 $\sum\limits_{i=1}^\phi deg(f_i)=2\epsilon(G)$，其中$f_1,f_2,...,f_\phi$是平面图$G$的所有面。

Theorem 7.1.5 极大可平面图是连通的。

Theorem 7.1.6 至少含有$3$个顶点的极大可平面图中没有割边和割点。

若有，删去割边或割点后的两个连通分支连线仍为可平面图。

Theorem 7.1.7 对于至少含$3$个顶点的极大可平面图，其每个面的度数必定都是$3$.

反证，考虑某个面上相邻的四个顶点$v_1,v_2,v_3,v_4$，则$v_1$和$v_3$，$v_2$和$v_4$必相邻（否则不极大），则这两边必在外部相交，矛盾。

这个定理是充要的，后面会证。

Theorem 7.2.1 (欧拉公式, 1753) 设连通平面图$G$，$\epsilon,\upsilon,\phi$分别是顶点数、边数和面数，则$\upsilon-\epsilon+\phi=2$。

对$\epsilon$做数学归纳法，当$\epsilon=k+1$时，对$G$是否含圈分别讨论。
若不含圈，则为树，直接计算即可；若含圈，去一边后仍为连通图（注意到面数也减少了$1$），使用归纳假设。

Theorem 7.2.2 (欧拉公式的推广形式) 设平面图$G$，$\epsilon,\upsilon,\phi,w$分别是顶点数、边数、面数和连通分支个数，则$\upsilon-\epsilon+\phi=w+1$。

对每个连通分支使用欧拉公式，注意到面数被多算了$w-1$次。

Theorem 7.2.3 设连通平面图$G$，每个面的度数至少为$l(l\ge3)\Longrightarrow \epsilon\le\frac{l}{l-2}(\upsilon-2)$。

$2\epsilon=\sum\limits_{i=1}^\phi deg(f_i)\ge l\cdot\phi$，使用欧拉公式消去$\phi$，整理后得证。

$K_5$和$K_{3,3}$都是不可平面图。

$K_{3,3}$最短圈长为$4$（最短圈的长度即为面度数的最小值）。

$K_n(n\ge5)$和$K_{3,n}(n\ge3)$都是不可平面图。
$K_5$和$K_{3,3}$都是极小不可平面图。

Theorem 7.2.4 设平面图$G$，每个面的度数至少为$l(l\ge3)\Longrightarrow \epsilon\le\frac{l}{l-2}(\upsilon-w-1)$。

Theorem 7.2.5 设简单图、平面图$G,\upsilon\ge3 \Longrightarrow \epsilon\le3\upsilon-6$。

分无圈和有圈讨论。
若无圈则为树或森林，若有圈则圈长$l\ge3$，使用Theorem 7.2.4得证。

Theorem 7.2.6 设极大平面图$G,\upsilon\ge3 \Longrightarrow \epsilon=3\upsilon-6, \phi=2\upsilon-4$。

$2\epsilon=\sum\limits_{i=1}^\phi deg(f_i)= 3\phi$，带入欧拉公式消去$\phi$。

Theorem 7.2.7 连通简单平面图$G,\upsilon\ge3$，$G$为极大平面图$\Longleftrightarrow G$每个面度数均为$3$。

$\Longleftarrow$ $2\epsilon=\sum\limits_{i=1}^\phi deg(f_i)= 3\phi$，带入欧拉公式消去$\phi$，可得$\epsilon=3\upsilon-6$。设$G'=G+uv$仍为平面图，则$\epsilon'=3\upsilon'-5>3\upsilon'-6$，与Theorem 7.2.5矛盾。

Theorem 7.2.8 设简单图、平面图$G,\upsilon\ge3 \Longrightarrow \delta\le5$。

反证，用度边关系推出矛盾。

Theorem 7.3.1 (Kuratowski, 1930) $G$是可平面图$\Longleftrightarrow G$既不含$K_5$的剖分图，也不含$K_{3,3}$的剖分图。

证明有30多页；

Peterson图是不可平面图，因为它含有$K_{3,3}$剖分图。

Theorem 7.3.2 (Wagner, 1937) $G$是可平面图$\Longleftrightarrow G$中既没有可收缩到$K_5$的子图，也没有可收缩到$K_{3,3}$的子图。

Theorem 7.4.1 $G^*$是连通平面图$G$的对偶图，则

$\upsilon^*=\phi$；
$\epsilon^*=\epsilon$；
$\phi^*=\upsilon$；
若$v^*_i$位于面$f_i$中，则$d_{G^*}(v_i^*)=deg(f_i)$。

前两条显然；

第三条对两个图使用欧拉公式；

第四条将边分为割边和非割边两类讨论。

Theorem 7.4.2 $G^*$是连通平面图$G$的对偶图，则

$\upsilon^*=\phi$；
$\epsilon^*=\epsilon$；
$\phi^*=\upsilon-w+1$；
若$v^*_i$位于面$f_i$中，则$d_{G^*}(v_i^*)=deg(f_i)$。

练习

设不含三角形的平面简单图$G,\upsilon(G)\ge3$，证明：$\epsilon(G)\le2\upsilon(G)-4$。

直接套公式$\epsilon\le\frac{l}{l-2}(\upsilon-w-1)$。

证明：可平面简单图$G,\upsilon(G)\le12$，必有度不超过$4$的顶点。

反证，直接套公式$\epsilon\le\frac{l}{l-2}(\upsilon-w-1)$。

证明：连通平面图$G,\delta(G)\ge3$，则$G$至少有一个面的度数不超过5.

反证，套公式$\epsilon\le\frac{l}{l-2}(\upsilon-w-1)$，得$2\epsilon\le3\upsilon-6$，与$2\epsilon\ge3\upsilon$矛盾。

总结

$\upsilon-\epsilon+\phi=w+1$；
$\epsilon\le\frac{l}{l-2}(\upsilon-w-1),\ (l\ge3)$；
连通简单图，极大平面图$\Longleftrightarrow$每个面度为$3$。