代数方法和图的平面性测试

发布时间：2018-01-10 10:28

  本文关键词：代数方法和图的平面性测试　出处：《华东师范大学》2017年硕士论文　论文类型：学位论文

  更多相关文章： 平面图 平面性测试 拓扑学 图论算法 图形可视化

【摘要】：本文共分3章,致力于研究图的平面性测试。在第一章中我们解释定义,给出DFS算法等一些著名的图算法,以及将在下一章使用的一些数学准备。在第二章中,我们描述平面性过程。为此,使用等距圈和图形顶点的旋转的方式;还将说明图形等距圈系统诱导图形顶点旋转以用于描述平面图的拓扑方案。在第三章中,我们用绘制平面图的拓扑方案的方式说明了平面性测试算法。与经典的平面性测试算法(Hopcroft-Tarjan算法)相反,作为算法执行的结果的拓扑图,之后便用于平面图的可视化。所提出的算法的计算复杂性由O(m~2)控制,其中m是图中的边数。
[Abstract]:In the first chapter, we explain the definition and give some famous graph algorithms such as DFS algorithm. And some mathematical preparations to be used in the next chapter. In Chapter 2, we describe the planarity process. It will also be explained that the graphic equidistant loop system induces the graph vertex rotation to describe the topological scheme of the planar graph. We illustrate the planarity test algorithm by using the topological scheme of drawing the planar graph, which is contrary to the classical planarity test algorithm, Hopcroft-Tarjan algorithm. As the result of the algorithm execution, the topology graph is then used to visualize the planar graph. The computational complexity of the proposed algorithm is controlled by OF2), where m is the number of edges in the graph.
【学位授予单位】：华东师范大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O157.5

【相似文献】

相关期刊论文 前6条

1 梁晶;;冲击波平面性的影响因素浅析[J];中国原子能科学研究院年报;2012年00期

2 叶大兴;判别一类图形的平面性[J];数学的实践与认识;1976年02期

3 梁晶;田宝贤;李业军;王钊;汤秀章;;高功率准分子激光驱动冲击波平面性的实验研究[J];中国原子能科学研究院年报;2011年00期

4 黄秀光;傅思祖;吴江;顾援;马民勋;舒桦;周华珍;叶君建;何钜华;王世绩;;“神光-Ⅱ”装置倍频激光直接驱动冲击波平面性的实验研究[J];强激光与粒子束;2006年05期

5 谢军;邢丕峰;易泰民;杨蒙生;孙涛;袁光辉;郑凤成;;冲击波平面性、稳定性实验用双边多台阶Al靶制备[J];原子能科学技术;2010年01期

6 刘晓平;;G~(---)的平面性(英文)[J];新疆大学学报(自然科学版);2006年02期

相关重要报纸文章 前1条

1 杜大恺;中国画以空白为底[N];文艺报;2010年

相关硕士学位论文 前5条

1 王欣;纯穆之美[D];云南艺术学院;2016年

2 高燕;油画创作中平面性的形式探究[D];山东师范大学;2016年

3 Khakimov Pavel;代数方法和图的平面性测试[D];华东师范大学;2017年

4 姜旭慧;浅谈油画创作中平面性与装饰性的应用[D];辽宁师范大学;2013年

5 王硕;“留白”之道[D];鲁迅美术学院;2013年

，

本文编号：1404927