图论ppt课件平面图的判定与涉及平面性的不变量.ppt
《图论ppt课件平面图的判定与涉及平面性的不变量.ppt》由会员分享,可在线阅读,更多相关《图论ppt课件平面图的判定与涉及平面性的不变量.ppt(32页珍藏版)》请在三一办公上搜索。
1、1,图论及其应用,应用数学学院,2,本次课主要内容,(一)、平面图的判定,(二)、涉及平面性的不变量,平面图的判定与涉及平面性的不变量,3,这次课要解决的问题是:给出判定一个图是否是可平面图的充分必要条件。,(一)、平面图的判定,在本章第一次课中,我们已经明确:对于3阶以上的具有m条边的图G来说,如果G满足如下条件之一: (1)m3n-6; (2) K5是G的一个子图;(3) K3,3是G的一个子图,那么,G是非可平面图。,但上面的条件仅为G是非可平面图的充分条件。,最早给出图的平面性判定充要条件的是波兰数学家库拉托斯基(30年代给出)。后来,美国数学家惠特尼,加拿大数学家托特,我国数学家吴文
2、俊等都给出了不同的充要条件。,4,所以,我们称K5与K3,3为库拉托斯基图。,我们主要介绍波兰数学家库拉托斯基的结果。,库拉托斯基定理主要基于K5和K3,3是非可平面图这一事实而提出的平面性判定方法。,一个自然的猜测是:G是可平面图的充分必要条件是G不含子图K5和K3,3。,上面命题必要性显然成立!但充分性能成立吗?,十分遗憾!下面例子给出了回答:NO!,下面的图G是一个点数为5,边数为9的极大平面图。考虑 F=GK3,5,注:F由G的3个拷贝组成,分别是G1,G2,G3。三个拷贝中的边没有画出。图中虚线不是对应的Gi中边。,6,可以证明:F中不含K5和K3,3,且F是非可平面图。,尽管我们的
3、直觉猜测错了,但库拉托斯基还是基于K5与K3,3得到了图的平面性判据。,1、相关概念,定义1 在图G的边上插入一个2度顶点,使一条边分成两条边,称将图在2度顶点内扩充;去掉一个图的2度顶点,使关联它们的两条边合并成一条边,称将图G在2度顶点内收缩。,7,定义2 两个图G1与G2说是同胚的,如果 ,或者通过反复在2度顶点内扩充和收缩后能够变成一对同构的图。,上面的G1, G2, G3 是同胚的。,注:图的平面性在同胚意义下不变。,8,定理1 (库拉托斯基定理) 图G是可平面的,当且仅当它不含K5或K3,3同胚的子图。,例1 求证:下面两图均是非平面图。,证明:对于G1来说,按G1在2度顶点内收缩
4、后,可得到K5。所以,由库拉托斯基定理知G1是非可平面图。,9,对于G2来说,先取如下子图,对上面子图,按2度顶点收缩得与之同胚子图K3,3:,所以,G2是非可平面图。,10,例2 确定下图是否是可平面图。,分析:我们根据图的结构形式,怀疑该图是非可平面图。但我们必须找到证据!,当然我们可能考虑是否m3n-6。遗憾的是该图不满足这个不等式!,11,所以,我们要在该图中寻找一个与k5或K3,3同胚的子图!,由于该图的最大度为4的顶点才4个,所以,不存在与K5同胚的子图。因此,只有寻找与K3,3同胚的子图!,解:取G中红色边的一个导出子图:,也就是得到G的如下形式的一个子图:,12,上图显然和K3
5、,3同胚。由库拉托斯基定理知,G是非可平面的。,注: (1) 库拉托斯基定理可以等价叙述为:,库拉托斯基定理:图G是非可平面的,当且仅当它含有K5或K3,3同胚的子图。,13,(2) 库拉托斯基 (1896-1980) 波兰数学家。1913年开始在苏格兰格拉斯哥大学学习工程学,1915年回到波兰发沙大学转学数学,主攻拓扑学。1921年获博士学位。1930年在利沃夫大学作数学教授期间,发现并证明了图论中的库拉托斯基定理。1939年后到发沙大学做数学教授。他的一生主要研究拓扑学与集合论。,库拉托斯基定理:图G是非可平面的,当且仅当它含有K5或K3,3同胚的子图。,定义2 给定图G, 去掉G中的环,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 图论ppt课件 平面图的判定与涉及平面性的不变量 图论 ppt 课件 平面图 判定 涉及 平面性 不变量
链接地址:https://www.31ppt.com/p-1930051.html