图论课件--平面性算法

图论课件--平面性算法

ID:21531821

大小:1.11 MB

页数:30页

时间:2018-10-22

图论课件--平面性算法_第1页
图论课件--平面性算法_第2页
图论课件--平面性算法_第3页
图论课件--平面性算法_第4页
图论课件--平面性算法_第5页
资源描述:

《图论课件--平面性算法》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、图论及其应用应用数学学院1本次课主要内容(一)、涉及算法的相关概念(二)、平面性算法平面性算法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的子图;3上面的方法,局限性很大。这次课我们将给出一个算法,其作用是:如果G非可平面,通过算法可以

2、得到判定;如果G是可平面图,通过算法,可以给出一种平面嵌入形式。定义1设H是G的一个子图,在E(G)-E(H)中定义一个二元关系“~”:(1)e1与e2分别是W的始边和终边,且(2)W与H的内点不能相交。容易验证:上面的关系是E(G)-E(H)元间的等价关系。4定义2设B是E(G)-E(H)关于二元关系“~”的等价类在G中的边导出子图,则称B是G关于子图H的一座桥。桥与H的公共顶点称为桥B在H中的附着顶点。例1在下图中,红色边在G中导出子图为H。求出G关于H的所有桥。GGB1B2B3B45定义3设H是图G的可平面子图,是H的一种平面嵌入。若G也是可平面图,且存在G的一个平面嵌入,且:称是G容

3、许的。例2在G中,我们取红色边导出的子图为H,并取容易知道:是G容许的。G6例3在G中,我们取红色边导出的子图为H,并取容易知道:不是G容许的。定义4设B是G中子图H的任意一座桥,若B对H的所有附着顶点都位于的某个面f的边界上,则称B在面f内可画入,否则,称B在面f内不可画入。7对于G的桥B,令:例4红色边的导出子图是H,如果取确定H的桥在中可以画入的面集合。B3B2B1f3f2f1G解:8定理1设是G容许的,则对于H的每座桥B:证明:因是G容许的,由定义,存在G的一个平面嵌入,使得:于是,H的桥B所对应的的子图,必然限制在的某个面内。所以:注:定理1实际上给出了一个图是可平面图的一个必要条

4、件。这个必要条件表明:如果存在G的一个可平面子图H,9使得对于某桥B,有,那么,G是非可平面的。根据上面的结论:我们可以按如下方式来考虑G的平面性问题:先取G的一个可平面子图H1,其平面嵌入是对于H1的每座桥B,如果:,则G非可平面。否则,取H1的桥B1,作:H2=B1∪H1,再取一个面将B1画入的面f中。10如果B1可平面,则只要把B1平面嵌入后,得到H2的平面嵌入然后再进行上面相同的操作,可以得到G的边数递增的子图平面嵌入序列:最终,得到可平面图G的一种平面嵌入形式。(二)、平面性算法1964年,Demoucron,Mlgrance和Pertuiset提出了下面的平面性算法,简称DMP算

5、法。11设G是至少三个顶点的简单块。(1)取G的一个圈H1,求出H1的一个平面嵌入。置i=1;(2)若E(G)-E(Hi)=Φ,则停止;否则,确定G中Hi的所有桥,并对每座桥B,求出;(3)若存在桥B,使得:,则停止(G不可平面);否则,在Hi的所有桥中确定一个使得最小的B,并取。(4)在桥B中取一条连接Hi中两个附着顶点的路Pi,置Hi+1=Hi∪Pi,把Pi画在的面f内,得到12(5)置i=i+1转(2)。例5用平面性算法考察下图G的平面性。v6v5v4v3v2v1v8v7图G解:(1)取G的一个圈H1,并作平面嵌入:13v6v5v4v3v2v1v8v7图G(2)v6v5v4v3v2v1

6、v8v7H1v6v5v4v3v2v1v8v7f1f214v6v5v4v3v2v1v8v7图G(3)取B1和f1.(4)取P1=v1v3f3v6v5v4v3v2v1v8v7f1f215v6v5v4v3v2v1v8v7图G(3)取B2和f3.(4)取P2=v2v7v6v5v4v3v2v1v8v7f1f2f316v6v5v4v3v2v1v8v7图Gv6v5v4v3v2v1v8v7f1f2f3f417(3)取B1和f1.(4)取P3=v1v4v6v5v4v3v2v1v8v7图Gv6v5v4v3v2v1v8v7f1f2f3f5f418v6v5v4v3v2v1v8v7图G(3)取B1和f5.(4)取P4

7、=v2v6v6v5v4v3v2v1v8v7f1f2f3f6f4f519v6v5v4v3v2v1v8v7图G继续下去,得到:v6v5v4v3v2v1v8v7算法分析:主要运算包括:20(i)找出块G中的一个圈Hi;(ii)确定G中Hi的桥以及它们对于Hi的附着点;(iii)对于的每个面f确定其周界;(iv)对于的每座桥B,确定(v)在Hi的某座桥B中求一条起点与终点均为附着点的一条路Pi。可证上述每一个算法均存

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。