论文部分内容阅读
本文主要研究了拓扑图论中的重要研究领域一图在曲面上的嵌入性质,给出了轮图和轮型图(Halin图)在环面上柔性的计算公式;证明了局部大边宽嵌入图的一些性质,并且证明了存在无数的图满足局部大边宽嵌入条件而不满足大边宽嵌入条件,同时,证明了在局部大边宽条件下存在多项式时间算法可以找到一个图的最短可收缩圈;最后,我们对一些图在射影平面上的交叉数问题进行研究,得到了它们的不可定向交叉数序列.具体内容如下:
1.利用Jordan曲线定理和经典的组合计数方法,得到了轮图在环面上柔性的计算公式,结合轮图的结果以及环面的性质,得到了轮型图(Halin图)在环面上柔性的计算公式.
2.利用C.Thomassen在大边宽嵌入方面的工作,得到了局部大边宽嵌入图的一些性质,再利用线性代数的知识,证明了在局部大边宽条件下存在多项式时间算法可以找到一个图的最短可收缩圈.
3.利用子式理论的部分结果,证明了一些循环图C(10,4),C(9,3),C(8,3)在射影平面上的交叉数,再利用嵌入技巧,得到了它们的不可定向交叉数序列,并证明C(10,4)的不可定向交叉数序列不是凸的.