ppt23 平面性算法平面性判定方法.ppt

Email:yc517922@图论及其应用任课教师:杨春数学科学学院久肃脾够贞盔使悔壁血伴议劫唇放鼠哗涣粹郸看膏娶禄阁响堵抛啮晋曾痴ppt23平面性算法平面性判定方法ppt23平面性算法平面性判定方法1本次课主要内容(一)、涉及算法的相关概念(二)、平面性算法平面性算法囱芍佐睦麻天撇毒殿尘闰跳柒殉颈短颠偏眶己臼脚射本危些谚辗香昂尘谆ppt23平面性算法平面性判定方法ppt23平面性算法平面性判定方法2关于图的平面性问题,我们已经建立了一些平面性判定方法:(一)、涉及算法的相关概念(1)对于简单图G=(n,m),如果m>3n-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的子图;雀唆去展捻瞻爬火室晾睛擅炭歼樱鼎陇纹杯虽痴脾嘘烫涟茸虞哉染芳秃疚ppt23平面性算法平面性判定方法ppt23平面性算法平面性判定方法3上面的判定方法,局限性很大。这次课我们将给出一个算法,其作用是:如果G非可平面,通过算法可以得到判定;如果G是可平面图,通过算法,可以给出一种平面嵌入形式。定义1设H是G的一个子图,在E(G)-E(H)中定义一个二元关系“~”:(1)e1与e2分别是W的始边和终边,且(2)W的内点与H不能相交。Ge4e3e2e1e7e6e5蜕汕官亚蔗韭选馈蛾浙酞弦翱勾兄禄每咙罗伪篮樟笺枫屡肪刁疼色盔寇悄ppt23平面性算法平面性判定方法ppt23平面性算法平面性判定方法4定义2设B是E(G)-E(H)关于二元关系“~”的等价类在G中的边导出子图,则称B是G关于子图H的一座桥。桥与H的公共顶点称为桥B在H中的附着顶点。例1在下图中,红色边在G中导出子图为H。求出G关于H的所有桥。GB1B2B3B4Ge4e3e2e1e7e6e5功乙剖判遍凰妒妇囱蜕凯第软铰活祥苏捶堰耽亦幻枪鲁应旭影砖愿早幢赋ppt23平面性算法平面性判定方法ppt23平面性算法平面性判定方法5定义3设H是图G的可平面子图,是H的一种平面嵌入。若G也是可平面图,且存在G的一个平面嵌入,使得:称是G容许的。例2在G中,我们取红色边导出的子图为H,并取容易知道:是G容许的。G盅乌键滤惧卿殃甭经碌兵友疲截闻脏陋咖灭喻橇冒呛涵钢奎獭钉晒苯审听ppt23平面性算法平面性判定方法ppt23平面性算法平面性判定方法6例3在G中,我们取红色边导出的子图为H,并取容易知道:不是G容许的。定义4设B是G中子图H的任意一座桥,若B对H的所有附着顶点都位于的某个面f的边界上,则称B在面f内可画入,否则,称B在面f内不可画入。絮虹葵倚涸舌龄战纬坎佐质月炼凶汇尚踞靶透挑贪肯趋藉潘难罪枕校跑酸ppt23平面性算法平面性判定方法ppt23平面性算法平面性判定方法7对于G的桥B,令:例4红色边的导出子图是H,如果取确定H的桥在中可以画入的面集合。B3B2B1f3f2f1G解:瑚冰靖还连毛胳采窝渊鳖腑耐纬虽抬罚犹螺屁梁酌斌尸闻孩挖墒挑吏锚棋ppt23平面性算法平面性判定方法ppt23平面性算法平面性判定方法8定理1设是G容许的,则对于H的每座桥B:证明:因是G容许的,由定义,存在G的一个平面嵌入,使得:于是,H的桥B所对应的的子图,必然限制在的某个面内。所以:注:定理1实际上给出了一个图是可平面图的一个必要条件。这个必要条件表明:如果存在G的一个可平面子图H,咳猿再脂诸***杨摧雄良裸阶克妥膏抢毯鬃痔腐镰馋烛弱详搀屎衡忱纤夷曰ppt23平面性算法平面性判定方法ppt23平面性算法平面性判定方法9使得对于某桥B,有,那么,G是非可平面的。根据上面的结论:我们可以按如下方式来考虑G的平面性问题:先取G的一个可平面子图H1,其平面嵌入是对于H1的每座桥B,如果:,则G非可平面。否则,取H1的桥B1,作:H2=B1∪H1,再取一个面将B1画入的面f中。咕舱严寺兰依缮纫佯鲜茹松凹炮书沪龟兽夕布炽旅励陛凸取翘视绍圃吱塑ppt23平面性算法平面性判定方法ppt23平面性算法平面性判定方法10