平面图

平面图的概念与性质

定义

• 能把图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中，如此重复

    • 直观点，就是找圈，然后看圈里的那些边(端点附着在圈上)，看它们是属于哪个面的(附着点均在哪个面的边界上，一个边可能可以属于多个面)，然后选择可能性最小的边，把它画上去，当然，一旦画上去，就会多一个面，这也无妨，继续走下去，直到画完，最终就是一个平面图，但也可能遇到有边，哪个面都不属于，直观上反应，它怎么画都会和别的边交叉，此时停止，说明不可平面
    • 具体的看那个例题，基本可以解决所有的问题

什么是超平面

我们最常见的平面概念是在三维空间中定义的:

• 方程是线性的: 是空间点的各分量的线性组合
• 方程数量为1

若抛却维度等于3的限制, 就得到了超平面的定义. 方程数量为1, 它的本质其实是自由度比空间维度 d 小一.自由度的概念可以简单的理解为至少要给定多少个分量的值才能确定一个点. 例如, 三维空间里的(超)平面只要给定了 (x,y,z)    中任意两个分量, 剩下的一个的值就确定了. 先确定值的两个分量是自由的, 因为它们想取什么值就能取什么值;剩下的那个是"不自由的", 因为它的值已经由另外两确定了.二维空间里的超平面为一条直线. 一维空间里超平面为数轴上的一个点.
现在用数学语言定义一下.
d 维空间中的超平面由下面的方程确定:

w

二维平面就是（w1,w2）(x1;x2)+b=0,即w1x1+w2x2+b=0。（直线方程）

点到超平面的距离

假设点 x′ 为超平面 A:wTx+b=0 上的任意一点, 则点 x 到 A 的距离为 x−x′在超平面法向量 w 上的投影长度:

超平面的正面与反面

一个超平面可以将它所在的空间分为两半, 它的法向量指向的那一半对应的一面是它的正面, 另一面则是它的反面.

判断一个点是在超平面的正面还是反面(面向的空间里)

还是要用到它的法向量 w .
仍然假设点 x′ 为超平面 A:wTx+b=0 上的任意一点, 点 x 为待判断的点.

若x−x′    与 w 的夹角小于 90∘ , 则 x 在 A 的正面, 否则在反面

所以判定依据为:

若将距离公式中分子的绝对值去掉, 让它可以为正为负. 那么, 它的值正得越大, 代表点在平面的正向且与平面的距离越远. 反之, 它的值负得越大, 代表点在平面的反向且与平面的距离越远.

http://blog.163.com/zhuandi_h/blog/static/180270288201261911146436/