论文部分内容阅读
图的交叉数理论是图论中十分重要的一个分支,多年来,国内外很多学者都从事过有关图的交叉数这一问题的研究。事实上,Garey和Johnson证明了确定一个图的交叉数是NP-完全问题,正是由于其难度,国内外在这方面的进展才如此缓慢。到目前为止,能确定交叉数的完全多部图少之又少。本文主要研究几个完全多部图的交叉数。 本文的主要内容: (1)对于完全四部图,K1,1,m,n首先,构造出K1,1,m,n的一个好画法,证明其交叉数的一个上界;其次,对K1,1,m,n的一个好画法进行适当的调整,构成完全三部图K1,m+1,n+1的一个好画法,证明出K1,1,m,n交叉数的一个下界;最后,假设完全三部图K2,m,n的交叉数是z(m+2,n+2)-mn进而得到K1,1,m,n当m与n均为奇数时的交叉数:cr(K1,1,m,n)=z(m+2,n)+([)m/2(])([)m-1/2(])n+([)m/2(])([)n/2(]),并给出当m,n为其他情形时K1,1,m,n交叉数的猜想。 (2)依据完全四部图K1,2,2,n好画法的局部特征,我们将K1,2,2,n的好画法分为两类,再用和(1)类似但不同于Ho的方法证明了K1,2,2,n的交叉数:cr(K1,2,2,n)=z(5,n)+([)3n/2(]). (3)对于完全四部图K1,3,3,n,首先,通过构造完全三部图K3,4,n的一个好画法,给出K3,4,n交叉数的猜想:cr(K3,4,n)=z(7,n)+4n+2([)n/2(])+2;其次,构造出K1,3,3,n的一个好画法,证明其交叉数的一个上界。根据K1,3,3,n好画法的局部特征,我们将K1,3,3,n的好画法分为三类,对K1,3,3,n的一个好画法进行适当的调整,构成完全三部图K3,4,n+1的一个好画法,证明出K1,3,3,n交叉数的一个下界;最后,结合K3,4,n交叉数的猜想,进而得到K1,3,3,n交叉数的猜想:cr(K1,3,3,n)=|z(7,n)+5n+3([)n/2(])+3.