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

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

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