84平面图 平面图与平面嵌入 平面图的面、有限面、无限面 面的次数 极大平面图 极小非平面图 欧拉公式 平面图的对偶图
1 8.4 平面图 ▪ 平面图与平面嵌入 ▪ 平面图的面、有限面、无限面 ▪ 面的次数 ▪ 极大平面图 ▪ 极小非平面图 ▪ 欧拉公式 ▪ 平面图的对偶图
平面图和平面嵌入 定义如果能将图G除顶点外边不相交地画在平面上, 则称G是平面图.这个画出的无边相交的图称作G 的平面嵌入.没有平面嵌入的图称作非平面图 例如下图中(1)(4)是平面图,(2)是(1)的平面嵌入 (4)是(3)的平面嵌入.(5是非平面图 (2) (4) (5)
2 平面图和平面嵌入 定义 如果能将图G除顶点外边不相交地画在平面上, 则称G是平面图. 这个画出的无边相交的图称作G 的平面嵌入. 没有平面嵌入的图称作非平面图. 例如 下图中(1)~(4)是平面图, (2)是(1)的平面嵌入， (4)是(3)的平面嵌入. (5)是非平面图
平面图和平面嵌入(续) ●按定义,平面图不一定是平面嵌入.但今后讨论性质时,通 常是针对平面嵌入的今后平面图均指它的一个平面嵌入 K和K33是非平面图 设G'cG,若G为平面图,则G也是 平面图;若G为非平面图,则G也 是非平面图 K(≥5,K3n(m≥3)都是非平面图 °平行边与环不影响图的平面性
3 平面图和平面嵌入(续) • 按定义, 平面图不一定是平面嵌入. 但今后讨论性质时, 通 常是针对平面嵌入的.今后平面图均指它的一个平面嵌入. • K5和K3,3是非平面图 • 设GG,若G为平面图,则G也是 平面图; 若G为非平面图,则G也 是非平面图. • Kn (n5), K3,n (n3)都是非平面图. • 平行边与环不影响图的平面性. K5 K3,3
平面图的面与次数 设G是一个平面嵌入 G的面:由G的边将平面划分成的每一个区域 无限面(外部面:面积无限的面,用R0表示 有限面(内部面:面积有限的面,用R1,R2,R表示 面R的边界:包围R的所有边构成的回路组 面R的次数:R边界的长度,用deg(R)表示 说明:构成一个面的边界的回路组可能是初级回路,简单回 路,也可能是复杂回路,甚至还可能是非连通的回路之并 定理平面图各面的次数之和等于边数的2倍
4 平面图的面与次数 设G是一个平面嵌入 G的面: 由G的边将平面划分成的每一个区域 无限面(外部面): 面积无限的面,用R0表示 有限面(内部面): 面积有限的面,用R1 , R2 ,…, Rk表示 面Ri的边界: 包围Ri的所有边构成的回路组 面Ri的次数: Ri边界的长度，用deg(Ri )表示 说明: 构成一个面的边界的回路组可能是初级回路, 简单回 路, 也可能是复杂回路, 甚至还可能是非连通的回路之并. 定理 平面图各面的次数之和等于边数的2倍
平面图的面与次数(续) 例1右图有4个面,deg(R1)=1, R deg(r,)=3, deg(r3)=2, rag deg(R0)=8.请写各面的边界 R 例2左边2个图是同一个平面 R 图的平面嵌入.R1在(1)中是 R R 外部面,在(2)中是内部面;R2 R 在(1)中是内部面,在(2)中是 R,外部面其实,在平面嵌入中 (1) (2) 可把任何面作为外部面
5 平面图的面与次数(续) 例1 右图有4个面, deg(R1 )=1, deg(R2 )=3, deg(R3 )=2, deg(R0 )=8. 请写各面的边界. 例2 左边2个图是同一个平面 图的平面嵌入. R1在(1)中是 外部面, 在(2)中是内部面; R2 在(1)中是内部面, 在(2)中是 外部面. 其实, 在平面嵌入中 可把任何面作为外部面