图论 王智慧 复旦大学计算机学院
图论 王智慧 复旦大学计算机学院
平面图 平面图的基本概念 欧拉公式 平面图的判断 平面图的对偶图
2 平面图 • 平面图的基本概念 • 欧拉公式 • 平面图的判断 • 平面图的对偶图
平面图的定义 定义1 若图G能以除顶点外无边相交的方式画在曲面上,则称G可嵌入 曲面.若G可嵌入平面,则称G是可平面图或平面图 画出的无边相交的图称为G的平面嵌入;无平面嵌入的图称为非 平面图
3 平面图的定义 定义1. 若图G能以除顶点外无边相交的方式画在曲面上, 则称G可嵌入 曲面. 若G可嵌入平面, 则称G是可平面图或平面图. 画出的无边相交的图称为G的平面嵌入; 无平面嵌入的图称为非 平面图
基本定理 定理1.若图G是平面图,则G的任何子图都是平面图。 定理2.若G是非平面图,则G的任何母图也都是非平面图。 定理3.设G是平面图,则在G中加平行边或环后所得图还是平面图 本定理说明平行边和环不影响图的平面性,因而在研究图是否 为平面图时,可不考虑平行边和环
4 基本定理 定理1. 若图G是平面图, 则G的任何子图都是平面图。 定理2. 若G是非平面图, 则G的任何母图也都是非平面图。 本定理说明平行边和环不影响图的平面性, 因而在研究图是否 为平面图时, 可不考虑平行边和环。 定理3. 设G是平面图, 则在G中加平行边或环后所得图还是平面图
平面嵌入 定义2. 设G是平面图且已是平面嵌入,由G的边将G所在的平面划分成若干个 区域,每个区域都称为G的一个面.其面积无限的面称为无限面或外部面; 面积有限的面称为有限面或内部面.包围每个面的所有边组成的回路组称 为该面的边界;边界的长度称为该面的次数 常记外部面为R,内部面为R1,R2…,R,面R的次数记为deg(R) 5
5 平面嵌入 定义2. 设G是平面图且已是平面嵌入, 由G的边将G所在的平面划分成若干个 区域, 每个区域都称为G的一个面. 其面积无限的面称为无限面或外部面; 面积有限的面称为有限面或内部面. 包围每个面的所有边组成的回路组称 为该面的边界; 边界的长度称为该面的次数。 常记外部面为R0, 内部面为R1, R2, …, Rk, 面R的次数记为deg(R)