图论讲义第7章平面图VIP免费

1第七章 平面图 §7.1 平面图的概念 定义 7.1.1 如果图 G 能画在曲面 S 上，使得任意两边互不交叉，则称 G 可嵌入曲面 S。若图 G 可嵌入平面，则称 G 是可平面图或平面图，画出的无交叉边的图形称为图 G 的平面嵌入。 例如，下面是三个平面图及其平面嵌入。 根据定义，下列定理是显然的。 定理 7.1.1 若图 G 是平面图，则 G 的任何子图都是平面图。 定理 7.1.2 若图 G 是非平面图，则 G 的任何母图都是非平面图。 定理 7.1.3 若图 G 是平面图, 则在 G 中添加重边或环边后所得之图仍是平面图。 注：由以上定理知 (1) Kn ( n≤4 ) 和 K1,n (n ≥ 1)及其所有子图都是平面图。 (2) 环边和重边不影响图的平面性。故以下讨论平面性时总假定图 G 是简单图。 定义 7.1.2 设图 G 是平面图 (已平面嵌入)，G 的边将平面划分出的若干区域都称为图 G 的面。其中面积无限的面称为无限面或外部面，面积有限的面称为有限面或内部面。包围一个面的所有边称为该面的边界。一个面边界上的边数称为该面的次数 (割边按两次计)，面 R 的次数记为 deg(R)。 定理 7.1.4 平面图 G 中所有面的次数之和等于 G 的边数的两倍，即 其中 R1, R2, … , Rr是 G 的所有面。 证明： 对 G 的任何一条边 e，若 e 是两个面 Ri 和 Rj 的公共边界，则在计算 Ri 和 Rj 的次数时，e 各提供了 1；若 e 只是某一个面的边界，则在计算该面的次数时，e 提供了 2。可见每条边在计算总次数时，都提供 2。因而结论成立。 1deg()2 ( ).riiRGε==∑ 2定义7 .1 .3 设G 为简单平面图，若在G 的任意不相邻的顶点u, v 之间加边uv 后，所得之图成为非平面图，则称G 是极大平面图。 易见K1, K2, K3, K4, K5– e 都是极大平面图。 定义7 .1 .4 若非平面图G 任意删除一条边后，所得之图都是平面图，则称G 为极小非平面图。 容易证明下列定理 定理7 .1 .5 极大平面图是连通的。 定理7 .1 .6 n 阶（ n ≥ 3）极大平面图中没有割边和割点。 §7 .2 欧拉公式 定理7 .2 .1 （欧拉公式）设G 是连通的平面图，n, m, r 分别是其顶点数、边数和 面数，则 n – m + r = 2。 证明：对边数 m 作数学归纳法。 当 m=0 时，因 G 是连通图，所以 G 只能是平凡图，结论显然成立。 假设当 m=k 时，结论成立。下面证明 m=k+1 的情况。 ...