小階圖與孤立點(diǎn)、路及圈的聯(lián)圖的交叉數(shù).pdf

1、圖的交叉數(shù)是在近代圖論中發(fā)展起來(lái)的一個(gè)重要概念，起源于19世紀(jì)五十年代，是拓?fù)鋱D論中的前沿問(wèn)題。它主要研究圖在一個(gè)平面或曲面上最優(yōu)畫法下的最小交叉數(shù)目，是圖的非平面性的一個(gè)重要參數(shù)。由于其在電路板設(shè)計(jì)和生物工程DNA圖示等領(lǐng)域的廣泛應(yīng)用，吸引著眾多國(guó)內(nèi)外的專家和學(xué)者的關(guān)注與研究。但Garey和Johnson已確定一般圖的交叉數(shù)是NP-完全問(wèn)題。因而，到目前為止，有關(guān)圖的交叉數(shù)方面的研究結(jié)果較少。但在一些特殊圖類和簡(jiǎn)單圖的交叉數(shù)方面的研究

2、結(jié)果還是比較豐富的。
　　本文主要確定了一個(gè)不連通六階圖和特殊的六階圖分別與孤立點(diǎn)、路及圈的聯(lián)圖的交叉數(shù)并給予證明。
　　本文主要結(jié)構(gòu)如下:
　　第一章:緒論，簡(jiǎn)述圖的交叉數(shù)的起源及應(yīng)用，介紹了圖論及圖的交叉數(shù)的研究背景及本文的結(jié)構(gòu)。
　　第二章:給出本文用到的圖論的一些基本的概念，以及在后文中常用的性質(zhì)、引理。
　　第三章:不連通六階圖與孤立點(diǎn)、路及圈的聯(lián)圖的交叉數(shù)的確定及證明。
　　第四章:特定六