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

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

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

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