论文部分内容阅读
拓扑图论研究的一个重要内容为图在曲面上的嵌入的性质.回顾历史,拓扑图论学家们首先研究的是图的最小亏格.由于确定图的最小亏格是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,及第四章节的一些构造方法等)可能跟原问题一样有意思.
论文的最后部分列出了本论文的参考文献和到目前为止作者在博士研究生期间所接收和发表的论文.