版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、1第十七章第十七章 平面图平面图本章的主要内容本章的主要内容l 平面图的基本概念平面图的基本概念l 欧拉公式欧拉公式l 平面图的判断平面图的判断l 平面图的对偶图平面图的对偶图2在图中,在图中,(2)是是(1) 的平面嵌入,的平面嵌入,(4)是是(3)的平面嵌入的平面嵌入.17.1 平面图平面图的基本概念的基本概念定义定义17.1 (1) G可嵌入曲面可嵌入曲面S若能将若能将G除顶点外无边相交地画在除顶点外无边相交地画在S上上(2) G是是可平面图可平面图或或平面图平面图G可嵌入平面可嵌入平面 (3) 平面嵌入平面嵌入画出的无边相交的平面图画出的无边相交的平面图(4) 非平面图非平面图无平面嵌
2、入的无向图无平面嵌入的无向图 (1) (2) (3) (4)3几点说明及一些简单结论几点说明及一些简单结论一般所谈平面图不一定是指平面嵌入,上图中一般所谈平面图不一定是指平面嵌入,上图中4个图都是平个图都是平面图,但讨论某些性质时,一定是指平面嵌入面图,但讨论某些性质时,一定是指平面嵌入. 结论:结论: (1) K5, K3,3都不是平面图(待证)都不是平面图(待证)(2) 设设GG,若,若G为平面图,则为平面图,则G 也是平面图(定理也是平面图(定理17.1)(3) 设设GG,若,若G 为非平面图,则为非平面图,则G也是非平面图(定理也是非平面图(定理17.2),由此可知,),由此可知,Kn
3、(n 6),K3,n(n 4) 都是非平面图都是非平面图. (4) 平行边与环不影响平面性平行边与环不影响平面性. 4平面图平面图(平面嵌入平面嵌入)的面与次数的面与次数定义定义17.2 (1) G的的面面由由G的平面嵌入的边将平面化分成的区域的平面嵌入的边将平面化分成的区域(2) 无限面无限面或或外部面外部面(可用(可用R0表示)表示)面积无限的面面积无限的面(3) 有限面有限面或或内部面内部面(可用(可用R1, R2, , Rk等表示)等表示)面积面积 有限的面有限的面 (4) 面面 Ri 的边界的边界包围包围Ri的回路组的回路组(5) 面面 Ri 的次数的次数Ri边界的长度,用边界的长度
4、,用deg(Ri)表示表示 5定理定理17.4 平面图各面次数之和等于边数的两倍平面图各面次数之和等于边数的两倍. 几点说明几点说明l 若平面图若平面图G有有k个面,可笼统地用个面,可笼统地用R1, R2, , Rk表示,不需表示,不需要指出外部面要指出外部面.l 定义定义17.2(4) 中回路组是指:边界可能是初级回路中回路组是指:边界可能是初级回路(圈圈),可,可能是简单回路,也可能是复杂回路能是简单回路,也可能是复杂回路. 特别地,还可能是非特别地,还可能是非连通的回路之并连通的回路之并. 平面图有平面图有4个面,个面,deg(R1)=1, deg(R2)=3, deg(R3)=2, d
5、eg(R0)=8. 请写各面的边界请写各面的边界. 6极大平面图极大平面图定义定义17.3 若在简单平面图若在简单平面图G中的任意两个不相邻的顶点之间中的任意两个不相邻的顶点之间加一条新边所得图为非平面图,则称加一条新边所得图为非平面图,则称G为为极大平面图极大平面图.注意:若简单平面图注意:若简单平面图G中已无不相邻顶点,中已无不相邻顶点,G显然是极大平显然是极大平面图,如面图,如K1(平凡图平凡图), K2, K3, K4都是极大平面图都是极大平面图.极大平面图的主要性质极大平面图的主要性质定理定理17.5 极大平面图是连通的极大平面图是连通的. 证明线索:否则,加新边不破坏平面性证明线索
6、:否则,加新边不破坏平面性定理定理17.6 n(n 3)阶极大平面图中不可能有割点和桥)阶极大平面图中不可能有割点和桥. 证明线索:由定理证明线索:由定理17.5及及n 3可知,可知,G中若有桥,则一定有中若有桥,则一定有割点,因而只需证无割点即可割点,因而只需证无割点即可. 方法还是反证法方法还是反证法.7证明线索:证明线索:(1) 由于由于n 3, 又又G必为简单必为简单平面图可知,平面图可知,G每个面的每个面的次数均次数均 3.(2) 因为因为G为平面图,又为极为平面图,又为极大平面图大平面图. 可证可证G不可能不可能存在次数存在次数3的面的面. 就给出的图讨论即可就给出的图讨论即可.
7、极大平面图的性质极大平面图的性质定理定理17.7 设设G为为n(n 3)阶极大平面图,则)阶极大平面图,则G的每个面的的每个面的次数均为次数均为3. 8定理定理17.7中的条件也是极大平面图的充分条件中的条件也是极大平面图的充分条件. 定理定理17.7 设设G为为n (n 3) 阶平面图,且每个面的次数均为阶平面图,且每个面的次数均为3,则则G为极大平面图为极大平面图.定理的应用定理的应用上图中,只有上图中,只有(3)为极大平面图为极大平面图 (1) (2) (3) 9极小非平面图极小非平面图定义定义17.4 若在非平面图若在非平面图G中任意删除一条边,所得图中任意删除一条边,所得图G 为平为
8、平面图,则称面图,则称G为为极小非平面图极小非平面图.由定义不难看出:由定义不难看出:(1) K5, K3,3都是极小非平面图都是极小非平面图(2) 极小非平面图必为简单图极小非平面图必为简单图图中所示各图都是极小非平面图图中所示各图都是极小非平面图.10定理定理17.9 (欧拉公式的推广)设(欧拉公式的推广)设G是具有是具有k(k 2)个连通)个连通分支的平面图,则分支的平面图,则n m+r=k+1证明中对各连通分支用欧拉公式,并注意证明中对各连通分支用欧拉公式,并注意即可即可. kiikrr1)1(17.2 欧拉公式欧拉公式定理定理17.8 设设G为为n阶阶m条边条边r个面的连通平面图,则
9、个面的连通平面图,则n m+r=2(此公式称为(此公式称为欧拉公式欧拉公式)证证 对边数对边数m做归纳法做归纳法m=0,G为平凡图,结论为真为平凡图,结论为真.设设m=k(k 1)结论为真,)结论为真,m=k+1时分情况讨论时分情况讨论.(1) G中无圈,则中无圈,则G为树,删除一片树叶,用归纳假设为树,删除一片树叶,用归纳假设.(2) 否则,在某一个圈上删除一条边,进行讨论否则,在某一个圈上删除一条边,进行讨论.11)2(2 nllm)2()deg(21nmlrlRmrii )2(2 nllm)1(2 knllm解得解得 定理定理17.11 在具有在具有k(k 2)个连通分支的平面图中,)个
10、连通分支的平面图中,与欧拉公式有关的定理与欧拉公式有关的定理定理定理17.10 设设G为连通的平面图,且为连通的平面图,且deg(Ri) l, l 3,则,则 证证 由定理由定理17.4及及欧拉公式得欧拉公式得推论推论 K5, K3,3不是平面图不是平面图.12定理定理17.12 设设G为为n(n 3)阶)阶m条边的简单平面图,则条边的简单平面图,则m 3n 6. 证证 设设G有有k(k 1)个连通分支,若)个连通分支,若G为树或森林,当为树或森林,当n 3时,时,m 3n 6为真为真. 否则否则G中含圈,每个面至少由中含圈,每个面至少由l(l 3)条边围成)条边围成,又,又2212 lll定
11、理定理17.13 设设G为为n(n 3)阶)阶m条边的极大平面图,则条边的极大平面图,则m=3n 6.证证 由定理由定理17.4, 欧拉公式及定理欧拉公式及定理17.7所证所证. 定理定理17.14 设设G 为简单平面图,则为简单平面图,则 (G) 5. 证证 阶数阶数 n 6,结论为真,结论为真. 当当n 7 时,用反证法时,用反证法. 否则会推出否则会推出2m 6n m 3n,这与定理,这与定理17.12矛盾矛盾. 与欧拉公式有关的定理与欧拉公式有关的定理在在l=3达到最大值,由定理达到最大值,由定理17.11可知可知m 3n 6.1317.3 平面图的判断平面图的判断1. 插入插入2度顶
12、点和消去度顶点和消去2度顶点度顶点定义定义17.5(1) 消去消去2度顶点度顶点v,见下图中,由,见下图中,由(1) 到到(2) (2) 插入插入2度顶点度顶点v,见下图中,从,见下图中,从(2) 到到(1) . (1) (2) 142. 收缩边收缩边e,见下图所示,见下图所示.3. 图之间的同胚图之间的同胚定义定义17.6 若若G1 G2,或经过反复插入或消去,或经过反复插入或消去2度顶点后所度顶点后所得得G 1 G 2,则称,则称G1与与G2同胚同胚. 图的同胚图的同胚右边两个图同胚右边两个图同胚15平面图判定定理平面图判定定理定理定理17.15 G是平面图是平面图 G中不含与中不含与K5
13、或或K3,3同胚的子图同胚的子图.定理定理17.16 G是平面图是平面图 G中无可收缩为中无可收缩为K5或或K3,3的子图的子图例例1 证明所示图证明所示图(1)与与(2)均为非平面图均为非平面图. (1) (2)右图右图(1),(2)分别为分别为原图原图(1), (2)的子图的子图与与K3,3, K5同胚同胚. 子图子图 (1) (2) 1617.4 平面图的对偶图平面图的对偶图定义定义17.7 设设G是某平面图的某个平面嵌入,构造是某平面图的某个平面嵌入,构造G的对偶图的对偶图G*如下:如下:(1) 在在G的面的面Ri中放置中放置G*的顶点的顶点v*i. (2) 设设e为为G的任意一条边的
14、任意一条边. 若若e在在G的面的面 Ri与与 Rj 的公共边界上,做的公共边界上,做G*的边的边e*与与e相相 交,且交,且e*关联关联G*的位于的位于Ri与与Rj中的顶点中的顶点v*i与与v*j,即,即 e*=(v*i,v*j), e*不与其它任何边相交不与其它任何边相交. 若若e为为G中的桥且在面中的桥且在面Ri的边界上,则的边界上,则e*是以是以Ri中中G*的顶的顶 点点v*i为端点的环,即为端点的环,即e*=(v*i,v*i). 17下面两图中,实线边图为平面图,虚线边图为其对偶图下面两图中,实线边图为平面图,虚线边图为其对偶图. 实例实例18G 的对偶图的对偶图G*有以下性质:有以下
15、性质:(1) G*是平面图,而且是平面嵌入是平面图,而且是平面嵌入.(2) G*是连通图是连通图(3) 若边若边e为为G中的环,则中的环,则G*与与e对应的边对应的边e*为桥,若为桥,若e为桥,为桥,则则G*中与中与e对应的边对应的边e*为环为环.(4) 在多数情况下,在多数情况下,G*为多重图(含平行边的图)为多重图(含平行边的图).(5) 同构的平面图(平面嵌入)的对偶图不一定是同构的同构的平面图(平面嵌入)的对偶图不一定是同构的. 如上面的例子如上面的例子. 对偶图的性质对偶图的性质19平面图与对偶图的平面图与对偶图的阶数、边数与面数之间的关系阶数、边数与面数之间的关系定理定理17.17
16、 设设G*是连通平面图是连通平面图G的对偶图,的对偶图,n*, m*, r*和和n, m, r分别为分别为G*和和G的顶点数、边数和面数,则的顶点数、边数和面数,则(1) n*= r(2) m*=m(3) r*=n(4) 设设G*的顶点的顶点v*i位于位于G的面的面Ri中,则中,则dG*(v*i)=deg(Ri)证明线索证明线索(1)、(2)平凡平凡.(3) 应用欧拉公式应用欧拉公式.(4) 的证明中注意,桥只能在某个面的边界中,非桥边在两的证明中注意,桥只能在某个面的边界中,非桥边在两个面的边界上个面的边界上. 20平面图与对偶图的平面图与对偶图的阶数、边数与面数之间的关系阶数、边数与面数之
17、间的关系定理定理17.18 设设G*是具有是具有k(k 2)个连通分支的平面图)个连通分支的平面图G的对的对偶图,则偶图,则(1) n*= r(2) m*=m(3) r*=n k+1(4) 设设G*的顶点的顶点v*i位于位于G的面的面Ri中,则中,则dG*(v*i)=deg(Ri)其中其中n*, m*, r*, n, m, r同定理同定理17.17. 证明证明(3) 时应同时应用欧拉公式及欧拉公式的推广时应同时应用欧拉公式及欧拉公式的推广. 21自对偶图自对偶图定义定义17.8 设设G*是平面图是平面图G的对偶图,若的对偶图,若G* G,则称,则称G为为自自对偶图对偶图. 轮图轮图定义如下:定
18、义如下:在在n 1(n 4)边形)边形Cn 1内放置内放置1个顶点,使这个顶点与个顶点,使这个顶点与Cn 1上的所有的顶点均相邻上的所有的顶点均相邻. 所得所得n 阶简单图称为阶简单图称为n阶轮图阶轮图. n为奇为奇数的轮图称为数的轮图称为奇阶轮图奇阶轮图,n为偶数的轮图称为为偶数的轮图称为偶阶轮图偶阶轮图,常,常将将 n 阶轮图记为阶轮图记为Wn. 轮图都是自对偶图轮图都是自对偶图. 图中给出了图中给出了W6和和W7. 请画出它们的对偶图,请画出它们的对偶图,从而说明它们都是自对偶图从而说明它们都是自对偶图. 22第十七章第十七章 习题课习题课主要内容主要内容l 平面图的基本概念平面图的基本
19、概念l 欧拉公式欧拉公式l 平面图的判断平面图的判断l 平面图的对偶图平面图的对偶图基本要求基本要求l 深刻理解本部分的基本概念:平面图、平面嵌入、面、深刻理解本部分的基本概念:平面图、平面嵌入、面、次数、极大平面图、极小非平面图、对偶图次数、极大平面图、极小非平面图、对偶图l 牢记极大平面图的主要性质和判别方法牢记极大平面图的主要性质和判别方法l 熟记欧拉公式及推广形式,并能用欧拉公式及推广形式熟记欧拉公式及推广形式,并能用欧拉公式及推广形式证明有关定理与命题证明有关定理与命题l 会用库拉图斯基定理证明某些图不是平面图会用库拉图斯基定理证明某些图不是平面图 l 记住平面图与它的对偶图阶数、边
20、数、面数之间的关系记住平面图与它的对偶图阶数、边数、面数之间的关系23练习练习1解解 设设G的阶数、边数、面数分别为的阶数、边数、面数分别为n, m, r. (1) 否则,由欧拉公式得否则,由欧拉公式得 2m 5r = 5 (2+m n) 由于由于 (G) 3及握手定理又有及握手定理又有 2m 3n 由由与与得得 m 30 又有又有 r=2+m n 12 由由及及又可得又可得 m30 ,是矛盾的是矛盾的. (2) 正十二面体是一个反例正十二面体是一个反例 1. 设设G是连通的简单的平面图,面数是连通的简单的平面图,面数r12, (G) 3. (1) 证明证明G中存在次数中存在次数 4的面的面(2) 举例说明当举例说明当r=12时,时,(1) 中结论不真中结论不真.242. 设设G是阶数是阶数n 11的无向平面图,证明的无向平面图,证明G和和 不可能全是不可能全是平面图平面图. G证证 只需证明只需证明G和和 中至少有一个是非平面图中至少有一个是非平面图. 采用反证法采用反证法. 否则否则 与与G 都是平面图,下面来推出矛盾都是平面图,下面来推出矛盾.G与与 的边数的边数m, m 应满足应满足 ( Kn的边数的边数) 由鸽巢原理知由鸽巢原理知m或或m ,不妨设,不妨设m, GGG2)1( nnmm4) 1( nnm又由定理又由定理17.12 知知 m 3n 6 由由与
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 专属2024委托项目评估协议书稿版
- 二零二五年度高铁站停车场租赁管理协议3篇
- 2024版跨境商品居间合作协议版B版
- 当代展览建筑设计与传统文化元素融合探索
- 心理调适在学科教育中的重要性
- 2025年度航空航天产品设计与制造承包合同3篇
- 山东工商学院《电力电子装置与系统》2023-2024学年第一学期期末试卷
- 宁波幼儿师范高等专科学校《人权法》2023-2024学年第一学期期末试卷
- 专业技术服务合作协议范本一
- 绵阳城市学院《发光器件与显示技术》2023-2024学年第一学期期末试卷
- 2025至2031年中国台式燃气灶行业投资前景及策略咨询研究报告
- (一模)株洲市2025届高三教学质量统一检测 英语试卷
- 2025年中国电科集团春季招聘高频重点提升(共500题)附带答案详解
- 2025年度建筑施工现场安全管理合同2篇
- 社区意识形态工作责任制实施细则模版(2篇)
- 矿业公司规章制度汇编
- 店铺(初级)营销师认证考试题库附有答案
- 福建省厦门市2023-2024学年高二上学期期末考试语文试题(解析版)
- 防火墙施工组织设计
- 中国博物馆协会博物馆陈列展览设计施工单位资质管理办法
- 人员招聘需求申请表(通用)
评论
0/150
提交评论