论文部分内容阅读
对图的性质的研究是图论中的一个重要部分，本文主要研究将图画在平面上图的交叉数的确定．并对循环图C(2m,m)嵌入在可定向曲面上的亏格分布进行了讨论．
如果把图画在平面上，则对于一些图来讲，无论怎么画，它的边必然相交，图G的交叉数是指将它画在平面上边交叉的最少次数，记为cr(G)，其中画法满足：
(1)任何两条边最多相交一次；
(2)边自身不相交；
(3)有相同端点的两条边不相交；
(4)没有三条边交于同一个点；
(5)任何一边不过除它端点之外的顶点．
研究图的交叉数不仅有重要的理论意义，而且有较强的实际意义，如VLSI芯片设计．
图G在曲面上的2-胞腔嵌入是指将图画在曲面上，使得G的边只在它们的公共顶点处相交且G画在曲面上对应的每一个面同胚于一个开圆盘．对图的2-胞腔嵌入的研究包含许多问题，比如：最大亏格，最小亏格，平均亏格，亏格分布等．
本文共分为三章．
第一章，介绍了一些本文需要的基本知识．
第二章，在前人研究的基础上给出了两类图的交叉数，证明了cr(S3+Sn)=n2-[n/2],以及cr(Wn×Pm)=(m-1)[n/2][n-1/2]+(m+1),n≥3,m≥1．
第三章，利用加边法给出了循环图C(2m,m)的亏格分布的递推公式．