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

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

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