關(guān)于一些圖類(lèi)的交叉數(shù).pdf

1、我們已經(jīng)知道確定圖的交叉數(shù)是一個(gè)NP完全問(wèn)題(見(jiàn)文獻(xiàn)[1])，因此，到現(xiàn)在為止有關(guān)交叉數(shù)的結(jié)果比較少，在許多情況下，甚至找出圖的一個(gè)好的上界或下界也很艱難.本文研究路與某些6-階圖的笛卡兒積交叉數(shù)，及在假定ZaranKiewicz猜想成立的基礎(chǔ)上研究完全3部圖K1,10,n及完全3部圖K1,m,n當(dāng)m，n均為偶數(shù)時(shí)的交叉數(shù). 在第一章：交代了本文的寫(xiě)作背景，交叉數(shù)研究在國(guó)內(nèi)外發(fā)展的動(dòng)態(tài)，研究工作的意義以及本文中要解決的問(wèn)題和創(chuàng)新

2、之處. 在第二章：給出一些基本概念和性質(zhì)，介紹了閱讀本文所需要的預(yù)備知識(shí)其中主要包括交叉數(shù)的概念，并介紹了在后面文章中會(huì)出現(xiàn)的一些相關(guān)概念、性質(zhì)以及常用到的一些定理，而部分使用較少的概念等我們放到了具體的章節(jié)中去交代. 在第三章：我們確定了5個(gè)六階圖與路Pn的笛卡兒積圖的交叉數(shù).在第四章：在假定ZaranKiewicz猜想對(duì)m=11成立的基礎(chǔ)上，我們得到了完全3部圖K1,10,n的交叉數(shù)，并且將結(jié)果推廣到假定Zarank