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)中是 外部面. 其实, 在平面嵌入中 可把任何面作为外部面
极大平面图 定义若G是简单平面图,并且在任意两个不相邻的顶点之 间加一条新边所得图为非平面图,则称G为极大平面图 性质 ●若简单平面图中已无不相邻顶点,则是极大平面图.如 K1,k2K,K都是极大平面图 ●极大平面图必连通 °阶数大于等于3的极大平面图中不可能有割点和桥 设G为m(m≥3)阶极大平面图,则G每个面的次数均为3 任何n(n≥4)阶极大平面图G均有8(O≥3
6 极大平面图 定义 若G是简单平面图,并且在任意两个不相邻的顶点之 间加一条新边所得图为非平面图,则称G为极大平面图. 性质 • 若简单平面图中已无不相邻顶点，则是极大平面图. 如 K1 , K2 , K3 , K4都是极大平面图. • 极大平面图必连通. • 阶数大于等于3的极大平面图中不可能有割点和桥. • 设G为n(n3)阶极大平面图,则G每个面的次数均为3. • 任何n(n4)阶极大平面图G均有δ(G)3
实例 3个图都是平面图,但只有右边的图为极大平面图
7 实例 3个图都是平面图, 但只有右边的图为极大平面图
极小非平面图 定义若G是非平面图,并且任意删除一条边所得图 都是平面图,则称G为极小非平面图 说明: K,K33都是极小非平面图 极小非平面图必为简单图 下面4个图都是极小非平面图
8 极小非平面图 定义 若G是非平面图, 并且任意删除一条边所得图 都是平面图, 则称G为极小非平面图. 说明: K5 , K3,3都是极小非平面图 极小非平面图必为简单图 下面4个图都是极小非平面图
欧拉公式 定理811(欧拉公式)设G为m阶m条边r个面的连通平面图, 则n-mr=2 证对边数m做归纳证明 mF=0,G为平凡图,结论为真 设m=kE1结论为真,k+时分情况讨论如下: (1)G中无圈,则G必有一个度数为1的顶点v删除v及它关 联的边,记作GG连通,有m-1个顶点,k条边和r个面由归 纳假设,(n-1)-k+r=2,即n-(k+1)+r=2,得证mk+1时结论成立 (2)否则删除一个圈上的一条边记作GG连通,有n个顶 点条边和r-1个面由归纳假设,n-k+(r1)=2,即n(k+1)+r=2, 得证m=k+1时结论也成立证毕
9 欧拉公式 定理8.11 (欧拉公式) 设G为n阶m条边r个面的连通平面图， 则 n−m+r=2. 证 对边数m做归纳证明. m=0, G为平凡图,结论为真. 设m=k(k1)结论为真, m=k+1时分情况讨论如下: (1) G中无圈, 则G必有一个度数为1的顶点v,删除v及它关 联的边,记作G. G连通, 有n-1个顶点, k条边和r个面.由归 纳假设,(n-1)-k+r=2, 即n-(k+1)+r=2, 得证m=k+1时结论成立. (2) 否则,删除一个圈上的一条边,记作G. G连通, 有n个顶 点,k条边和r-1个面.由归纳假设, n-k+(r-1)=2, 即n-(k+1)+r=2, 得证m=k+1时结论也成立.证毕
欧拉公式(续) 欧拉公式的推广 设G是有p(p≥2)个连通分支的平面图,则 n-m+r=p+1 证设第i个连通分支有n个顶点,m条边和r个面 对各连通分支用欧拉公式, ni-mi t ri 求和并注意r=r1+…+rn+p-1,即得 n-mtr=p+ 10
10 欧拉公式(续) 欧拉公式的推广 设G是有 p (p2) 个连通分支的平面图, 则 n − m + r = p + 1 证 设第 i 个连通分支有 ni个顶点, mi条边和 ri 个面. 对各连通分支用欧拉公式, ni − mi + ri = 2, i = 1, 2, … , p 求和并注意 r = r1+…+rp+ p−1, 即得 n − m + r = p + 1