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

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

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