平面图
平面图的概念与性质
定义
- 能把图G花在平面上，使得边与边之间没有交叉，称G可以嵌入平面，或称G是可平面图。G的平面嵌入表示的图称为平面图
-
一个平面图G把平面分成若干连通片，这些连通片称为G的一个面或区域，G的面组成的集合用Φ表示
- 其中面积有限的区域称为平面图G的内部面，否则，称为外部面
-
Jordan曲线
-
一条连续的，自身不交的，起点和终点重合（封闭的）曲线，平面图中圈中的各条边构成一条Jordan曲线
- 这个线是真实存在的，不是你自己想象的···
-
Jordan曲线定理：平面上任意简单闭合的曲线J把平面其余部分划分内部和外部
-
-
面的次数deg(f)
- 面的边界的边数，割边算2次
性质
-
欧拉公式
-
欧拉公式：G(m,n)是连通平面图，φ是G的面数，则n-m+φ=2
- 证明：数学归纳法即可，比较简单，假设n-1成立，然后n那里减去一条非割边，则面数-1，且边数-1，点数不变
-
推论1：设G是具有φ个面k个连通分支的平面图，则n-m+φ=k+1
-
推论2：设G是具有n个点m条边φ个面的连通平面图，如果对G的每个面f，有：deg(f)≥l≥3，则m≤(n-2)l/(l-2)
- 这里有2m=∑deg(f)，也就难怪之前割边要算两次了，因为一条非割边肯定是要作为两个面的边界的
- 然后证明主要由2m=∑deg(f)和欧拉公式来求
-
推论3：设G是具有n(n≥3)个点m条边φ割面的简单平面图，则m≤3n-6
- 推论4：设G说是具有n(n≥3)个点m条边φ割面的简单平面二部图，则：m≤2n-4
-
推论5：设G是具有n个点m条边的连通平面图，若G的每个圈均由长度是l的圈围成，则m(l-2)=l(n-2)
- 由次数公式，欧拉公式易得
-
推论6：设G是具有n个点m条边的简单平面图，则δ≤5
- 若不然，由握手定理会得m>3n-6不可平面
-
这里的性质都是 不可平面的判定条件（必要条件，而不充分）
- 这里的推论之后可以好好的证明一哈
-
-
定理：一个连通图是2连通的，当且仅当它的每个面的边界是圈
特殊平面图
极大平面图
-
对于一个简单平面图，在不邻接顶点对间加边，当边数增加到一定数量时，就会变成非平面图
- 平面图的极图
- 只有在简单图的前提下极大平面图才有意义
-
K1-K4都是极大平面图
- K5非平面图
-
设G是极大平面，则G必然连通，若G阶数的大于等于3，则G无割边
-
性质
-
定理1：设G是n阶简单平面图，则下面命题等价
- G是极大平面图
- G每个面的次数是3
- G有3n-6条边
-
推论：设G是n个点，m条边和φ个面的极大平面图，且n≥3，则φ=2n-4
-
极大外平面图
-
定义
- 若一个可平面图G存在一种平面嵌入，使其所有顶点均在某个面的边界上，称该图为外可平面图
-
2-连通的外平面图的外面边界是哈密尔顿圈
- 设G是一个连通简单外可平面图，则再G中有一个度数至多是2的顶点
- 定理2：设G是一个有n(n≥3)个点，且所有点均在外部面上的极大外平面图，则G有n-2个内部面
- 定理3：设G是一个有n个点，且所有点均在外部面上的外平面图，则G是极大外平面图，当且仅当其外部面的边界是圈，内部面是三角形
平面图的对偶图
对偶图的定义
- 每个面取做一个点，然后两个面相邻，就连边，相邻几条边，就画几个重边，若是自己有割边，则自己画自环
对偶图(G')的性质
- G’的顶点数等于G的面数
- G‘的边数等于G的边数
- G’的面数等于G的顶点数
- d(v')=deg(f)
- 对偶图的对偶图就是原图（当且仅当G是连通的）
定理5：平面图G的对偶图必然连通
- 因为面之间一定相互邻接，所以对偶图一定连通
同构的平面图可以有不同构的对偶图
平面图的判定
相关概念
-
剖分
- 一条边上插入一个2度顶点，使一条边分成两条边
-
内收缩(简化)
- 去掉一个图的2度顶点，使关联它们的两条边合并成一条边
-
同胚的
- 两图同构，或通过反复剖分和内收缩能变成同构
-
初等收缩子图
- 对G进行一系列删点，删边或边收缩运算得到的基础简单图
定理1：图G是可平面的，当且仅当它不含K5和K3,3同胚的子图
- 感觉没啥用
定理2：（1）图G是可平面的，当且仅当它的基础简单图是可平面的（2）图G是可平面图当且仅当G的每个块是可平面图
定理3：简单图G是可平面图当且仅当它不包含K5或K3,3的初等收缩子图
平面性的不变量
懒得看，感觉不考···
平面图算法
定义
-
H为G的真子图，E(G)-E(H)被划分成一些类
- G-V(H)的每个分支F以及F连向H的边
- e的端点在V(H)上，但e不在E(H)中，其作为一个孤立类
-
由H的这些类在G中的边导出子图称为G的H-片段，片段与H的公共顶点称为附着顶点
-
冲突
-
令C是图G的一个圈，G的两个C-片段A和B是冲突的
- 1）A和B在C上有三个公共的附着点
- 2）在C上存在四个顺序排列的顶点v1,v2,v3,v4，其中v1，v3是A的附着点，v2，v4是B的附着点
-
C的冲突图
- 顶点为G的C-片段，若C的两个片段冲突，则再冲突图中相邻
-
定理4：图G是可平面的当且仅当对G的每个圈C，C的冲突图是二部图
-
F(B,G)={f|f是G的面，且B的附着点均在f的边界上}
- B是片段
- F(B,G)是集合
- 注意是均哦
- 这里的面是针对C的面，而不是针对G的面
平面图算法（DMP）
-
算法流程
-
先找一个圈H，然后获取所有的圈片段，之后求F(B,G)，选择一个|F|最小的，在该片段中取一条连接圈中两个附着点的路Pi，把它画进H中，如此重复
- 直观点，就是找圈，然后看圈里的那些边(端点附着在圈上)，看它们是属于哪个面的(附着点均在哪个面的边界上，一个边可能可以属于多个面)，然后选择可能性最小的边，把它画上去，当然，一旦画上去，就会多一个面，这也无妨，继续走下去，直到画完，最终就是一个平面图，但也可能遇到有边，哪个面都不属于，直观上反应，它怎么画都会和别的边交叉，此时停止，说明不可平面
- 具体的看那个例题，基本可以解决所有的问题
-