- 1、本文档共48页,可阅读全部内容。
- 2、原创力文档(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
11 可平面图的判断
可平面图的判断
程龚 (gcheng@)
本节课的主要内容
7.3 可平面图的判断
DMP算法
2
回顾
• 不可平面图
– K
5
– K
3,3
• 极小不可平面图(minimal nonplanar graph)
– 任何真子图都是可平面图
你能举一些例子吗?
• K 、K
5 3,3
• 可平面图的子图一定是可平面图
– K 和K 一定不是可平面图的子图
5 3,3
3
剖分
• 剖分(subdivision)
– 在一条边上加入一个新的顶点,将其分为两条边
4
/wiki/Subdivision_(graph_theory)#Subdivisions
Kuratowski子图
• Kuratowski子图
– K 或K 的剖分
5 3,3
5
/wikipedia/commons/thumb/7/73/GP92-Kuratowski.svg/500px-GP92-Kuratowski.svg.png
Kuratowski定理
• 可平面图的充要条件:没有Kuratowski子图。
证明:
⇒
剖分并不改变图的可平面性⇒K 或K 的剖分是不可平面图
5 3,3
⇒可平面图没有Kuratowski子图
剖分会不会改变图的可平面性?
6
Kuratowski定理(续)
• 可平面图的充要条件:没有Kuratowski子图。
证明:
⇐*
反证法:假设存在一个不包含Kuratowski子图的不可平面图
1. 边最少的不包含Kuratowski子图的不可平面图一定是3-连通的。
2. 不包含Kuratowski子图的3-连通图一定是可平面图。
7
Kuratowski定理(续)
• 1. 边最少的不包含Kuratowski子图的不可平面图G一定是3-连通的。
证明:
1. 从G 中删除边e不会引入Kuratowski子图⇒G-e是可平面图⇒G是极小不可平面图
2. (引理1)极小不可平面图是2-连通的⇒G是2-连通的
3. 反证法:假设G不是3-连通的⇒G有2-点割集S={x, y}
4. G-S 的一个连通分支中的所有顶点和{x, y}的并在G 中的导出子图称作一个S-lobe。
5. (引理2 )对于不可平面图G的2-点割集S={x, y},G有一个S-lobe+(x, y)是不可平面图,
记作H。
6.
您可能关注的文档
- (101年6月28日申办说明会简报档).ppt
- ( )1 - 桥头国中.doc
- (一)国宾饭店滑倒赔偿案.ppt
- (二)记录照片在摄影艺术上占据了主要地位.ppt
- (她)走出灾难阴影-灾后儿童心理复健之辅导训练 - 台中市临床心理师公会.ppt
- (三)中医—再生不良性贫血.ppt
- (员林高中).ppt
- (水中不可以有杂质,水盆需清洗干净) 2均匀撒上滑石粉.pdf
- (字音) - 湖南教育网.ppt
- (势) 吞天沃日声如雷霆交叉潮.ppt
- 【初中语文】第1课《春》课件++统编版语文七年级上册.pptx
- 第一单元第4课宋明理学-经典教学教辅文档.PPT
- 第一单元第6课中国古代的科学技术-经典教学教辅文档.PPT
- 第一单元第4课明清君主专制的加强-经典教学教辅文档.PPT
- 第一单元第4课时-经典教学教辅文档.pptx
- 第一单元第二课第一框 公民的义务 ( 27 张PPT)-经典教学教辅文档.ppt
- 第一单元第二章第一节生物与环境的关系-经典教学教辅文档.ppt
- 第一单元第4课明清之际活跃的儒家思想-经典教学教辅文档.PPT
- 第一单元第三课第二框哲学史上的伟大变革-经典教学教辅文档.ppt
- 第一单元第一课第二框关于世界观的学说-经典教学教辅文档.ppt
文档评论(0)