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

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

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