關(guān)于圖的笛卡爾積交叉數(shù)的研究.pdf

1、圖的交叉數(shù)是在近代圖論中發(fā)展起來的一個重要概念，主要研究如何把圖畫在一個平面上，使其交叉的數(shù)目最少，通常這項(xiàng)研究都采用純數(shù)學(xué)方法證明．然而，確定一般圖的交叉數(shù)是一個NP—完全問題，因此，到目前為止有關(guān)交叉數(shù)的結(jié)果比較少，僅限于一些特殊圖和簡單圖的交叉數(shù)，甚至于在許多情況下，試圖找出圖的交叉數(shù)的一個好的上界或下界也很困難． 近年來，笛卡爾積交叉數(shù)越來越受到國內(nèi)外有關(guān)學(xué)者的重視和關(guān)注．本文運(yùn)用組合方法和歸納思想以及反證法，主要研究了

2、六階圖Gi（i＝1，2，3，4）與路Pn的笛卡爾積交叉數(shù)，五階圖G13與星圖Sn的笛卡爾積交叉數(shù)，輪W5與星圖Sn的笛卡爾積交叉數(shù)，全文由五個章節(jié)構(gòu)成． 第一章：較為詳細(xì)地交代了交叉數(shù)的起源，理論和實(shí)際意義，國內(nèi)外發(fā)展的動態(tài)，本文的寫作背景，將要解決的問題和文章的創(chuàng)新之處。同時對與交叉數(shù)有關(guān)的一些基本概念和性質(zhì)進(jìn)行了解釋． 第二章：主要確定四個六階圖Gi（i=1，2，3，4）與路Pn的笛卡爾積交叉數(shù)． 第三章：主