全文总字数：699字

1. 研究目的与意义

图的交叉数是图的一种重要参数，研究图的交叉数不仅具有重要理论意义，而且具有较强的现实意义，如VLSI中的布线问题，电子线路板设计的布线问题，软件开发过程中文档部分的实体联系图的自动生成等。一般情况下，确定图的交叉数是十分困难，确定图的交叉数是一类NP完全问题，同时对于确定某种图类的交叉数的方法，用于类似的图类上往往是不适合的，例如确定完全2-部图的方法并不能确定完全2-部图的交叉数，随着研究对象的阶数不断扩大，好画法的数目会增加，采用原有的方法来研究图的交叉数会越发困难，近年来，越来越多的研究人员采用结合计算机或其他学科中的方法来确定交叉数，这对以后的研究有很好的提示作用，采用这些新方法，也是我们所要面对的十分具有挑战性的工作，对今后研究图的交叉数具有十分重要的意义。

2. 国内外研究现状分析

图的交叉数是图论中的重要参数【文献(0)】。匈牙利数学家palturan通过砖厂碰到的实际问题（turansbrickfactoryproblem）【文献(1)】提出了交叉数的概念。此后，图的交叉数问题成了活跃的图论分支，很多图论专家对图的交叉数进行了的深入的研究，现实生活中有很多方面与图的交叉数有关，比如：生物工程的dna图示；草图的识别与重新画的问题；在工业上，电子线路板设计的布线问题这些与图的交叉数都有着密切的关系。确定图的交叉数是一个np完全问题【文献(2)】，目前为止有关图的交叉数的结果很少，在不少情况下，找出图的交叉数的上界或下界也是很困难的，目前国际上对交叉数的研究主要有笛卡尔积的交叉数、完全二部图的交叉数、完全三部图的交叉数、循环图、广义petersen图等。对于完全三部图的交叉数的研究，早在上世纪八十年代就有所研究，至今的研究成果如下：

1、k.asamo证明了，

2、黄元秋教授证明了【文献(3)】

3. 研究的基本内容与计划

研究内容：研究完全3-部图的交叉数

第一章：引言部分主要介绍图的交叉数的相关知识，好画法的定义以及所要证明的定理的提出

第二章：引理以及定理的证明，通过反证法、同构以及对n的奇偶性的讨论得到完全3-部图的交叉数的上下界，得以证明

4. 研究创新点

理论证明的交叉数，寻找完全三部图的交叉数的上界、下界，n要从奇数与偶数两方面着手，在通过反证法等数学的理论方法证明的同时，还可以通过MATLAB软件作图进行辅助证明。