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

1、圖的交叉數(shù)是在近代圖論中發(fā)展起來(lái)的一個(gè)重要概念，主要研究如何把圖畫(huà)在一個(gè)平面上，使其交叉的數(shù)目最少．通常這項(xiàng)研究都采用純數(shù)學(xué)方法證明．然而，確定一般圖的交叉數(shù)是一個(gè)NP—完全問(wèn)題，因此，到目前為止有關(guān)交叉數(shù)的結(jié)果比較少，僅限于一些特殊圖和簡(jiǎn)單圖的交叉數(shù)．甚至于在許多情況下，試圖找出圖的交叉數(shù)的一個(gè)好的上界或下界也很困難．本文運(yùn)用組合方法和歸納思想以及反證法，確定了一些六階圖與星的笛卡爾積的交叉數(shù)，并且研究了聯(lián)圖的交叉數(shù)．全文由五個(gè)章節(jié)構(gòu)

2、成． 在第一章中較為詳細(xì)地交代了交叉數(shù)的起源，交叉數(shù)研究的理論及實(shí)際意義，以及這項(xiàng)研究工作在國(guó)內(nèi)外發(fā)展的動(dòng)態(tài)，同時(shí)還簡(jiǎn)要介紹了本文的寫(xiě)作背景，將要解決的問(wèn)題和文章的創(chuàng)新之處． 在第二章中對(duì)與交叉數(shù)有關(guān)的一些基本概念和性質(zhì)進(jìn)行了解析，同時(shí)介紹了閱讀本文所需要的預(yù)備知識(shí)，并介紹了在后續(xù)文章中將會(huì)出現(xiàn)的定義、記號(hào)以及常用到的一些性質(zhì)．對(duì)于部分使用較少的概念我們放到具體的章節(jié)中來(lái)交代． 在第三章中著重研究了與笛卡爾積交叉