幾類聯(lián)圖交叉數(shù)的確定.pdf

1、自20世紀(jì)70年代，Paul Tur(n)提出交叉數(shù)的概念后，研究圖的交叉數(shù)漸漸成為近代圖論中的一個(gè)重要分支。它主要探究把一個(gè)圖畫在平面或曲面上，使得交叉數(shù)的數(shù)目最少。由于其理論在實(shí)際應(yīng)用中的指導(dǎo)作用，吸引了國內(nèi)外眾多專家和學(xué)者的關(guān)注和研究。然而，Garey和Johnson已確定研究圖的交叉數(shù)是NP-完全問題，即多項(xiàng)式復(fù)雜程度的非確定性問題。因?yàn)槠潆y度，現(xiàn)今有關(guān)圖的交叉數(shù)方面的研究結(jié)果并不豐富，主要集中在具有特殊結(jié)構(gòu)的圖或小階圖上。

2、r>　　本文主要確定了兩個(gè)特殊的五階圖不連通圖和n個(gè)孤立點(diǎn)的聯(lián)圖的交叉數(shù)，并在此基礎(chǔ)上得到了一些圖的交叉數(shù)。
　　本文主要結(jié)構(gòu)如下:
　　第一章:緒論.闡述了圖的交叉數(shù)的起源和實(shí)際意義，介紹寫作背景及本文的基本框架。
　　第二章:簡述了本文用到的圖論的一些預(yù)備知識(shí)及在后文中常用的定義、性質(zhì)、引理。
　　第三章:確定了一個(gè)特殊的5-階不連通圖和n個(gè)孤立點(diǎn)的聯(lián)圖的交叉數(shù)。
　　第四章:確定了一個(gè)特殊的5-階不連