文献综述
图的交叉数问题起源于二战时期PualTuraacute;n在砖厂碰到的一个实际问题，后来逐渐发展成为图论学科中非常活跃的一个分支，吸引着大批国内外学者的关注和研究，通常这项研究都采用纯数学方法证明。其理论在电路板设计，草图识别与重画以及生物DNA的图示等领域有广泛的应用。到目前为止有关图的交叉数的结果比较少,仅限于一些特殊简单图的交叉数.甚至在许多情况下,试图找出图的交叉数的一个好的上界或者下界也是很困难的。目前，很多文献都是在研究一些特殊图类的最小交叉数，例如：完全图，完全二部图，完全三部图，循环图及笛卡尔积图等。
一个图的一个画法是指这个图画在平面上满足下列条件的一个画法：（1）关联同一个顶点的两条边不相交，（2）两条边相交不多于一次，（3）三条边不相交于同一个点。一个图的最大交叉数是最大的k使得这个图有一个含有k个交叉点的画法。 顶点数大于1的完全图是任何两个顶点之间都有一条边的图， 而顶点数为1的完全图就是一个顶点。一条有n个顶点的路是将这n个顶点用边依次相连得到的图。
完全图与路的并的最大交叉数研究是一项很有意义且具有挑战性的工作。多年了，国内外有许多学者都从事交叉数研究，但是，到目前为止，还没有一种有效的算法能确定一般图类的交叉数。更不必说完全图的交叉数了，事实上现今已确定一般图类的交叉数是一个NP-完全问题.因此,现在研究的主要对象为一些具体的特殊结构图类的交叉数。由于其研究难度非常大，国内外在这方面的研究进展都十分缓慢。
本课题主要研究如何把图画在一个平面上,使其交叉的数目最多，即给出完全图K4与一条路Pn的并的最大交叉数的界。当n取较小的值时，确定完全图K4与一条路Pn的并的最大交叉数。给出完全图K5与一条路Pn的并的最大交叉数的界。
由于确定一个图的交叉数是一件困难的事, 人们往往给出这个图的交叉数的上界. 上界多大是合理的? 人们往往考虑图的最大交叉数. 另外, 图的最大交叉数在离散几何中有一定的应用.
对于任意一个图，设是图的边集，为的顶点的度。Piazza等人[10]给出了的最大交叉数的上界为。在1969年,Saaty [11]证明了一个有n(3)个顶点的完全图的最大交叉数为。1994年，Piazza 等人[7] 证明了图的最大交叉数至多为80。
以上是毕业论文文献综述，课题毕业论文、任务书、外文翻译、程序设计、图纸设计等资料可联系客服协助查找。
