平面图和平面嵌入.ppt

* 6.4 平面图 平面图与平面嵌入 平面图的面 极大平面图与极小非平面图 欧拉公式 平面图的对偶图 地图着色与四色定理 * 平面图和平面嵌入 定义 如果能将图G除顶点外边不相交地画在平面上, 则称G是平面图. 这个画出的无边相交的图称作G的平面嵌入. 没有平面嵌入的图称作非平面图. 例如 下图中(1)~(4)是平面图, (2)是(1)的平面嵌入，(4)是(3)的平面嵌入. (5)是非平面图. * 平面图和平面嵌入(续) 今后称一个图是平面图, 可以是指定义中的平面图, 又可以是指平面嵌入, 视当时的情况而定. 当讨论的问题与图的画法有关时, 是指平面嵌入. K5和K3,3是非平面图 设G ??G, 若G为平面图, 则G ?也是 平面图; 若G ?为非平面图, 则G也 是非平面图. Kn(n?5), Kn,m(n,m?3)都是非平面图. 平行边与环不影响图的平面性. * 平面图的面与次数 设G是一个平面嵌入 G的面: 由G的边将平面划分成的每一个区域 无限面(外部面): 面积无限的面, 用R0表示 有限面(内部面): 面积有限的面, 用R1, R2,…, Rk表示 面Ri的边界: 包围Ri的所有边构成的回路组 面Ri的次数: Ri边界的长度，用deg(Ri)表示 定理 平面图各面的次数之和等于边数的2倍. 证 每条边可能在两个面的公共边界上，也可能只在一个面 的边界上. 前者, 在每个面的边界上这条边只出现一次, 计算 两次. 后者, 它在这个面的边界上出现2次, 也计算两次. * 平面图的面与次数(续) 例1 右图有4个面, deg(R1)=1, deg(R2)=3, deg(R3)=2, deg(R0)=8. 例2 左边2个图是同一个平面图的平面嵌入. R1在(1)中是外部面, 在(2)中是内部面; R2在(1)中是内部面, 在(2)中是外部面. 其实, 在平面嵌入中可把任何面作为外部面. * 极大平面图 定义 若G是简单平面图, 并且在任意两个不相邻的顶点之 间加一条新边所得图为非平面图, 则称G为极大平面图. 例如, K5, K3,3若删去一条边是极大平面图. K1, K2, K3, K4都是极大平面图(它们已无不相邻顶点). 极大平面图必连通. 阶数大于等于3的极大平面图中不可能有割点和桥. 任何n(n?4)阶极大平面图G均有?(G)?3. 定理 n(n?3)阶简单平面图是极大平面图当且仅当它连通且 每个面的次数都为3. * 实例 例 是否是极大平面图? 不是 不是 是 * 极小非平面图 定义 若G是非平面图, 并且任意删除一条边所得图 都是平面图, 则称G为极小非平面图. 极小非平面图必为简单图 例如, K5, K3,3是极小非平面图 * 欧拉公式 定理 (欧拉公式) 设G为n阶m条边r个面的连通平面图, 则 n?m+r=2. 证 对边数m做归纳证明. m=0, G为平凡图, 结论为真. 设m=k(k?0)结论为真, m=k+1时分情况讨论如下: (1) 若G中有一个1度顶点v, 则G ?=G-v 连通, 有n-1个顶点, k条边和r个面. 由归纳假设, (n-1)-k+r=2, 即n-(k+1)+r=2, 得证m=k+1时结论成立. (2) 否则, G中必有圈. 删除一个圈上的一条边,记作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 个连通分支有 ni个顶点, mi 条边和 ri 个面. 对各连通分支用欧拉公式, ni ? mi + ri = 2, i = 1, 2, … , p 求和并注意 r = r1+…+rp –p+1, 即得 n ? m + r = p + 1 * 平面图的性质 定理 设G为n阶m条边的连通平面图, 每个面的次数不小于l (l ?3), 则 设G为有 p (p?2) 个连通分支的平面图, 且每个面的次数不 小于l (l ?3), 则