离散数学--65平面图ppt课件

1、6.4.4 平面图平面图 平面图与平面嵌入平面图与平面嵌入平面图的面及其次数平面图的面及其次数极大平面图极大平面图极小非平面图极小非平面图欧拉公式欧拉公式库拉图斯基定理库拉图斯基定理平面图的对偶图平面图的对偶图平面图与非平面图平面图与非平面图定义定义6.22 如果能将图如果能将图G除顶点外边不相交地画在平面上除顶点外边不相交地画在平面上, 则称则称G是平面图是平面图. 这个画出的无边相交的图称作这个画出的无边相交的图称作G的平面的平面嵌入嵌入. 没有平面嵌入的图称作非平面图没有平面嵌入的图称作非平面图.例如例如 下图中下图中(1)(4)是平面图是平面图, (2)是是(1)的平面嵌入，的平面嵌入

2、， (4)是是(3)的平面嵌入的平面嵌入. (5)是非平面图是非平面图.平面图的面与次数平面图的面与次数设设G是一个平面嵌入是一个平面嵌入G的面的面: 由由G的边将平面划分成的每一个区域的边将平面划分成的每一个区域无限面无限面(外部面外部面): 面积无限的面面积无限的面, 用用R0表示表示有限面有限面(内部面内部面): 面积有限的面面积有限的面, 用用R1, R2, Rk表示表示 面面Ri的边界的边界: 包围包围Ri的所有边构成的回路组的所有边构成的回路组面面Ri的次数的次数: Ri边界的长度，用边界的长度，用deg(Ri)表示表示 说明说明: 构成一个面的边界的回路组可能是初级回路构成一个面

3、的边界的回路组可能是初级回路, 简单回简单回路路, 也可能是复杂回路也可能是复杂回路, 甚至还可能是非连通的回路之并甚至还可能是非连通的回路之并.实例实例例例1 右图有右图有 个面个面4deg(R1)=deg(R2)=deg(R3)=deg(R0)=1328R1的边界的边界:R2的边界的边界:R3的边界的边界:R0的边界的边界:abcefgabcdde, fg实例实例例例2 右边右边2个图是同一个图是同一平面图的平面嵌入平面图的平面嵌入. R1在在(1)中是外部面中是外部面, 在在(2)中是内部面中是内部面; R2在在(1)中是内部面中是内部面, 在在(2)中是外部面中是外部面. (1)R1R

4、2R3(2)R1R2R3说明说明: (1) 一个平面图可以有多个不同形式的平面嵌入一个平面图可以有多个不同形式的平面嵌入, 它们都同构它们都同构.(2) 可以通过变换可以通过变换(测地投影法测地投影法)把平面图的任何一面作为把平面图的任何一面作为外部面外部面平面图的面与次数平面图的面与次数( (续续) )定理定理6.13 平面图各面的次数之和等于边数的平面图各面的次数之和等于边数的2倍倍证证 一条边或者是一条边或者是2个面的公共边界个面的公共边界, 或者在一个面的边界或者在一个面的边界中出现中出现2次次. 在计算各面的次数之和时在计算各面的次数之和时, 每条边恰好被计算每条边恰好被计算2次次.

5、极大平面图极大平面图定义定义6.24 若若G是简单平面图是简单平面图, 且在任意两个不相邻的顶点且在任意两个不相邻的顶点之间加一条新边所得图为非平面图之间加一条新边所得图为非平面图, 则称则称G为极大平面图为极大平面图例如例如 K1, K2, K3, K4都是极大平面图都是极大平面图(1)是是K5删去一条边删去一条边, 是极大平面图是极大平面图. (2)、(3)不是不是.(2)(3)(1)极大平面图的性质极大平面图的性质极大平面图是连通的极大平面图是连通的 设设G为为n(n3)阶简单图阶简单图, G为极大平面图的充分必要条为极大平面图的充分必要条 件是件是, G每个面的次数均为每个面的次数均为

6、3.例如例如极大平面图极大平面图外部面的次数为外部面的次数为4 非极大平面图非极大平面图极小非平面图极小非平面图定义定义6.25 若若G是非平面图是非平面图, 并且任意删除一条边所得图都并且任意删除一条边所得图都是平面图是平面图, 则称则称G为极小非平面图为极小非平面图例如例如 K5, K3,3都是极小非平面图都是极小非平面图下述下述4个图也都是极小非平面图个图也都是极小非平面图欧拉公式欧拉公式定理定理6.14 设设G为为n阶阶m条边条边r个面的连通平面图个面的连通平面图, 那么那么 nm+r=2 证证 对边数对边数m做归纳证明做归纳证明. m=0, G为平凡图为平凡图, 结论成立结论成立.设

