论文部分内容阅读
图的交叉数问题主要考虑的是如何把一个图画在平面上，使得其边与边之间产生的交叉数数目最少．图G的交叉数cr(G)，是指在图G的全部画法中边与边产生的交叉的最小值．本文利用了好画法D下子图的分离圈方法，证明了两个特殊的m(≥5)阶图与n个孤立点的联图的交叉数．主要内容包括:(1)确定了图Gm(1)与两个孤立点的联图的交叉数以及在Gm(1)的分离圈下Ti与Gm(1)的交叉数情况．在此基础上，利用数学归纳法和反证法，得到Gm(1)(m≥5)与n个孤立点的交叉数．(2)分别确定了图Gm(2)与一个点和两个孤立点的联图的交叉数，再进一步确定在Gm(2)的分离圈下Ti与Gm(2)的交叉数情况．在此基础上，结合数学归纳法和反证法，得到Gm(2)(m≥5)与n个孤立点的交叉数．