圖的交叉數(shù)的研究.pdf

1、圖的交叉數(shù)問(wèn)題,起源于二戰(zhàn)期間Pual Turán在磚廠碰到的一個(gè)實(shí)際問(wèn)題,后來(lái)逐漸發(fā)展成為了圖論學(xué)科中非?；钴S的一個(gè)分支,吸引著大批國(guó)內(nèi)外學(xué)者的關(guān)注和研究.然而,確定一般圖類(lèi)的交叉數(shù)是一個(gè)NP-完全問(wèn)題.因此,到目前為止有關(guān)圖的交叉數(shù)的結(jié)果比較少,僅限于一些特殊簡(jiǎn)單圖的交叉數(shù).甚至在許多情況下,試圖找出圖的交叉數(shù)的一個(gè)好的上界或者下界也是很困難的.本文運(yùn)用歸納思想以及反證法,確定了兩個(gè)特殊圖:一個(gè)六點(diǎn)圖G1與路Pn的聯(lián)圖,以及一個(gè)五點(diǎn)

2、圖G2與路Pn的聯(lián)圖的交叉數(shù)的精確值,并試圖研究了關(guān)于完全二部圖K5,n的一般性質(zhì).全文由5個(gè)章節(jié)組成.
　　 第一章介紹了交叉數(shù)的起源,交叉數(shù)研究的理論與實(shí)際意義,以及目前交叉數(shù)研究在國(guó)內(nèi)外的發(fā)展情況.同時(shí)還簡(jiǎn)要介紹了本文的主要結(jié)構(gòu).
　　 第二章介紹了閱讀本文所要用到的圖的交叉數(shù)方面的基本概念和預(yù)備知識(shí).
　　 第三章得到了圖Gj(j=1,2)與路Pn的聯(lián)圖的交叉數(shù).
　　 第四章討論了關(guān)于完全二部圖