Skip to content

平面图

如果能把图 G 画在平面上,使得除顶点外,边与边之间没有交叉,称 G 可嵌入平面,或称 G 是可平面图

可平面图 G 的边不交叉的一种画法,称为 G 的一种平面嵌入G 的平面嵌入表示的图称为平面图

可平面图概念和平面图概念有时可以等同看待;

图的平面性问题主要涉及如下几个方面:

  • 平面图的性质
  • 平面图的判定
  • 平面嵌入方法(平面性算法)
  • 涉及图的平面性问题的拓扑不变量

平面图的性质

一个平面图 G 把平面分成若干连通片,这些连通片称为 G区域,或 G 的一个G 的面组成的集合用 Φ 表示。

面积有限的区域称为平面图 G内部面,否则称为 G外部面

G 中,顶点和边都与某个给定区域关联的子图,称为该面的边界。某面 f 的边界中含有的边数 (割边计算 2 次⚠) 称为该面 f次数, 记 degf

平面图的次数公式

G=(n,m) 是平面图,则:

fΦdeg(f)=2m

证明:

G 的任意一条边 e, 如果 e 是某面割边,那么由面的次数定义,该边给 G 的总次数贡献 2 次;如果 e 不是割边,那么,它必然是两个面的公共边,因此,由面的次数定义,它也给总次数贡献 2 次。

连通平面图的欧拉公式

G=(n,m)连通平面图,φG 的面数,则:

nm+φ=2

证明:

情形 1,如果 G 是树。

那么 m=n1, 𝜑=1。在这种情况下,容易验证,定理中的恒等式是成立的。

情形 2, G 不是树的连通平面图。

假设在这种情形下,欧拉恒等式不成立。则存在一个含有最少边数的连通平面图 G,使得它不满足欧拉恒等式。设这个最少边数连通平面图 G=(n,m),面数为 𝜑,则:

nm+φ2

因为 G 不是树,所以存在非割边 e。显然,Ge 是连通平面图,边数为 m1,顶点数为 n,面数为 𝜑1。由最少性假设Ge 满足欧拉等式:

n(m1)+(φ1)=2nm+φ=2

于是矛盾,假设不成立。

非连通平面图的欧拉公式

G=(n,m)k 个连通分支的平面图,φG 的面数,则:

nm+φ=k+1

证明:

对第 i(1ik) 个分支来说,设顶点数为 ni,边数为 mi,面数为 𝜑i,由欧拉公式:

nimi+φi=2i=1k(nimi+φi)=2ki=1knii=1kmi+i=1kφi=2k

同时:(扣除重复计算的 k1 个外部面)

i=1kni=n,  i=1kmi=m,  i=1kφi=φ+k1

于是得到:

nm+(φ+k1)=2knm+φ=k+1

G 是具有 n 个点 m 条边 𝜑 个面的连通平面图,如果对 G 的每个面 f,有 degfl3,则:

mll2(n2)

Warning

这是连通平面图的必要条件,不是充分条件!

G 是具有 n 个点 m 条边 𝜑 个面的连通平面图,有:

m3n6

G 是具有 n 个点 m 条边 𝜑 个面的连通平面图,如果对 G 的每个面 f,有 degf=l,则:

m(l2)=l(n2)

G 是具有 n 个点 m 条边 𝜑 个面的连通平面图,有:

δ5

Abstract

该结论是证明“5 色定理”的出发点

一个连通平面图是 2 连通的,当且仅当它的每个面的边界是圈。

图的嵌入性问题

曲面嵌入

球面嵌入

⭐ G 可球面嵌入与 G 可平面嵌入等价

我们实际上对图的嵌入性问题也只考虑这两个。

环面嵌入

定向曲面嵌入

3 维空间嵌入

所有图均可嵌入 R3 中。

凸多面体与平面图

一个多面体称为凸多面体,如果在体上任取两点,其连线均在体上。

凸多面体的一维骨架:把一个凸多面体压缩在平面上,得到一个对应的平面图,该平面图称为该凸多面体的一维骨架。

存在且只存在 5 种正多面体:它们是正四、六、八、十二、二十面体

平面图的判定

同胚

  • 在图 G 的边上插入一个新的 2 度顶点,使一条边分成两条边,则称将图 G 在 2 度顶点内扩充
  • 去掉图 的一个 2 度顶点,使这个 2 度顶点关联的两条边合成一条边,则称将 G 在 2 度顶点内收缩

两个图 G1G2,如果 G1G2,或者通过反复在 2 度顶点内扩充和收缩它们能变成同构的,则称 G2G2同胚的,或 G1G2 2 度顶点内是同构的

⭐图的可平面性在同胚意义下不变。

库拉托夫斯基定理

G 是可平面的当且仅当它不含与 K5K3,3 同胚的子图

库拉托夫斯基定理可以等价叙述为:「图 G 是非可平面的当且仅当它含有与 K5K3,3 同胚的子图」

给定图 G,去掉 G 中的环 (若有的话),将 G 中的重边 (若有的话) 用单边代替,称这样所得的图为 G基础简单图

  • G 是可平面图当且仅当其基础简单图是可平面图
  • G 是可平面图当且仅当它的每个块是可平面图

初等收缩

