五階圖與星圖的笛卡爾積圖的交叉數(shù).pdf

1、圖的交叉數(shù)是近代圖論中發(fā)展起來(lái)的一個(gè)重要概念，自從上個(gè)世紀(jì)五十年代初匈牙利數(shù)學(xué)家Paul turán根據(jù)其在一個(gè)磚廠碰到的實(shí)際難題(Turán’s brick factory problem)，從而提出了交叉數(shù)的概念以來(lái)，圖的交叉數(shù)逐漸成為國(guó)際上一個(gè)非?；钴S的圖論分支，使得很多圖論專家對(duì)這方面進(jìn)行了深入研究． 研究圖的交叉數(shù)不僅具有重要理論意義，而且有較強(qiáng)的現(xiàn)實(shí)意義，如超大規(guī)模集成電路VLST中的圈布局問(wèn)題、電子線路板設(shè)計(jì)中的布

2、線問(wèn)題等．1983年計(jì)算機(jī)科學(xué)家Garey和Johnson證明了確定圖的交叉數(shù)是一個(gè)NP完全問(wèn)題，由于其難度，我們能夠確定交叉數(shù)的圖類非常少，在許多情況下，即使找出圖的交叉數(shù)的一個(gè)好的上界或下界也非常困難．目前，很多文獻(xiàn)在研究一些特殊圖類的交叉數(shù)，例如：完全圖，完全2-部圖，完全3-部圖及笛卡爾積圖等．本文研究幾個(gè)連通五階圖與星圖Sn的笛卡爾積圖的交叉數(shù)． 第一章：交代了本文的寫作背景，交叉數(shù)研究在國(guó)內(nèi)外發(fā)展的動(dòng)態(tài)，研究工作的意

3、義以及本文中要解決的問(wèn)題和創(chuàng)新之處． 第二章：給出一些基本概念和性質(zhì)，介紹了閱讀本文所需要的預(yù)備知識(shí)，并介紹了在后面章節(jié)中會(huì)出現(xiàn)的一些相關(guān)概念、性質(zhì)以及常用到的一些引理，而部分使用較少的概念則放到了具體的章節(jié)中去交代． 第三章：著重研究了三個(gè)五階圖G12、G15、G18與星圖Sn的笛卡爾積圖的交叉數(shù)問(wèn)題，分別確定它們各自的交叉數(shù)為： 1．cr(G12×Sn)=n(n-1)，n≥1． 2．cr(G15×Sn