论文部分内容阅读
图的可嵌入性的概念源于平面性,早在30年代初,波兰数学家K.Kuatowski和其后美国数学家H.Whitney,S.Maclane在图的可嵌入性方面做过精湛的研究。他们在该方面都创立了各自的理论。50年代,中国数学家吴文俊基于代数拓扑学中的理论揭示了判定图的平面性的一个判断准则,其后又得到许多学者的改进,提出了更好的算法,如刘彦佩基于确向树,使算法的复杂性上达到了线性顶峰,在图的平面性和平面嵌入上做出很大的贡献。随着研究的深入,到70年代,Nordhuas E,Stewart B,White A等人提出了图在曲面上的可嵌入性问题,其中最大亏格问题及图的上可嵌入性是重要的组成部分。
亏格是图的一个拓扑不变量,本文主要总结和研究了图在曲面上嵌入的最大亏格,揭示了图的某种属性或含有一定特征的图对其最大亏格的影响。全文分为三部分:
在第一章中,首先介绍了图论中图的参数的基本定义,综述了图的嵌入性理论的基本知识,从图的平面嵌入引出了图在曲面上的嵌入,重点叙述了图的最大亏格理论,两个确定最大亏格的基本定理,一个是Xuong的理论,一个是Nebesky理论,两者都是围绕着与图的最大亏格十分密切的参数Betti亏数的大小,揭示了最大亏格的计算方法。之后,黄元秋在Nebeski7理论的基础上,给出了参数Betti亏数与图的特征结构的关系,为从图的结构上来研究图的最大亏格开辟了一个新的途径。
在第二章中,介绍了一些目前已得到的关于图的最大亏格与某些图的参数的理论结果,这些参数包括顶点的度,图的连通度,直径,围长,割点,独立数,嵌入的面的度数,着色数,正则性,2-因子等.对于图的直径,黄元秋和刘彦佩得到了一类直径为4的不含K<,3>子图的简单连通图的最大亏格的下界,但是该下界并非是紧的下界.在第二节中,通过分析和证明改进了他们的结果,并发表了文章,文章中得出改进的结果为紧的下界。最后,对于任意的有限无向的无环图,给出了一种构造上可嵌入图的方法。
第三章为结束语,对最大亏格的某些方面的研究,文中提出了自己的看法,希望所指出的想法能够给以后的研究工作带来益处。