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

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

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