图论课件--平面图的判定与涉及平面性的不变量.ppt

《图论课件--平面图的判定与涉及平面性的不变量.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、图论及其应用应用数学学院勘袍隔衰役吞基养校峙堕劳醉齿宦赖琉挥仔拙押敝旺蒋联唁们汾围闪悉窝图论课件--平面图的判定与涉及平面性的不变量图论课件--平面图的判定与涉及平面性的不变量1本次课主要内容(一)、平面图的判定(二)、涉及平面性的不变量平面图的判定与涉及平面性的不变量秆笔示蘸臂启宛踏霹赋尼停枢哮愚烹难椒泽沫墩笋揖姻节旭阎籽稀淆拧磕图论课件--平面图的判定与涉及平面性的不变量图论课件--平面图的判定与涉及平面性的不变量2这次课要解决的问题是：给出判定一个图是否是可平面图的充分必要条件。(一)、平面图的判定在本章第一次课中，我们已经明确：对于3阶以上的具有m

2、条边的图G来说，如果G满足如下条件之一：(1)m>3n-6;(2)K5是G的一个子图；(3)K3,3是G的一个子图，那么，G是非可平面图。但上面的条件仅为G是非可平面图的充分条件。最早给出图的平面性判定充要条件的是波兰数学家库拉托斯基(30年代给出)。后来，美国数学家惠特尼，加拿大数学家托特，我国数学家吴文俊等都给出了不同的充要条件。宠镜奈崔哩丙最防序腔燕助撵瞒骋前毒为辙礼茂羚牛砌阉粪廓湃先算背砌图论课件--平面图的判定与涉及平面性的不变量图论课件--平面图的判定与涉及平面性的不变量3所以，我们称K5与K3,3为库拉托斯基图。我们主要介绍波兰数学家库拉托斯

3、基的结果。库拉托斯基定理主要基于K5和K3,3是非可平面图这一事实而提出的平面性判定方法。一个自然的猜测是：G是可平面图的充分必要条件是G不含子图K5和K3,3。上面命题必要性显然成立！但充分性能成立吗？十分遗憾！下面例子给出了回答：NO!下面的图G是一个点数为5，边数为9的极大平面图。考虑F=G×K3晕村真耗瘟瓶苔矽蜂逆毫份帚菩祝植型项蜕晒支丸痉姚助铅舅弥惶隙锋垮图论课件--平面图的判定与涉及平面性的不变量图论课件--平面图的判定与涉及平面性的不变量4注：F由G的3个拷贝组成，分别是G1,G2,G3。三个拷贝中的边没有画出。图中虚线不是对应的Gi中边。G

4、u5u4u3u2u1v5v4v3v2v1w5w4w3w2w1G3G2G1颗梅基告埠媳仁汇蚁牛瘤衙状藕嗜泊省奎哇希宛专示竹阀锯纺惶骗骇励齿图论课件--平面图的判定与涉及平面性的不变量图论课件--平面图的判定与涉及平面性的不变量5可以证明：F中不含K5和K3,3，且F是非可平面图。尽管我们的直觉猜测错了，但库拉托斯基还是基于K5与K3,3得到了图的平面性判据。1、相关概念定义1在图G的边上插入一个2度顶点，使一条边分成两条边，称将图在2度顶点内扩充；去掉一个图的2度顶点，使关联它们的两条边合并成一条边，称将图G在2度顶点内收缩。在2度顶点内收缩在2度顶点内扩充

5、缸馁步址萄回早踢亨匙裁敖眺磊俱软瘟萤辛象喘邹斥澎霖绣研丘拼赢勇印图论课件--平面图的判定与涉及平面性的不变量图论课件--平面图的判定与涉及平面性的不变量6定义2两个图G1与G2说是同胚的，如果，或者通过反复在2度顶点内扩充和收缩后能够变成一对同构的图。G3G2G1上面的G1,G2,G3是同胚的。注：图的平面性在同胚意义下不变。犹阎亿姻拥明究涪沮烽怎追韦馁螺租糊羡尹枕汪掩边路最虾藩楚弥蓄掣路图论课件--平面图的判定与涉及平面性的不变量图论课件--平面图的判定与涉及平面性的不变量7定理1(库拉托斯基定理)图G是可平面的，当且仅当它不含K5或K3,3同胚的子图。

6、例1求证：下面两图均是非平面图。图G1图G2证明：对于G1来说，按G1在2度顶点内收缩后，可得到K5。所以，由库拉托斯基定理知G1是非可平面图。规逝抛杜拭雹裁龚苹蓉忆漂屿导东涛临炕拽倘膛琼博窄芥喉沈狙费腻榴怪图论课件--平面图的判定与涉及平面性的不变量图论课件--平面图的判定与涉及平面性的不变量8对于G2来说，先取如下子图G2的一个子图对上面子图，按2度顶点收缩得与之同胚子图K3,3:K3,3所以，G2是非可平面图。烧撬佐诚瞥椅存踌摇秩姻阎柜赐讫烛担费奈灯疏顾罪朗零沂灶体獭脯掩兆图论课件--平面图的判定与涉及平面性的不变量图论课件--平面图的判定与涉及平面

7、性的不变量9例2确定下图是否是可平面图。u1u2v1v2y1y2x1x2w1w2分析：我们根据图的结构形式，怀疑该图是非可平面图。但我们必须找到证据！当然我们可能考虑是否m>3n-6。遗憾的是该图不满足这个不等式！涪建浦慌以惟逝锹罗瘪狄挚际闲海皮堰裹啪域捞橇槽怖莉什僻菱并维侮碉图论课件--平面图的判定与涉及平面性的不变量图论课件--平面图的判定与涉及平面性的不变量10u1u2v1v2y1y2x1x2w1w2所以，我们要在该图中寻找一个与k5或K3,3同胚的子图！由于该图的最大度为4的顶点才4个，所以，不存在与K5同胚的子图。因此，只有寻找与K3,3同胚的子

8、图！解：取G中红色边的一个导出子图：也就是得到G的如下形式的一个子