六階不連通圖與孤立點(diǎn)的聯(lián)圖的交叉數(shù).pdf

1、圖的交叉數(shù)是在近代圖論中發(fā)展起來的一個重要概念，起源于二十世紀(jì)四十年代，是圖的非平面性的一個重要參數(shù).自Paul Turn提出交叉數(shù)的概念后，對圖的交叉數(shù)的研究漸漸成為近代圖論中的一個重要研究方向，它主要研究圖在一個平面或曲面上最優(yōu)畫法下的最小交叉數(shù)，是拓?fù)鋱D論中的前沿問題.它的理論在電路板設(shè)計(jì)（見文獻(xiàn)[1]）、草圖識別以及生物工程DNA圖示等領(lǐng)域有廣泛的應(yīng)用，因此吸引了國內(nèi)外眾多專家和學(xué)者的關(guān)注與研究.但Garey和Johnson已確

2、定一般圖的交叉數(shù)是NP-完全問題（見文獻(xiàn)[2]），即多項(xiàng)式復(fù)雜程度的非確定性問題.由于其難度，到目前為止有關(guān)交叉數(shù)的研究結(jié)果并不豐富，主要集中在具有特殊結(jié)構(gòu)的圖或小階圖上，這些圖多為連通圖，不連通圖的結(jié)果并不多.
　　本文主要確定了一個特殊六階不連通圖和n個孤立點(diǎn)的聯(lián)圖的交叉數(shù)并給予證明.
　　本文主要結(jié)構(gòu)如下:
　　第一章:緒論，闡述了圖的交叉數(shù)的起源和實(shí)際意義，介紹了圖論及圖的交叉數(shù)的研究背景及本文的基本結(jié)構(gòu).