特殊圖G與路與圈以及與孤立點(diǎn)的聯(lián)圖交叉數(shù).pdf

1、圖的交叉數(shù)問(wèn)題起源于二戰(zhàn)時(shí)期PualTurán在磚廠碰到的一個(gè)實(shí)際問(wèn)題，后來(lái)逐漸發(fā)展成為圖論學(xué)科中非?；钴S的一個(gè)分支，吸引著大批國(guó)內(nèi)外學(xué)者的關(guān)注和研究，其理論在電路板設(shè)計(jì)，草圖識(shí)別與重畫(huà)以及生物DNA的圖示等領(lǐng)域有廣泛的應(yīng)用.但是，k確定一般圖類(lèi)的交叉數(shù)問(wèn)題已經(jīng)被證明是一個(gè)NP-完全問(wèn)題.因此，至今為止有關(guān)圖的交叉數(shù)問(wèn)題的結(jié)果還非常少，且已被確定交叉數(shù)的圖類(lèi)大多數(shù)都是一些比較特殊的圖類(lèi)，故很多方法都不能推廣到一般情況.甚至有的時(shí)候找出圖

2、的交叉數(shù)的一個(gè)比較好的上界或下界也很困難.本文運(yùn)用歸納法的思想以及反正法確定了兩個(gè)特殊圖類(lèi)的交叉數(shù)：一個(gè)六階圖H與路Pn的聯(lián)圖的交叉數(shù)以及一個(gè)四階不連通圖G與路，圈聯(lián)圖的交叉數(shù)本文一共由五個(gè)章節(jié)組成。
　　 第一章，主要介紹了交叉數(shù)的起源，交叉數(shù)研究的理論與實(shí)際意義，目前關(guān)于交叉數(shù)的一些研究現(xiàn)狀，同時(shí)本章節(jié)還簡(jiǎn)要的介紹了本文主要結(jié)構(gòu)。
　　 第二章，介紹了閱讀本文時(shí)所必須的一些關(guān)于交叉數(shù)方面的基本概念以及一些重要結(jié)果。<