图的嵌入分布的平均亏格

来源 :北京交通大学 | 被引量 : 0次 | 上传用户:queenie88
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
拓扑图论研究的一个重要内容为图在曲面上的嵌入的性质.回顾历史,拓扑图论学家们首先研究的是图的最小亏格.由于确定图的最小亏格是NP-困难的[25],因此求解图的最小亏格或者确定图的最小亏格的界是一类十分困难的问题,在这方面的研究远不够理想.随后也就是上个世纪70年代初,Nordhaus,Stewart和white[17]等人提出了图的最大亏格的概念,因此研究也就转向了确定图的最大亏格的问题和刻划,由于N.H.xuong[28],Liu Yanpei[14]等于上个世纪70年代未分别独立地给出或部分的给出了刻划图的最大亏格的示性定理和Nebesky[18]于上个世纪80年代初又给出了图的最大亏格的另外一种对偶形式的刻划,因此关于图的最大亏格的研究取得了很重要的一步.关于图的最大亏格最近研究可参见黄元秋的博士论文[13].在他的博士论文里对图的最大亏格进行了进一步的研究总结及简化.S.Stahl[21]及J.L.Gross[8,9]等于上个世纪80年代提出了图的平均亏格的概念.对图的平均亏格的研究有助于对图在曲面上的嵌入有更深入细致的了解.由于确定一个图的最小亏格是NP-困难的,而确定一个图的平均亏格的值必须先求出最小亏格,因此确定一个图的平均亏格是NP-困难问题.从目前的参考文献来看,国际上主要有两个人S.Stahl[21-25]和Chen.Jianer[2-7]在图的平均亏格领域内作了深入的细致的研究.其中S.Stahl侧重于研究一些特殊图类的平均亏格[21,22],随机图的平均亏格[24]等.Chen.Jianer侧重于研究任意单个图的平均亏格[2-4,6],主要考察将图的平均亏格作为一个不变量是否为图同构的一个不变量(后来发现并不是).虽然他们着眼及出发点和所用的方法不一样但从结果上看起来确是殊途同归的(最终还是要得到一好的上下界),他们在图的平均亏格的研究成果可参见文献[2-4,6,21-25]等. 图的平均亏格还有一般性的问题还没有解决,从数学理论上看仍然需要进一步的研究. 第一类问题应该是确定一些有对称性结构的图的平均亏格(不可定向平均亏格),或者求出他们的渐近值.例如说完全图K<,n>,完全二部图K<,m,n>,立方体Q<,n>等等.两者比较而言,求出平均亏格具体值要比渐近值要容易.这两方面的结果很少[3,8,21,22]. 第二类问题应该是确定平均亏格(不可定向平均亏格)的一些好的上下界.已经知道确定一个图的平均亏格是NP-困难问题.我们不可能把所有的图的平均亏格都给算出来,因此这是不现实的一个问题.所以很自然的就是给出平均亏格的一些好的上下界.虽然已经有部分的结果[6,23,25,],但这方面仍然不够.本文沿着Chen.Jianer的思路研究了任意图的可定向平均亏格及首先对任意图不可定向平均亏格进行了研究,共分为六章. 第一章主要研究了不含三种禁用构形的图的平均亏格的下界的问题.得到了平均亏格的一些新的下界. Chen.Jianer在他的论文[2,3,6]里的结果可看作这些结论的一个直接推论(实际上推广了[2,3,6]中的结论),而且这里的证明要比[2,3,6]简单. 第二章Chen.Jianer在[6]得到了三正则图的平均亏格的最好下界.在这一章节里,我们刻划了三正则图的平均亏格达到下界的图的结构的问题.作为附带的一个结果,也得到了一个图跟它的子图有相同的平均亏格的结构问题. 第三章对不可定向平均亏格进行了研究,它可看做是可定向平均亏格在不可定向曲面上的推广.我们首先研究了两类图:仙人掌图和项链图的不可定向平均亏格.得到了仙人掌图的不可定向平均亏格的精确值和项链图的不可定向平均亏格的递推表达式.并由此确定了最大亏格为1的任意图的不可定向平均亏格的值. 第四章借助计算机确定了Betti数不超过4的图的不可定向平均亏格的值.并由此我们确定了一些最小的不可定向平均亏格的值和发现了一些不同构的图而有相同的不可定向平均亏格及有相同的可定向平均亏格而不可定向平均亏格却不同的图,跟可定向平均亏格一样不可定向平均亏格也不是一同构不变量.另外也找到一些数学方法来构造了具有相同不可定向平均亏格而不同构的图类.当然也得到了不可定向平均亏格的一些其它的性质如所有图的不可定向平均亏格在实数轴上的分布是稀疏的和不存在极限点(这与可定向平均亏格不一样[2,3])等. 第五章我们得到了不可定向平均亏格的紧的上下界.该上下界是最优的.另外也刻划了任意图的不可定向平均亏格达到上下界的图的结构的问题. 第六章由于研究者本人的能力及时间的限制,我们对本文未能解决的一些问题进行了论述. 从上面的论述可以看出本论文的主要的工作点在于提出研究了不含三种禁用构形的图的平均亏格的问题及首先对不可定向平均亏格进行了研究并得到了不可定向平均亏格的紧的上下界.最后无关紧要的说明一下本论文中大部分内容用的Liu Yanpei教授提出的方法来进行研究的,因此在方法上与S.Stahl和Chen.Jianer不一样,在研究可定向平均亏格(不可定向平均亏格)的问题中过程中得到一些有趣的结果(如第一,三章节中的辟分运算,第三章节中的Lemma 2.2,及第四章节的一些构造方法等)可能跟原问题一样有意思. 论文的最后部分列出了本论文的参考文献和到目前为止作者在博士研究生期间所接收和发表的论文.
其他文献
期刊
学位
能控性是控制系统理论的基本概念之一,对于抛物型控制系统,众所周知,由于系统解的正则性,我们只能做到近似能控,无法做到精确能控。一个自然的想法是:当系统的初态和末态满足什么样
本文主要针对几类离散系统分析了其分岔问题,并得到了一些较新颖实用的结果.全文共分五章. 第一章是综述,介绍离散系统之分岔问题的一般研究方法、研究现状及本文的工作.
本文提出了一种利用复杂系统组成设备的试验信息,对复杂系统平均寿命进行综合评估的方法。首先,考虑单个设备情况下的可靠度评估问题,在完全样本情形下利用枢轴量方法对不同设备
科学教育对于幼儿园的幼儿来说非常重要,一方面可以使得幼儿从小就养成良好的科学素养,促进今后的综合素质全面发展,另一方面可以从小培养各种动手能力和实践能力.因此对于幼
课堂的组织管理是课堂教学的重要一环,是提高教学质量的关键因素。既要使学生生动活泼地学习,又要有纪律作为保障,这无疑对教师来说是个难题。而初中物理的实践性更强,开放性
期刊
问题是师生间信息交换的重要方式,在课堂教学中,教师通过一定情境的创设,从而引发学生的有效思考,让学生在学习过程中去发现问题、提出问题、分析并解决问题,从而促进学生思
期刊