已阅读5页,还剩17页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1,8.7 可平面图 Planar Graphs,2,8.7 可平面图 Planar Graphs,例:,有六个结点的图如上, 试问:能否转变成与其等价的,但没有任何相交线的平面上的图? 结论:不能,3,8.7 可平面图 Planar Graphs,DEFINITION A graph is called planar(可平面的) if it can be drawn in the plane without any edges crossing. Such a drawing is called a planar representation(平面表示) of the graph,4,例:,8.7 可平面图 Planar Graphs,5,例:,8.7 可平面图 Planar Graphs,6,8.7 可平面图 Planar Graphs,一个图的可平面表示把平面分割成一些面,包括一个无界的面。包围每个面的边界的长度称为面的次数,记为Deg(R)。,7,8.7 可平面图 Planar Graphs,EULERS FORMULA Let G be a connected planar simple graph with e edges and v vertices. Let r be the number of regions in a planar representation of G. Then r=e-v+2.,8,证明:用数学归纳法 归纳基础: 面数r=1,r=e-v+2成立。 面数r=2,G为一多边形,且e=v=3(e=v=4), 得e-v+2=3-3+2=r成立, 或e-v+2=4-4+2=r成立;,8.7 可平面图 Planar Graphs,9,归纳步骤: 设图G的面为r时,r=e-v+2成立。 证明面数为r=r+1时,等式也成立。 (a)先构成图G,其中点数为v,边数为e,面数为r; (b)在G中,加入一条长度为L的简单通路(L1),且与G共有二个结点,从而使G变为G;,8.7 可平面图 Planar Graphs,10,(c) e-v+2 =(e+L)-(v+(L-1)+2 =e+L-v-L+1+2 =e-v+2+1 =r+1 =r 定理成立,8.7 可平面图 Planar Graphs,L条边 (L-1)个点,G,11,8.7 可平面图 Planar Graphs,COROLLARY If G is a connected planar simple graph with e edges and v vertices, where v3, then e3v-6。,12,8.7 可平面图 Planar Graphs,证明: G为简单连通平面图 每一面至少用三条或更多条边构成, =所有面的边的总数。 因此边的总数 3r( 包含重复计算的边),13,8.7 可平面图 Planar Graphs,一条边是在至多二个面的边界中, 各面的实际总边数一定有3r( 2e) 即 成立,14,8.7 可平面图 Planar Graphs,由欧拉定理:,15,8.7 可平面图 Planar Graphs,例:证明K5图不是平面图 K5图中,v=5,e=10, 3*5-6=910 K5图不为平面图 思考:证明K3,3不是平面图,16,8.7 可平面图 Planar Graphs,COROLLARY If G is a connected planar simple graph, then G has a vertex of degree not exceeding five. COROLLARY If a connected planar simple graph has e edges and v vertices with v3 and no circuits of length three, then e2v-4.,17,8.7 可平面图 Planar Graphs,Elementary subdivision(初等细分) Removing an edge u, v and adding a new vertex w together with edges u, w and w, v The graphs G1 and G2 are called homeomorphic(同胚) if they can be obtained from the same graph by a sequence of elementary subdivisions.,18,8.7 可平面图 Planar Graphs,例:同胚图,19,8.7 可平面图 Planar Graphs,THEOREM A graph is nonplanar if and only if it contains a subgraph homeomorphic to K3,3 or K5.,20,8.7 可平面图 Planar Graphs,Example: Determin
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 安全技术交底 (新空白) - 副本
- 2024年内蒙古锡林郭勒盟农管局民族中学中考语文复习练习题
- 办公室改造装修项目 投标方案(技术方案)
- 急性上呼吸道感染:预防、识别与治疗
- 新学期国旗讲话稿7篇
- 2022年浙江杭州城站广场物业管理有限公司招聘考试试题及答案
- 2022年内江市妇幼保健院考核招聘考试试题及答案
- 2022年嘉兴市秀水高级中学教师招聘考试试题及答案
- 2022年北京市体育设施管理中心招聘应届毕业生考试试题及答案
- 幼儿园中秋活动总结与反思7篇
- 北京高中化学会考知识点( 特经典有效)
- 公司向个人借款合同范本简单版
- 中学师德师风突发事件联动处置预案
- DBJ52∕T 110-2022 贵州省城镇燃气安全检查标准
- 农产品项目策划书(共7篇)
- 商品学课件(完整版)
- 生物医药实验室安全知识培训试题与答案
- 中国标准文献分类法(中标分类CCS)
- 关键岗位轮岗情况表(预算、收支、资产管理采购业务)
- 趣味数学——推理小故事PPT课件(PPT 14页)
- 2017-2021年北京高考英语真题分类汇编之语法填空
评论
0/150
提交评论