7、设m=k(k0)时结论成立时结论成立, 对对m=k+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时结论成立时结论成立. 否则否则, 删除一个圈上的一条边删除一个圈上的一条边,记作记作G. G连通连通, 有有n个顶个顶点点,k条边和条边和r-1个面个面. 由归纳假设由归纳假设, n-k+(r-1)=2, 即即n-(k+1)+r=2. 得得证证m=k+

8、1时结论也成立时结论也成立. 证毕证毕.欧拉公式欧拉公式(续续)推论推论 设平面图设平面图G有有 p (p2) 个连通分支个连通分支, 那么那么 n m + r = p + 1其中其中n, m, r 分别是分别是G的阶数的阶数, 边数和面数边数和面数.证证 设第设第 i 个连通分支有个连通分支有 ni个顶点个顶点, mi 条边和条边和 ri 个面个面. 对对各各连通分支用欧拉公式连通分支用欧拉公式, ni mi + ri = 2, i = 1, 2, , p求和并注意求和并注意 r = r1+rp p+1, 即得即得 n m + r = p + 1欧拉公式欧拉公式(续续)定理定理6.15 设设

9、G为为n阶连通平面图阶连通平面图, 有有m条边条边, 且每个面的次且每个面的次数不小于数不小于l (l 3), 那么那么 证证 由各面次数之和等于边数的由各面次数之和等于边数的2倍及欧拉公式得倍及欧拉公式得 2m lr = l (2+m-n)可解得所需结论可解得所需结论.)2(2nllm实例实例例例4 设简单连通平面图有设简单连通平面图有n(n3)个顶点、个顶点、m条边条边, 那么那么 m3n-6例例3 证明证明 K5 和和 K3,3不是平面图不是平面图证证 不难证明不难证明3阶以上的简单连通平面图每个面的次数至阶以上的简单连通平面图每个面的次数至少为少为3, 由定理由定理6.15立即得到要证

10、的结论立即得到要证的结论.证证 K5 : n=5, m=10, l=3 K3,3 : n=6, m=9, l=4不满足定理不满足定理6.15的条件的条件同胚与收缩同胚与收缩消去消去2度顶点度顶点v 如图从如图从(1)到到(2)插入插入2度顶点度顶点v 如图从如图从(2)到到(1)G1与与G2同胚同胚: G1与与G2同构同构, 或或经过反复插入、或消去经过反复插入、或消去2度顶度顶点后同构点后同构收缩边收缩边e 如图从如图从(3)到到(4)(3)(4)库拉图斯基库拉图斯基(Kuratowski)(Kuratowski)定理定理定理定理6.16 一个图是平面图当且仅当它既不含与一个图是平面图当且仅

11、当它既不含与K5同胚的同胚的子图子图, 也不含与也不含与K3,3同胚的子图同胚的子图.定理定理6.17 一个图是平面图当且仅当它既无可收缩为一个图是平面图当且仅当它既无可收缩为K5的的子图子图, 也无可收缩为也无可收缩为K3,3的子图的子图. 实例实例与与K3,3同胚同胚也可收缩到也可收缩到K3,3例例5 证明下面证明下面2个图均为非平面图个图均为非平面图. 与与K5同胚同胚也可收缩到也可收缩到K5对偶图对偶图定义定义6.28 设平面图设平面图G有有n个顶点个顶点, m条边和条边和r个面个面, G的对偶的对偶图图G*=构造如下构造如下: 在在G的每一个面的每一个面Ri中任取一个点中任取一个点v

12、i*作为作为G*的顶点的顶点, V*= vi*| i=1,2,r . 对对G每一条边每一条边ek, 若若ek在在G的面的面Ri与与Rj的公共边界上的公共边界上, 则作则作边边ek*=(vi*,vj*), 且与且与ek相交相交; 若若ek只在面只在面Ri的边界上的边界上, 则作环则作环ek*=(vi*,vi*). E*= ek*| k=1,2, ,m .实例实例性质性质G*是平面图，而且是平面嵌入是平面图，而且是平面嵌入.G*是连通的是连通的.若若e为为G中的环中的环, 则则G*中中e*为桥为桥; 若若e为桥为桥, 则则G*中中e*为环为环.同构的平面图的对偶图不一定同构同构的平面图的对偶图不一定同构. 如如(1)和和(3)(1)(2)(3)对偶图对偶图(续续)定理定理6.18 设设G*是连通平面图是连通平面图G的对偶图的对偶图, n*, m*, r*和和n, m, r分别为分别为G*和和G的顶点数、边数和面数，那么的顶点数、