完全四部图K1,1,m,n和K1,3,3,n的交叉数下界

《完全四部图K1,1,m,n和K1,3,3,n的交叉数下界》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号：学校代码：10165密级：学号：201511000556硕士学位论文完全四部图K和K的交叉数下界,1,1m,n,3,3,1nTheLowerBoundoftheCrossingNumberofKandK,1,1m,n,3,3,1n作者姓名：李喜悦学科、专业：应用数学研究方向：图论导师姓名：张新立副教授杨希武副教授2018年3月辽宁师范大学硕士学位论文摘要图的交叉数理论是图论中十分重要的一个分支，多年来，国内外很多学者都从事过有关图的交叉数这一问题的研究。事实上，Garey和Johnson证明了确定一个图的交叉数是NP-完全问题，

2、正是由于其难度，国内外在这方面的进展才如此缓慢。到目前为止，能确定交叉数的完全多部图少之又少。本文主要研究几个完全多部图的交叉数。本文的主要内容：（1）对于完全四部图K，首先，构造出K的一个好画法，证明其交叉数,1,1m,n,1,1m,n的一个上界；其次，对K的一个好画法进行适当的调整，构成完全三部图K,1,1m,n,1m,1n1的一个好画法，证明出K交叉数的一个下界；最后，假设完全三部图K的交,1,1m,n,2m,n叉数是z(m,2n)2mn，进而得到K当m与均为奇数时的交叉数：n,1,1m,nmm1mn，cr(K,1,1

3、m,n)z(m,2n)22n22并给出当m,n为其他情形时K交叉数的猜想。,1,1m,n（2）依据完全四部图K好画法的局部特征，我们将K的好画法分为两类，,2,2,1n,2,2,1n再用和（1）类似但不同于Ho的方法证明了K的交叉数：,2,2,1ncr(K)z,5(n)3n.,2,2,1n2（3）对于完全四部图K，首先，通过构造完全三部图K的一个好画法，给出,3,3,1n,4,3nK交叉数的猜想：cr(K)z,7(n)4n2n2；其次，构造出K的一个好画,4,3n,4,3n2,3,3,1n法，

4、证明其交叉数的一个上界。根据K好画法的局部特征，我们将K的好画法,3,3,1n3,3,1,n分为三类，对K的一个好画法进行适当的调整，构成完全三部图K的一个好画,3,3,1n,4,3n1法，证明出K交叉数的一个下界；最后，结合K交叉数的猜想，进而得到K交1,3,3,n,4,3n,3,3,1n叉数的猜想：(),7()53n3crKznn.,3,3,1n2关键词：交叉数；完全多部图；好画法-I-完全四部图K和K的交叉数下界,1,1m,n,3,3,1nTheLowerBoundoftheCrossingNumberofKandK

5、,1,1m,n,3,3,1nAbstractThecrossingnumberofgraphsisaveryimportantbranchofgraphtheory.Overtheyears,manydomesticandforeignscholarshaveengagedinthestudyoftheproblemofthecrossingnumberofgraphs.Infact,GareyandJohnsonprovedthatdeterminingthecrossingnumberofagraphisaNP-completepr

6、oblem.Duetothedifficultyofthecrossingnumberproblem,thedomesticandinternationalresearchprogressonthisissueisveryslow.Sofar,thecrossingnumbersoffewcompletemultipartitegraphsareknown.Thispapermainlystudiesthecrossingnumberofseveralcompletemultipartitegraphs.Themaincontentso

7、fthispaperareasfollows:(1)Forthecomplete4-partitegraphK,firstly,inordertogetanupperboundofthe,1,1m,ncrossingnumberofK,weconstructagooddrawingofK.Secondly,inordertoget,1,1m,n,1,1m,nalowerboundofthecrossingnumberofK,bymakingappropriateadjustmentsona,1,1m,ngooddrawingofK,we

8、constituteagooddrawingofcompletetripartitegraphK.,1,1m,n,1m,1n1Finally,assumingthatthecrossingnumbero