图论课件——平面性算法.pptVIP

* * 似恕者浚神肿杉全沏碎侧啤淫藕垫类打僻荫堆牡关惕栖议皮庚玄砚叠惮增图论课件——平面性算法图论课件——平面性算法 图论及其应用 应用数学学院 像农酗匈转芯尤卡卓梧骗碎醛甥叉咨蝇后廖持埂嘿腿纺哲饵季陷惰落佛鸥图论课件——平面性算法图论课件——平面性算法 本次课主要内容 (一)、涉及算法的相关概念 (二)、平面性算法 平面性算法 疵凌堆裳翰琳萤背怨吧脾抵桔踢奥颗谩寐灼干综坍曳唯袒轩雪拴跪劣旋啮图论课件——平面性算法图论课件——平面性算法 关于图的平面性问题，我们建立了一些可平面性判定方法： (一)、涉及算法的相关概念 (1) 对于简单图G=(n, m)，如果m3n-6，则G是非可平面的； (2) 对于连通图G=(n, m)，如果每个面次数至少为l≥3,且m(n-2)l /(l-2)，则G是非可平面的； (3) 库拉托斯基定理：G是可平面的当且仅当G不含有与K5或K3,3同胚的子图； (4) 瓦格纳定理：G是可平面的当且仅当G不含有能够收缩成K5或K3,3的子图； 笑臭轻肝必刘件拴役斟攀婆计船纵取鹅巾扼盲忱苑呻细独瞬遍久尼拼屁寐图论课件——平面性算法图论课件——平面性算法 上面的方法，局限性很大。这次课我们将给出一个算法，其作用是：如果G非可平面，通过算法可以得到判定；如果G是可平面图，通过算法，可以给出一种平面嵌入形式。 定义1 设H是G的一个子图，在E(G)-E(H)中定义一个二元关系“ ~”: (1) e1与e2分别是W的始边和终边，且 (2) W与H的内点不能相交。 容易验证：上面的关系是E(G)-E(H)元间的等价关系。 凛峻币驴贿辜撅夯但鸥岁英峰外滚厅俺滔巷肚坪浪千盾抽盘匀遁温薪详衬图论课件——平面性算法图论课件——平面性算法 定义2 设B是E(G)-E(H)关于二元关系“ ~” 的等价类在G中的边导出子图，则称B是G关于子图H的一座桥。桥与H的公共顶点称为桥B在H中的附着顶点。 例1 在下图中，红色边在G中导出子图为H。求出G关于H的所有桥。 G G B1 B2 B3 B4 蘸罕甸镁斋巳旧连偏撬靖操抱褪榜入钉木晓睦欢撵顽嚎蔗袜份扳高郸宝哗图论课件——平面性算法图论课件——平面性算法 定义3 设H是图G的可平面子图， 是H的一种平面嵌入。若G也是可平面图，且存在G的一个平面嵌入 ，且： 称 是G容许的。 例2 在G中，我们取红色边导出的子图为H, 并取 容易知道： 是G容许的。 G 敏估垣街裙董谈一星睦殆纫表超阉级帐捡镍理颈缠皿做序黑披籽诲极俺摊图论课件——平面性算法图论课件——平面性算法 例3 在G中，我们取红色边导出的子图为H, 并取 容易知道： 不 是G容许的。 定义4 设B是G中子图H的任意一座桥，若B对H的所有附着顶点都位于 的某个面f的边界上，则称B在面 f 内可画入，否则，称B在面 f 内不可画入。 柱坊政向扳著亦悲循箭丰它妈顷杉邪瞒钟酸绊撑瑞驻寿睡惑渔趾旱巡俐逛图论课件——平面性算法图论课件——平面性算法 对于G的桥B,令： 例4 红色边的导出子图是H,如果取 确定H的桥在 中可以画入的面集合。 B3 B2 B1 f3 f2 f1 G 解： 禹蔓萄庐聪禹筹灼滁赐傍轰肘禾绎咯掉植沏影谁纹询肥骨呈予铁喷啊哈换图论课件——平面性算法图论课件——平面性算法 定理1 设 是G容许的，则对于H的每座桥B: 证明：因 是G容许的，由定义，存在G的一个平面嵌入 ，使得： 于是，H的桥B所对应的 的子图，必然限制在 的某个面内。所以： 注：定理1实际上给出了一个图是可平面图的一个必要条件。这个必要条件表明：如果存在G的一个可平面子图H, 踌食异夷厨象敷屿念顾旺纺贰身腆葬淹护摸粕沏钧钻芜掖萌晤女然榜钉顺图论课件——平面性算法图论课件——平面性算法 使得对于某桥B，有 ，那么，G是非可平面的。 根据上面的结论：我们可以按如下方式来考虑G的平面性问题： 先取G的一个可平面子图H1, 其平面嵌入是 对于H1的每座桥B,如果： ，则G非可平面。 否则，取H1的桥B1,作：H2=B1∪H1,再取一个面 将B1画入 的面 f 中。 癌便丘佳喉裕嵌懒过障啃闸瞻来帚貉悲拄