Skip to content

平面图

平面图的基本概念

  • 平面图:若能将无向图 G 无边相交地画在平面上,称 G平面图可平面图
  • 平面嵌入:画出的无边相交的平面图称为平面嵌入
  • 非平面图:不能画出无边相交的平面图的图称为非平面图

面与次数

  • :由 G 的平面嵌入所分割出的区域称为
    • 无限面或外部面:无穷大的面。用 R0 表示。
    • 有限面或内部面:有限大的面。用 R1,R2, 表示。
  • 边界:面 Ri 是包围它的边的组成的回路组
  • 次数:面 Ri 的次数是与边界的长度,即边数,记作 deg(Ri)

握手定理

在平面图中,各面的次数之和等于边数的两倍。

i=1ndeg(Ri)=2m

极大平面图

极大平面图:在平面图 G 中再加一条边,就会使 G 变成非平面图的图称为极大平面图

极大平面图的性质

极大平面图是连通的,且 n(n3) 阶极大平面图中不可能有割点和桥。

Gn(n3) 阶极大平面图当且仅当 G 是简单平面图,且 G 的每个面的次数都为 3

极小非平面图

极小非平面图:在非平面图 G 中去掉一条边,就会使 G 变成平面图的图称为极小非平面图

极小非平面图必为简单图

欧拉公式

G 是一个 nm 条边 r 个面的连通平面图,则

nm+r=2

欧拉公式的推论

Gk 个连通分支的平面图,则

nm+r=k+1

握手定理可得,对于联通的平面图,有

mll2(n2)mll2(nk1)

其中 l=min{deg(Ri)}

证明:

2m=i=1rdeg(Ri)rl(nk1)l

根据握手定理极大平面图的性质,可得 设 Gnm 条边的极大平面图,则

m=3n6

Gn(n3)m 条边的简单平面图,则

m3n6

注意,此推论为简单平面图的必要条件,不是充分条件。

G 为简单平面图,则

δ(G)5

用反证法证明。

平面图的判断

插入 2 度顶点与消去 2 度顶点

  • 插入 2 度顶点:设 e=(u,v)G 的一条边,uv 之间插入一个顶点 w,并将 e 替换为 (u,w)(w,v) 两条边,称作在 G 中插入 2 度顶点 w
  • 消去 2 度顶点:设 wG 的一个 2 度顶点,wuv 相连,将 wuv 相连的两条边替换为一条边 e=(u,v),并删除 w,称作在 G 中消去 2 度顶点 w

插入2度顶点与消去2度顶点

同胚

G1G2 在反复进行插入 2 度顶点和消去 2 度顶点的操作后同构,则称 G1G2 同胚

平面图判定定理

  1. G 是平面图 G 不含同胚于 K5K3,3 的子图。
  2. G 是平面图 G 中无 可 收缩K5K3,3 子图。

平面图的对偶图

G 是某平面图的某个平面嵌入,构造 G 的对偶图如下:

  1. G 的每个面 Ri 对应 G 的一个顶点 vi
  2. G 的每条边对应 G 的一条边。即若 eRiRj 的边界,则 vivj 之间有一条边。
    • eRi 的边界且是桥,即 e 只属于 Ri,则 vi 与自身有一条边。

对偶图的性质

GG 的对偶图,则

  1. G 也是平面图,且是平面嵌入。
  2. G 是连通图。
  3. G 是连通图,则 GG
  4. G 中的环对应 G 中的桥,G 中的桥对应 G 中的环。
  5. n=r,m=m,r=nk+1
  6. G 中的顶点 vi 位于 G 的面 Ri 的内部,则 d(vi)=deg(Ri)

GG,则称 G自对偶图

轮图

轮图定义如下: 在 Cn1n4)边形内放置一个顶点,使得这个顶点与 Cn1 上的所有顶点均相邻。所得的 n 阶简单图称为 n阶轮图,常记为 Wn

  • n 为奇数时,称为 奇阶轮图
  • n 为偶数时,称为 偶阶轮图

轮图是自对偶图

离散数学复习笔记