写在前面

平面图这章被Michael_Bryant整个旷了QAQ

一些概念

1.平面图 图的平面嵌入

可以将所有的边放在同一个平面内并且任意两条边不相交的图叫做平面图
一个图是可平面的 当我们可以将其化成一个平面图
上述过程叫做将图$G$嵌入平面
化成的一个平面图叫做图$G$的一个平面嵌入

2.面 内部面 外部面 面的次数

一个平面图$G$会将一个平面分为很多个区域 每个区域叫做一个面
其中会有一个没有边界的(外部面) 以及若干有边界的(内部面)
一个面的次数其边界边的次数和 其中桥的次数是$2$ 其余边次数是$1$ 面$f$记作$deg(f)$
我们给出一个小小的例子吧
Onenote画图太累了 下面的图用notability画吧(手动狗头

如上图是一个平面图(小老爷们不要把$f_2$和$f_3$的组合看成圆锥bbl
此时$deg(f_1)=1$,$deg(f_2)=2$,$deg(f_3)=3$,$deg(f_4)=6$,$deg(f_5)=10$
这个图吧 有一点点小小的问题(
就是从最右侧扎出来的那条边到底算是哪个面的
笔者认为算哪个都行 但是原则是不重不漏
比如$deg(f_4)=4$,$deg(f_5)=12$也无可厚非
那么 根据上面的定义易知
1.如果一条边不是桥 那么它一定是两个面的公共边界
2.桥只能是一个面的边界
这里注意 如上图 一个比较显然的误区是桥只能是外部面的边界
但是上面的例子就很好的反驳了这个观点

3.相邻面

这个过于显然了 以至于我差点忘了写(
两个有公共边界的面称为相邻的面

一些(亿些)定理

1.面的次数定理

平面图$G$的所有面的次数之和等于边数的两倍(类比握手定理)
根据上面的性质 我们不难看出 无论是不是桥 每条边都被计算了两次

2.欧拉公式

设$G$是具有$n$个点$m$条边$k$个面的连通平面图 那么$n-m+k=2$
证明方法是针对$k$这个变量进行归纳 读者可以自行证明
一个事情值得注意就是当$k=1$的时候 这个图形是一棵树
证明思路是当$k$增加$1$的时候 我们采取删边的措施 使得$k$变回上次的值使用结论

3.欧拉公式的进一步推广

设$G$是具有$k$个面$l$个连通分支的平面图 那么
$n-m+k=l+1$
证明方法是对于每个连通分支使用欧拉公式
然后在把所有的式子加在一起的时候 注意到唯一出现问题的是外部面
我们把重复加上的外部面减掉就可以了
还有就是一个有关边数和面的次数的关系的公式
若$G$由$n$个点 $m$条边组成 并且对于任意的面$f$都有$deg(f) \geq l \geq 3$
那么 $m \leq l(n-2)/(l-2)$
证明方法同样是利用欧拉公式

4.一些推论

由于这些推论的实际应用价值远大于其证明思想 所以如下我们不加证明地给出这些推论

4.1

设$G$是具有$n$个点$m$条边的简单可平面图 那么当$n \geq 3$时 满足$m \leq 3n-6$
特别地 如果图$G$中不含有三角形 那么$m \leq 2n-4$

4.2

设$G$是具有$n$个点$m$条边的连通平面图 若$G$中所有面均由长度为$l$的圈围成 那么$m(l-2)=l(n-2)$

4.3

$K_5$,$K _ {3,3}$都是不可平面图
注释:第一个利用推论$4.1$ 第二个利用进一步推广的第二条(此时$l=4$) 感兴趣的读者可以自行验证以及证明

4.4

如果$G$是简单平面图 那么$δ \leq 5$
注释:证明思路是假设$n \geq 3$,$δ \geq 6$利用边的次数之和公式来证明
至此 我们对于亿些定理的探讨暂时结束

5.几个小小的应用

$1$ 证明正多面体只有$5$种
证明如下:
设一个正多面体的每个面是正$n$边形 每个顶点连接着$m$条棱 总面数是$F$ 总棱数是$E$ 总顶点数是$V$ 那么有下面两个显然的式子
$n * F = 2 * E$
$m * V = 2 * E$
我们由上式推出$F = 2E/n$,$V=2E/m$带入欧拉公式有
$2E/m+2E/n-E=2$进行整理有$1/m+1/n=1/2+1/E$
得到$m$,$n$不能同时大于$3$
又根据$m$,$n$的几何意义有 $m \geq 3$,$n \geq 3$
所以二者必有一个等于$3$
根据那个加和的性质得知另外一个变量不能超过$5$
所以我们得到如下结果
$(3,3),(3,4),(3,5),(4,3),(5,3)$
对应的分别是正四面体 正八面体 正二十面体 正六面体 正十二面体
(解方程即可)
如上 正多面体仅$5$种
PS.其实还有一种更加直观的算法 但是这个要求相当强的空间想象以及证明能力 Michael_Bryant并不具备 所以就算了
一个小小的思路就是利用正多面体一个点处所有的角的平面角的度数和小于$360°$来做
$2$ 没有$7$条棱的凸多面体
根据总度数$14$得知 只能是$4$个顶点的凸多面体
但是最多$6$条边 所以这件事情就不成立了

Grinberg定理

这个定理曾用来举出反对Tait针对四染色平面图的猜测的反例
但是至今笔者未发现什么特别显著的用处 而且相关资料很少 这里引用一下知乎专栏的知识吧
传送门
值得注意的是一个理论
任何$4$-连通平面图都是哈密顿图

Kuratowski定理

概念——同胚图

我们说对于图$G_1$ $G_2$ 当两个图同构 或者插入或删除度数为$2$的顶点后同构时 我们说这两个图同胚

概念——边的收缩

对于图$G$的一条边$e=(u,v)$ 我们采取一个新的节点$w$ 使得$w$与$u$ $v$相连的节点均相连 这个过程我们叫做边的收缩
可以举个小小的例子

Kuratowski定理

两种描述:
1.图$G$是可平面图的充分必要条件是$G$不含有与$K_5$或者$K _ {3,3}$同胚的子图
2.(这个更常用)图$G$是平面图的充要条件是图$G$不含可收缩到$K_5$或者$K _ {3,3}$的子图
例如上面边的收缩的第二个图就收缩到了一个$K_5$ 所以它不是平面图
当然了也可以收缩到$K _ {3,3}$ 笔者这边不画了
利用删除边$(B_2,B_5)$和$(A_3,A_4)$的子图进行收缩边$(A_i,B_i)$,$(i=2,3,4,5)$即可得到
至此 我们对于Kuratowski定理的讨论暂时结束
这个算法挺看脸的 如果使用笔算的话
至于程序算法Tarjan老爷子有个优秀的算法 但是论文我还没找到 放个坑在这吧 找到论文就来填

一些特殊的平面图

极大可平面图

极大可平面图:对简单可平面图$G$ 对任意两个不相邻的点 添加一条边 就会导致产生一个不可平面图
笔者注:其实不能再添加边也算是一种极大可平面图 例如$K_3$之类的

极大平面图

极大平面图:极大可平面图的平面嵌入
有关极大平面图的一些性质:
$1$.如果$G$是极大平面图 那么$G$必连通 更多地 如果$G$中不少于$3$个点 那么$G$中一定没有桥
证明思路:
前半段 考虑取出两个同为平面图的连通分支 将其中一个$G_2$画在$G_1$的外部面 并在两个图的外部面边界处取出两个点$u$ $v$ 显然这两个点不邻接 这样我们得到了一个新的图 这个新图更大而且也是平面图
所以我们说不连通的图一定不是极大平面图
后半段 假设存在桥$uv$ 那么我们把桥切断得到两个连通分量$G_1$ $G_2$ 而且至少有一个是$ \geq 2$个点的 我们不妨设$G_2$是这个$ \geq 2$个点的 取出$G_1$中含有$u$的面$f$那么我们把$G_2$画在$f$内 并取$G_2$外部面边界上异于$v$的另一个点$t$
现在把桥接回来 连接$ut$ 得到一个更大的平面图了 所以假设不成立
笔者注:后半段看起来不好理解 说白了就是两边只有一段相连的话一定可以再添上第二段
$2$.如果$G$是一个至少具有$3$个顶点的平面图 则$G$是极大平面图的充要条件是$G$是简单图且各面的次数都是$3$
(简单图:无重边无自环)
证明思路:
充分性显然QAQ 可以从定义入手
我们来说必要性 根据$G$是一个极大平面图得知$G$一定是一个简单图 又$G$至少有三个顶点 所以每个面的次数$deg(f) \geq 3$
不妨设有一个面$deg(f_0) \geq 4$那么根据极大平面图没有桥可以知道$f_0$的边界一定是一个闭环 我们记这个闭环的前$4$个点是$v_i$,$(i=1,2,3,4)$
首先看$v_1$,$v_3$ 如若他们不相邻 则在面$f_0$内连上之后并不破坏原图的平面性 这和$G$是极大平面图矛盾 所以它们之间一定有一条边并且在$f_0$外部 同理$v_2$和$v_4$之间也有一条边在面外
而这两条边一定相交 与平面性矛盾
所以假设不成立 原结论成立
$3$. 对于一个极大平面图
边数$m=3 * n-6$,面数$k=2 * n-4$
这也就是说一个极大平面图给定一个条件则三个参数全部确定
但是并不代表极大平面图是唯一形态的

极小不可平面图

就是说任意删除一条边就能变成可平面图的图
注意 强调任意
例如$K_5$,$ K _ {3,3}$都是极小不可平面图

外可平面图

一个可平面图 存在使得所有点出现在同一个面内的平面嵌入
这个图就是外可平面图
基本的非外可平面图:$K_4$,$K _ {2,3}$

外平面图

外可平面图的任意一种外平面嵌入
极大外可平面图:对一个简单外可平面图$G$ 若对$G$的任意两个不相邻的顶点 增加一条边 就会得到不是外可平面图。
极大外平面图:外部面的周界 是由多边形组成 内部面均由三角形围成
这个是能证明的 但是感觉yy一下就出来了
证明方法:数学归纳法证明下述结论即可
所以我们就可以轻松得到 如果一个极大外平面图有$n$个顶点的话 那么有$n-2$个内部面
证明提示 新加入节点的时候观察其度数特点
另外一个结论:顶点数$n \geq 7$的外可平面图的补图不是外可平面图
证明的话可以自行画图验证
至此 这些特殊的平面图我们讨论结束

平面图转对偶图

这个相信是讲了这么多仅有的贴近OI和ACM的知识点吧
bzoj 1001 狼抓兔子简直是呼之欲出
可惜那题我用的dinic
现在知道什么是平面图了 那么到底什么是对偶图
且听我分说
对偶图:把平面图的面换成对偶图的点 把平面图中的两个面的交线换成对偶图中的对应点之间的连线
(只在一个面上的边 也就是桥 变成一个自环)
一个定理:如果图$G * $ 是一个对偶图 那么图$G * $一定是连通的
证明方法是在平面图中任意画一条不经过原平面图的线 然后找到其经过的面和边序列 对应到对偶图中的点和边序列 这样就是一条路径 所以是连通的就显然了
只有$G$连通的时候才有$(G * ) * = G$这个值得注意
讲了这个应用是什么呢
如果网络流中的图$G$可以转化为一个平面图 那么其对偶图$G'$中的环对应$G$中的割 利用最大流最小割定理转化模型 根据平面图$G'$与其对偶图的关系 先求出最小割
首先连接$s$和$t$得到一个附加面 我们设附加面对应的点为$s'$ 无界面对应的点为$t'$ 求该图的对偶图$G'$,最后删去$s'$和$t'$之间的边
一条从$s'$到$t'$的路径 就对应了一个$s-t$割 更进一步 如果我们令每条边的长度等于它的容量 那么最小割的容量就等于最短路的长度 这样时间复杂度大大降低了
注意 如果是有向边 那么就统一顺时针旋转90度
以上