uv 是简单图 G 的一条边。去掉该边,重合其端点,再删去由此产生的环和重边。这一过程称为图 G初等收缩收缩边 uv 的运算,并记所得之图为 G/uv

一个图 G 可收缩到 H,是指 H 可从 G 通过一系列初等收缩而得到。

瓦格纳定理

简单图 G 是可平面图当且仅当它不含可收缩到 K5K3,3 的子图。

该定理和库拉托夫斯基定理是等价的。

至少有 9 个点的简单可平面图的补图是不可平面的,而 9 是这种数目中最小的一个

平面性的拓扑不变量

亏格

环柄

在边交叉处建立的“立交桥”,通过环柄使得一条边经过“桥下”,另一条边经过“桥上”,使二者分开。

亏格定义

若通过加上 k 个环柄可将图 G 嵌入球面,则 k 得最小值称为 G亏格,记为:

γ(G)
  • G 是可平面图,则 γ(G)=0
  • 同胚的图是亏格相等;
  • γ(K5)=1

引入亏格的欧拉公式

对一个亏格为 γ,有 n 个顶点,m 条边和 φ 个面的多面体或连通图,有:

nm+φ=22γ

结论

G 是一个有 n 个顶点,m 条边和 φ 个面的多面体或连通图,有:

  • γm6n22
  • G 无三角形,则 γm4n22
  • G 每个面是三角形,则 m=3(n2+2γ)
  • G 每个面是四边形,则 m=2(n2+2γ)

厚度

若图 Gk 个可平面子图的并等于 ,则称 k 的最小值为 G厚度,记为

G 是可平面图当且仅当 θ(G)=1

叉数

G 画在平面上时相交的边对的最少数目称为 G叉数,记为:

η(G)

G 是可平面图当且仅当 η(G)=0

糙度

G 中边不重的不可平面子图的最多数目称为 G糙度,记为:

ζ(G)

平面性算法

H 是图 G 的一个子图,在 E(G)E(H) 上定义关系 如下:e1e2 当且仅当存在一条途径 W,使得:

  • W 的第一条边与最后一条边分别是 e1e2
  • W 的内部顶点与 H 不相交

易证关系 具有自反性,对称性和传递性,从而是 E(G)E(H) 上的一个等价关系

此等价关系的等价类导出的 GE(H) 的边导出子图称为 H-片段,或者 G 关于 H 的桥。片段或桥与 H 的公共顶点称为附着顶点

  • BH-片段,则 B 是连通图
  • B 的任何两个顶点都有和 H 的内部不相交的路相连接
  • 不计 H 的顶点,任意两 H-片段没有公共顶点

H 是图 G 的一个圈,图 G 的两个 H-片段 B1B2冲突的,如果

  • B1B2H 上有三个公共的附着顶点;或
  • H 上存在四个顺序排列的顶点 v1,v2,v3,v4 使得 v1,v3B1 的附着顶点并且 v2,v4B2 的附着顶点

冲突的两个片段无法同时平面嵌入到同一个面中

H 是图 G 的一个圈,以图 GH-片段为顶点,顶点间连一条边当且仅当对应的 H-片段是冲突的,把这样得到的图称为 H 的冲突图

H 是图 G 的可平面子图,是 H~ 的一种平面嵌入。若 G 也是可平面图,且存在 G 的一个平面嵌入 H~,使得:

H~G~

则称 H~G 容许的。

G 是可平面的当且仅当对 G 的每个圈 H,其冲突图是二部图

H 是图 G 的一个可平面子图,HH 的一个平面嵌入。假定 B 是子图 H 的任一片段,若 BH 的所有附着顶点都位于 H 中某个面 f 的边界上,则称 BH 的面 f 中是可画入的,否则,称为不可画入的。令:

F(B,H)={f|fH的面且Bf中可画入}

假定 H 如实线所示,则片段 B3 在外部面上是可画入的,而 B2 对面 f2f3 均为不可画入的,且 F(B1,H)={f1,f3}

可画入示例

算法流程

如果 G 非可平面,通过算法可以得到判定;如果 G 是可平面图,通过算法,可以给出一种平面嵌入形式。

G 是至少有三个顶点的简单块,取 G 的任意一个圈 H,求出 H 的一个平面嵌入。若无圈,则 G 是一棵树,一定可平面。

初始取 G 的一个圈 H1,并作平面嵌入 H~1。假设 Hi 已确定,下面确定 Hi+1,算法流程如下:

  1. 判断 E(G)E(Hi)=
  2. 若是空集
    • 🖐则停,返回 G 可平面。
  3. 否则
    1. 确定 Hi 的所有片段(桥),
    2. 对每个片段(桥) B,求集合 F(B,Hi)
  4. 判断是否存在片段 B,使 F(B,H~i)=
  5. 若存在
    • 🖐则停 ,返回 G 不可平面。
  6. 否则
    1. Hi 的所有片段中确定一个使 |F(B,H~i)| 最小的片段 B
      • (⭐这 2 步的选取具有随机性,算法的随机性来自于这一步)
    2. 并取 fF(B,H~i)
    3. 在片段 B 上取一条连接 Hi 上两个附着点的路 Pi
    4. Pi 画在 H~i 的面 f 内得到 Hi+1=HiPi
  7. i=i+1,转第 1