论文部分内容阅读
图G的交叉数是将G画在平面上时交叉次数的最小值,记为cr(G)。其中画法满足: (1)任何两条边相交叉的边最多交叉一次; (2)边不能自身交叉(3)有相同端点的两条边不交叉; (4)没有3条边交叉于同一点。称含最小交叉数的画法为最优画法。一般而言,确定图的交叉数是一个完全NP-问题,给出给定图的交叉数的具体值是项非常困难的工作。对交叉数的研究主要集中在对完全图,n部图,广义Petersen图,循环图,笛卡尔积图的交叉数的计算上。目前知道交叉数的图类很少,其中知道交叉数的图类主要集中在简单图的特殊图与路,与星图,与圈,简单的特殊图之间的笛卡尔积图等。
本文共分两章。
第一章中综述了本篇文章主要要用的基本概念,以及前人给出的关于交叉数的已有结果。
第二章中给出了一些新的结果:
循环图C(11,4)和C(13,4)的交叉数。
两个笛卡尔积图的交叉数。
一个三部图的交叉数。