




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、18.4 平面图平面图 平面图与平面嵌入平面图与平面嵌入平面图的面、有限面、无限面平面图的面、有限面、无限面面的次数面的次数极大平面图极大平面图极小非平面图极小非平面图欧拉公式欧拉公式平面图的对偶图平面图的对偶图 2平面图和平面嵌入平面图和平面嵌入 定义定义 如果能将图如果能将图g除顶点外边不相交地画在平面上除顶点外边不相交地画在平面上, 则称则称g是是平面图平面图. 这个画出的无边相交的图称作这个画出的无边相交的图称作g的的平面嵌入平面嵌入. 没有平面嵌入的图称作没有平面嵌入的图称作非平面图非平面图. 例如例如 下图中下图中(1)(4)是平面图是平面图, (2)是是(1)的平面嵌入,的平面嵌
2、入,(4)是是(3)的平面嵌入的平面嵌入. (5)是非平面图是非平面图.3平面图和平面嵌入平面图和平面嵌入( (续续) )今后称一个图是平面图今后称一个图是平面图, 可以是指定义中的平面图可以是指定义中的平面图, 又可以又可以是指平面嵌入是指平面嵌入, 视当时的情况而定视当时的情况而定. 当讨论的问题与图的画当讨论的问题与图的画法有关时法有关时, 是指平面嵌入是指平面嵌入. k5和和k3,3是非平面图是非平面图设设g g, 若若g为平面图为平面图, 则则g 也是也是 平面图平面图; 若若g 为非平面图为非平面图, 则则g也也 是非平面图是非平面图. kn(n 5), k3,n(n 3)都是非平
3、面图都是非平面图. 平行边与环不影响图的平面性平行边与环不影响图的平面性. k5k3,34平面图的面与次数平面图的面与次数设设g是一个平面嵌入是一个平面嵌入g的面的面: 由由g的边将平面划分成的每一个区域的边将平面划分成的每一个区域无限面无限面(外部面外部面): 面积无限的面面积无限的面, 用用r0表示表示有限面有限面(内部面内部面): 面积有限的面面积有限的面, 用用r1, r2, rk表示表示 面面ri的边界的边界: 包围包围ri的所有边构成的回路组的所有边构成的回路组面面ri的次数的次数: ri边界的长度,用边界的长度,用deg(ri)表示表示 说明说明: 构成一个面的边界的回路组可能是
4、初级回路构成一个面的边界的回路组可能是初级回路, 简单回简单回路路, 也可能是复杂回路也可能是复杂回路, 还可能是非连通的回路之并还可能是非连通的回路之并. 定理定理 平面图各面的次数之和等于边数的平面图各面的次数之和等于边数的2倍倍.5平面图的面与次数平面图的面与次数( (续续) )例例1 右图有右图有4个面个面, deg(r1)=1, deg(r2)=3, deg(r3)=2, deg(r0)=8. 请写各面的边界请写各面的边界.例例2 左边左边2个图是同一个平面个图是同一个平面图的平面嵌入图的平面嵌入. r1在在(1)中是中是外部面外部面, 在在(2)中是内部面中是内部面; r2在在(1
5、)中是内部面中是内部面, 在在(2)中是中是外部面外部面. 其实其实, 在平面嵌入中在平面嵌入中可把任何面作为外部面可把任何面作为外部面.6极大平面图极大平面图 定义定义 若若g是简单平面图是简单平面图, 并且在任意两个不相邻的顶点之并且在任意两个不相邻的顶点之间加一条新边所得图为非平面图间加一条新边所得图为非平面图, 则称则称g为为极大平面图极大平面图.性质性质若简单平面图中已无不相邻顶点,则是极大平面图若简单平面图中已无不相邻顶点,则是极大平面图. 如如 k1, k2, k3, k4都是极大平面图都是极大平面图. 极大平面图必连通极大平面图必连通. 阶数大于等于阶数大于等于3的极大平面图中
6、不可能有割点和桥的极大平面图中不可能有割点和桥. 设设g为为n(n 3)阶极大平面图阶极大平面图, 则则g每个面的次数均为每个面的次数均为3. 任何任何n(n 4)阶极大平面图阶极大平面图g均有均有(g) 3. 7实例实例3个图都是平面图个图都是平面图, 但只有右边的图为极大平面图但只有右边的图为极大平面图. 8极小非平面图极小非平面图 定义定义 若若g是非平面图是非平面图, 并且任意删除一条边所得图并且任意删除一条边所得图都是平面图都是平面图, 则称则称g为为极小非平面图极小非平面图.说明说明: k5, k3,3都是极小非平面图都是极小非平面图 极小非平面图必为简单图极小非平面图必为简单图下
7、面下面4个图都是极小非平面图个图都是极小非平面图 9欧拉公式欧拉公式 定理定理8.11 (欧拉公式欧拉公式) 设设g为为n阶阶m条边条边r个面的连通平面图,个面的连通平面图,则则 n m+r=2. 证证 对边数对边数m做归纳证明做归纳证明. m=0, g为平凡图为平凡图, 结论为真结论为真.设设m=k(k 0)结论为真结论为真, m=k+1时分情况讨论如下时分情况讨论如下: (1) g中无圈中无圈, 则则g必有一个度数为必有一个度数为1的顶点的顶点v, 删除删除v及它关及它关联的边联的边, 记作记作g . g 连通连通, 有有n-1个顶点个顶点, k条边和条边和r个面个面. 由由归归纳假设纳假
8、设, (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时结论也成立时结论也成立. 证毕证毕. 10欧拉公式欧拉公式( (续续) )欧拉公式的推广欧拉公式的推广 设设g是有是有 p (p 2) 个连通分支的平面图个连通分支的平面图, 则则 n m + r = p + 1证证 设第设第 i 个连通分支有个连通分支
9、有 ni个顶点个顶点, mi 条边和条边和 ri 个面个面. 对各连通分支用欧拉公式对各连通分支用欧拉公式, ni mi + ri = 2, i = 1, 2, , p求和并注意求和并注意 r = r1+rp+ p 1, 即得即得 n m + r = p + 111与欧拉公式有关的定理与欧拉公式有关的定理 )2(2 nllmk5k3,3定理定理 设设g为为n阶连通平面图阶连通平面图, 有有m条边条边, 且每个面的次数不且每个面的次数不小于小于l (l 3), 则则 证证 由定理由定理 (各面次数之和等于边数的各面次数之和等于边数的2倍倍)及欧拉公式得及欧拉公式得 2m lr = l (2+m-
10、n)可解得所需结论可解得所需结论. 推论推论 k5 和和 k3,3不是平面图不是平面图.证证 用反证法用反证法, 假设它们是平面图假设它们是平面图,则则 k5 : n=5, m=10, l=3 k3,3 : n=6, m=9, l=4与定理矛盾与定理矛盾.12与欧拉公式有关的定理与欧拉公式有关的定理( (续续) )1(2 pnllm定理定理: 设设g为有为有 p (p 2) 个连通分支的平面图个连通分支的平面图, 且每个面的次数不小于且每个面的次数不小于l (l 3), 则则定理定理 设设g为简单平面图,则为简单平面图,则 (g) 5.13同胚与收缩同胚与收缩 消去消去2度顶点度顶点v 如上图
11、从如上图从(1)到到(2)插入插入2度顶点度顶点v 如上图从如上图从(2)到到(1)g1与与g2同胚同胚: g1与与g2同构同构, 或或经过反复插入、或消去经过反复插入、或消去2度顶度顶点后同构点后同构收缩边收缩边e 如下图从如下图从(1)到到(2)14库拉图斯基定理库拉图斯基定理定理定理 g是平面图是平面图g中不含与中不含与k5同胚的子图同胚的子图, 也不也不含与含与k3,3同胚的子图同胚的子图.定理定理 g是平面图是平面图g中无可收缩为中无可收缩为k5的子图的子图, 也无也无可收缩为可收缩为k3,3的子图的子图. 15非平面图证明非平面图证明例例 证明下述证明下述2个图均为非平面图个图均为
12、非平面图. 证证图中红色部分分别与图中红色部分分别与k3,3和和 k5 同胚同胚16平面图的对偶图平面图的对偶图 定义定义 设平面图设平面图g, 有有n个顶点个顶点, m条边和条边和r个面个面, 构造构造g的的对偶图对偶图g*=如下:如下:在在g的每一个面的每一个面ri中任取一个点中任取一个点vi*作为作为g*的顶点的顶点, v*= vi*| i=1,2,r .对对g每一条边每一条边ek, 若若ek在在g的面的面ri与与rj的公共边界上的公共边界上, 则作边则作边ek*=(vi*,vj*), 且与且与ek相交相交; 若若ek为为g中的桥且在中的桥且在面面ri的边界上的边界上, 则作环则作环ek
13、*=(vi*,vi*). e*= ek*| k=1,2, ,m . 17平面图的对偶图(续)平面图的对偶图(续)例例 黑色实线为原平面图黑色实线为原平面图, 红色虚线为其对偶图红色虚线为其对偶图 18平面图的对偶图平面图的对偶图( (续续) )性质:性质:g*是平面图,而且是平面嵌入是平面图,而且是平面嵌入.g*是连通图是连通图若边若边e为为g中的环,则中的环,则g*与与e对应的边对应的边e*为桥为桥; 若若e为桥,则为桥,则g*中与中与e对应的边对应的边e*为环为环.在多数情况下,在多数情况下,g*含有平行边含有平行边.同构的平面图的对偶图不一定同构同构的平面图的对偶图不一定同构. 上面两个平面图是同构的上面两个平面图是同构的, 但它们的对偶图不同构但它们的对偶图不同构. 19平面图与对偶图的阶数、边数与面数之间的关系平面图与对偶图的阶数、
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 海门初中二模数学试卷
- 广西四月联考数学试卷
- 国际学校英文数学试卷
- 虹桥初二期末数学试卷
- 红桥期末高二数学试卷
- 衡水二中初三数学试卷
- 杭州小考数学试卷
- 吉水思源小升初数学试卷
- 贵阳初一加初二数学试卷
- 合肥九中开学考数学试卷
- 仪表工基础知识课件
- 2025年医院管理知识考试试题及答案
- 福建省厦门市2025年高一化学第二学期期末调研模拟试题含解析
- 危险废物突发事故应急演练方案
- DB11-T 2408.1-2025城市管理大数据平台 第1部分:架构及接口规范
- 2023年08月江苏省高邮市招考70名村级工作人员笔试上岸试题历年
- 2025年山东省济南市槐荫区八年级下期末语文试题(含答案)
- DB41∕T 610-2024 高速公路收费人员操作规范
- 北京安全生产治本攻坚三年行动方案
- 建设单位全员安全生产责任清单
- 项目计划管理培训
评论
0/150
提交评论