论确定图的最小亏格

来源 :北京交通大学 | 被引量 : 0次 | 上传用户:yangwenhuai
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
图在曲面上的可嵌入性是拓扑图论的主要问题,其中图的最小亏格问题是NP-困难的,所以对解决任意图的最小亏格仍需很长的一段距离。基于此,本文主要是在刘彦佩提出的联树模型的基础上,选择考虑了有趣且有意义的图类来研究其最小亏格问题,除此之外还计算了特定图类的可定向嵌入的亏格分布。本文所考虑的图类对已研究最小亏格或亏格分布的图类有一定的推广作用,所用方法提升了计算技巧,从而为更广泛图类的最小亏格及亏格分布问题的研究提供了更广阔的前景。本研究分为七个部分: 第一章首先对这两方面的研究背景作了简要的介绍.随后,给出了一些与之相关的定义和性质。 第二章首先利用异于以前的方法得到了完全二部图的最小亏格.然后基于完全二部图关联曲面的特点进行推广,构造了对称性比较弱的新图类J(m,n)且得其最小亏格,最后对完全二部图不同最小亏格嵌入的数目作了估算。 第三章构造了对称性比较弱的新图类T(n,l,m)且得其最小亏格.作为推论得到了完全三部图Kn,n,l(l≥n≥2)的最小亏格.最后对完全三部图Kn,n,l不同最小亏格嵌入的数目作了估算。 第四章研究了边合并图的最小亏格.文献[1,2]分别讨论了完全图与完全图,完全二部图与完全二部图边合并的最小亏格问题,本章给出了n个特定图边合并的最小亏格。 第五章讨论了几类图与一节点的联图的最小亏格.而平面图与一节点的联图亦为apex图.众所周知,apex图是拓扑图论中比较重要的一类图,在图的最小亏格问题研究中具有强大的作用. Mohar证明了apex图的最小亏格问题是NP-困难的,本章考虑了几类平面图与一节点的联图,即为apex图,以及两类未必是平面的图与一节点联图的最小亏格。 第六章,推广了[21]中“珠子”的类,构造了异于目前已知亏格分布的图类,所用方法主要是根据给定图类的特点,选择确切的支撑树,把关联曲面集合进行分类,建立递推关系式,进而得给定图类的可定向嵌入亏格分布的显式表达式,由此可进一步考虑具有任意多节点且其度大于3和4的此类正则图的可定向嵌入亏格分布。 第六章首先构造了推广的项链图,循环项链图以及推广的另三类图,其次得其可定向嵌入亏格分布的显式表达式,最后把上面图类进一步推广,得到了一类更一般的图,并对其可定向嵌入的亏格分布进行了刻画。 第七章介绍了图的最小亏格及亏格分布领域中一些需要更进一步研究的问题,如如何利用联树模型计算完全图的最小亏格,以及如何通过刻画最小亏格关联曲面的特性来确定更广泛图类,乃至任意图类的最小亏格问题等等。
其他文献
学位
十七世纪下半叶,在前人工作的基础上,英国数学家牛顿和德国数学家莱布尼茨创立了微积分理论,从而把两个貌似毫不相关的问题(一个是切线问题,一个是求面积问题)联系在一起.从那
本文首先对一维周期脉冲系统进行了详尽的研究,用Poincare映射和后继函数的方法讨论了周期解的存在性、稳定性及其判据和分支;对平面哈密顿系统周期性脉冲扰动下闭轨的分支也进
在对目前的空气净化系统的分析过程中,有许多共存的问题,诸如经济效益、性能优化、安全性等问题,还有一些未知因素存在,诸如未建模动态、参数不确定性、工作环境的变化或外部干扰
I期临床试验研究首次用于人体试验的药物,目的是从预先给定的剂量水平中找出最大耐受剂量(MTD),以用于后续的II期和III期临床试验.本文以新药的I期临床试验设计为主线,从临床试
组合合作对策,又称组合最优化对策,是建立在组合最优化模型上的合作对策.合作对策理论研究的核心问题是如何将联盟的整体收益(或费用)公平合理地分配给每个局中人.不同的分配合