Komari
《图论导论》平面图

Indexed transmission

《图论导论》平面图

Received
Collection
graph_theory
Read
8 分钟
Signal taxonomy 定义核心性质
目录 0%

平面图(Planar Graph)的基本知识

平面图(planar graph)的定义：平面图是指不存在交叉(crossing)、能被完整体现在平面(draw in the plain)上的图。

瓦格勒(Wagner,1936)-珐里定理(Fáry,1948)：一个简单平面图的任意边都是直线。

交叉数
在平面上绘制一个图 G 时，所需要的最少的边的交叉数量；如对于平面图，交叉数为0

库拉托斯基(Kuratowski)定理：一个图是平面图，当且仅当它不包含任何与K5K_5 或K3,3K_{3,3}同胚的子图

瓦格纳(Wagner)定理：一个图是平面图当且仅当它的任何子图都不能通过边的收缩得到K5K_5 或K3,3K_{3,3}

从库拉托斯基(Kuratowski)定理到瓦格纳(Wagner)定理
假定图G不是平面图，则其包含与K5K_5 或K3,3K_{3,3} 同胚的子图，将这些同胚子图中度为二的节点去除，则可以收缩得到K5K_5 或K3,3K_{3,3}，从而顺利切换到了瓦格纳定理

同胚 (Homeomorphic)
如果两个图可以从同一个原始图通过“在边上插入度为2的新顶点” 得到，那么这两个图同胚

无限可数平面图的证明：如果G是可数图，且其的每个有限子图为平面图，则G是平面图

证明过程
把GG 的顶点按序列列出为v1,v2,…v_1,v_2,\dots。令GiG_i 为v1,…,viv_1,\dots,v_i 所诱导的有限子图，则每个GiG_i 都可平面嵌入。
对于每个ii，记EiE_i 为GiG_i 的所有平面嵌入（按顶点处的环序或同胚类计）。注意每个EiE_i 是有限的（因为每个顶点的循环顺序是有限的），且若e∈Eie \in E_i 与e′∈Ei+1e' \in E_{i+1} 满足e′e' 限制到前ii 个顶点时等于ee，则称e′e' 是ee 的延拓。
构造分层有向图（或有根的有限分支树）TT：顶点集为⋃iEi\bigcup_i E_i，只在相邻层间连接“延拓”关系。从任一层出发出度有限且层数无限，所以TT 是一棵无限且有限分支的树。由柯尼希引理（König’s lemma）可知，TT 上存在无限向下路径：

e1→e2→e3→⋯ ,ei∈Ei,e_1 \to e_2 \to e_3 \to \cdots, \qquad e_i \in E_i,

其中每个ei+1e_{i+1} 都延拓eie_i。
于是对任意ii，eie_i 给出了GiG_i 的无交嵌入，且这些嵌入相互兼容。将这些兼容嵌入按层取并（对每个顶点/边取某一层以后固定的图像），得到对整个GG 的映射。任一有限子图落在某个GiG_i 中，因此其图像无交；故全图的映射也是无交的平面嵌入。因此GG 为平面图。

欧拉等式

面(face)的定义：被图的顶点和边划分出的一个个独立区域，被称为面(face)，无限面(infinite face) 则是唯一不被包围的、包含图外所有无限延伸的区域。

球极平面投影(stereographic projection)
无限面和其它面是平等的，这里用球极平面投影(stereographic projection)可以证明，步骤如下：

  1. 从平面到球面： 拿一个球体，把它放在我们画好的平面图上，让球的“南极”与平面接触；从球的“北极”点亮一盏灯。平面图上的每一个点和每一条线，都会在球的表面上投下影子；我们就把整个平面图“画”到了球面上
  2. 在球面上的观察： 当图被画到球面上之后，无限的外部区域，在球面上变成了包含“北极”点的一块有限的“补丁”；球面被图的线条分成了多个小块，所有这些面在地位上都是平等的，就像足球上的色块一样，没有哪个是“外面”的，此时也没有“无限面”了
  3. 从球面回到平面： 现在可以随意转动这个球再进行一次相反的投影；结果无边界的无限面和普通的内部面发生内部互换，但实际整体上并没有变化 描述文字

欧拉公式(Euler’s Formula)： 令G为平面连通图的平面画法，n,m,fn,m,f分别为该图的顶点、边和面，则三者满足：

n−m+f=2n-m+f=2

上述公式的证明并不难，采用归纳法即可完成证明。

平面连通图(Connected Plannar Graph)
平面连通图并不是说该图就是平面的，这是一个性质或潜力的描述。它指的是一个图有没有可能被画在一个平面（比如一张纸）上，并且所有的边除了在顶点处之外，互相不交叉。一个图是“平面图(Plannar Graph)” ，不代表它现在画出来的样子就没有交叉。它仅仅意味着存在至少一种能让它没有交叉的画法。如果一个图不是平面图（比如K5K_5），那么它就不可能有“平面画法(Plane Drawing)” 。如果一个图是平面图，那么它至少有一个“平面画法”。
描述文字

多面体图引理及其推广： 对于多面体图及相关推广有两条引理

  • 令G为多面体图，其满足等式n−m+f=2n-m+f=2
  • 令G为平面图，其具有n个节点、m条边、f个面和k个连通分量，则有等式n−m+f=k+1n-m+f=k+1 (证明方法：对不同的连通分量分别应用欧拉公式，然后进行整合)

简单图的一些引理和定理：

  • 如果G是简单连通平面图，且有n(大于等于3)个节点和m条边，则m≤3n−6m \le 3n-6；如果G不存在三角形结构，则m≤2n−4m \le 2n-4
  • K5K_5和K3,3K_{3,3}都是非平面图
  • 任意简单平面图G中，至少存在一个节点的度小于等于5

概念回顾：简单图、连通图、平面图
简单图是无重边、无自环的图，连通图是任意两点可达的图，平面图是边不交叉的图

图的厚度(thickness)： 将图G所有边分解成最少的若干个平面子图所需的数量

对于一个简单图，假设其有n(大于等于3)个节点和m条边，则有如下不等关系：

t(G)≥⌈m3n−6⌉,t(G)≥⌊m+3n−73n−6⌋t(G) \ge \lceil \frac{m}{3n-6} \rceil , \quad t(G) \ge \lfloor \frac{m+3n-7}{3n-6} \rfloor

关键不等式
对于向上取整和向下取整之间，满足不等式：
⌈ab⌉=⌊a+b−1b⌋\lceil \frac{a}{b} \rceil = \lfloor \frac{a+b-1}{b} \rfloor

对偶图(Dual Graph)

构架过程：给定一个平面图GG ，可以构建图GG 的对偶图，记作G∗G^* ，其构建方式分为两步：

  • 在图GG 内的每个面内选择点v∗v^* ，作为G∗G^* 的顶点
  • 针对图GG 的每条边，绘制边e∗e^* 穿过图GG 的一条边ee 、连接位于ee 所毗邻的面ff 中的顶点v∗v^*
描述文字

对偶图的一些关系

如果GG 为平面图且连通，则G∗G^* 也为平面图且连通，同时图GG 和图G∗G^* 在顶点、边和面上存在一些关系。

令图GG 为具有nn 个顶点、mm 条边、ff 个面的连通平面图，令其的对偶图具有G∗G^* 具有n∗n^* 个顶点、m∗m^* 条边、f∗f^* 个面，则有下述三个等量关系，其中第三个可以通过欧拉公式证明：

n∗=f,m∗=m,f∗=nn^*=f, m^*=m, f^*=n

同构性质：当GG 为平面图且连通，则G∗∗G^{**} 和GG 是同构的