平面图
如果能把图
可平面图
可平面图概念和平面图概念有时可以等同看待;
图的平面性问题主要涉及如下几个方面:
- 平面图的性质
- 平面图的判定
- 平面嵌入方法(平面性算法)
- 涉及图的平面性问题的拓扑不变量
平面图的性质¶
一个平面图
面积有限的区域称为平面图
在 ) 称为该面
平面图的次数公式¶
设
证明:
对
连通平面图的欧拉公式¶
设
证明:
情形 1,如果
那么
情形 2,
假设在这种情形下,欧拉恒等式不成立。则存在一个含有最少边数的连通平面图
因为
于是矛盾,假设不成立。
非连通平面图的欧拉公式¶
设
证明:
对第
同时:(扣除重复计算的
于是得到:
设
Warning
这是连通平面图的必要条件,不是充分条件!
设
设
设
Abstract
该结论是证明“5 色定理”的出发点
一个连通平面图是
图的嵌入性问题¶
曲面嵌入¶
球面嵌入¶
我们实际上对图的嵌入性问题也只考虑这两个。
环面嵌入¶
略
定向曲面嵌入¶
略
3 维空间嵌入¶
所有图均可嵌入
凸多面体与平面图¶
一个多面体称为凸多面体,如果在体上任取两点,其连线均在体上。
凸多面体的一维骨架:把一个凸多面体压缩在平面上,得到一个对应的平面图,该平面图称为该凸多面体的一维骨架。
存在且只存在 5 种正多面体:它们是正四、六、八、十二、二十面体
平面图的判定¶
同胚¶
- 在图
的边上插入一个新的 度顶点,使一条边分成两条边,则称将图 在 2 度顶点内扩充; - 去掉图 的一个
度顶点,使这个 度顶点关联的两条边合成一条边,则称将 在 2 度顶点内收缩
两个图
图的可平面性在同胚意义下不变。
库拉托夫斯基定理¶
图
库拉托夫斯基定理可以等价叙述为:「图
是非可平面的当且仅当它含有与 或 同胚的子图」
给定图
- 图
是可平面图当且仅当其基础简单图是可平面图 - 图
是可平面图当且仅当它的每个块是可平面图
初等收缩¶
设
一个图
瓦格纳定理¶
简单图
该定理和库拉托夫斯基定理是等价的。
至少有 9 个点的简单可平面图的补图是不可平面的,而 9 是这种数目中最小的一个
平面性的拓扑不变量¶
亏格¶
环柄¶
在边交叉处建立的“立交桥”,通过环柄使得一条边经过“桥下”,另一条边经过“桥上”,使二者分开。
亏格定义¶
若通过加上
- 若
是可平面图,则 ; - 同胚的图是亏格相等;
;
引入亏格的欧拉公式¶
对一个亏格为
结论¶
;- 若
无三角形,则 ; - 若
每个面是三角形,则 ; - 若
每个面是四边形,则 ;
厚度¶
若图
叉数¶
将
糙度¶
图
平面性算法¶
设
的第一条边与最后一条边分别是 与 ; 的内部顶点与 不相交
易证关系
此等价关系的等价类导出的
- 若
是 -片段,则 是连通图 的任何两个顶点都有和 的内部不相交的路相连接- 不计
的顶点,任意两 -片段没有公共顶点
设
和 在 上有三个公共的附着顶点;或- 在
上存在四个顺序排列的顶点 使得 是 的附着顶点并且 是 的附着顶点
冲突的两个片段无法同时平面嵌入到同一个面中
设
设
则称
图
设
假定
算法流程¶
如果
非可平面,通过算法可以得到判定;如果 是可平面图,通过算法,可以给出一种平面嵌入形式。
设
初始取
- 判断
: - 若是空集
则停,返回
可平面。
- 否则
- 确定
的所有片段(桥), - 对每个片段(桥)
,求集合 ,
- 确定
- 判断是否存在片段
,使 : - 若存在
则停 ,返回
不可平面。
- 否则
- 在
的所有片段中确定一个使 最小的片段 ,- (
这 2 步的选取具有随机性,算法的随机性来自于这一步)
- (
- 并取
, - 在片段
上取一条连接 上两个附着点的路 , - 把
画在 的面 内得到 ,
- 在
- 令
,转第1
步