王智慧复旦大学计算机学院.PDF

图论 王智慧 复旦大学计算机学院 平面图 • 平面图的基本概念 • 欧拉公式 • 平面图的判断 • 平面图的对偶图 2 平面图的定义 定义1. 若图G能以除顶点外无边相交的方式画在曲面上, 则称G可嵌入 曲面. 若G可嵌入平面, 则称G是可平面图或平面图. 画出的无边相交的图称为G的平面嵌入; 无平面嵌入的图称为非 平面图. 3 基本定理 定理1. 若图G是平面图, 则G的任何子图都是平面图。 定理2. 若G是非平面图, 则G的任何母图也都是非平面图。 定理3. 设G是平面图, 则在G中加平行边或环后所得图还是平面图。 本定理说明平行边和环不影响图的平面性, 因而在研究图是否 为平面图时, 可不考虑平行边和环。 4 平面嵌入 定义2. 设G是平面图且已是平面嵌入, 由G的边将G所在的平面划分成若干个 区域, 每个区域都称为G的一个面. 其面积无限的面称为无限面或外部面; 面积有限的面称为有限面或内部面. 包围每个面的所有边组成的回路组称 为该面的边界; 边界的长度称为该面的次数。 常记外部面为R , 内部面为R , R , …, R , 面R的次数记为deg(R). 0 1 2 k 5 平面嵌入 定理4. 平面嵌入图G中所有面的次数之和等于边数m的两倍, 即 Σ deg(R ) = 2m, 其中r为G的面数. i=1..r i 证明: 对于任意的e∈E(G), 分以下情况考虑: 若e为面R 和R (i ≠j) 的公共边界上的边时, 在计算R 和R 的次 i j i j 数时, e各被计算1次; 当e只在某一个面的边界上出现时, 则在计算该面的次数时, e 被计算2次; 所以, 每条边在计算总次数时, 都被计算2次。 因此, Σ deg(R ) = 2m。 i=1..r i 6 极大平面图 定义3. 设G为简单平面图, 若在G的任意不相邻的顶点u, v之间加 边(u, v), 所得图为非平面图, 则称G为极大平面图。 定理5. 极大平面图是连通的。 定理6. 设G是n(n ≥3)阶极大平面图, 则G中不可能存在割点和桥。 7 极大平面图 定理7. 设G为n(n ≥3)阶简单连通的平面图, G为极大平面图, 当且仅当G 的每个面的次数均为3。 证明: 先证明该定理的必要性。其充分性在后续部分再证明. 因为G为简单平面图, 所以, G中无环和平行边。由定理5和定理6可知, G中无割点和桥。于是G中各面的次数大于或等于3, 下面只需证明: G中各 面的次数不可能大于3。 假设面R 的次数deg(R ) = s 3。 i i 在G中, 若v 与v 不相邻, 在R 内加边(v , v )不破坏平面性, 这与G是极 1 3 i 1 3 大平面图矛盾, 因此, v 与v 必相邻。由于R 的存在,边(v , v )必在R 外. 类 1 3 i