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

1、圖的交叉數(shù)是圖論中的一個(gè)重要概念，目前圖的交叉數(shù)問題已成為國際上一個(gè)非?；钴S的圖論分支．研究圖的交叉數(shù)不僅具有重要的理論意義，而且具有特有的實(shí)踐意義，在許多領(lǐng)域有著非常廣泛的作用，如工業(yè)上電子線路板設(shè)計(jì)中的布線問題；生物工程DNA的圖示；軟件開發(fā)過程中文檔部分的ER圖(實(shí)體聯(lián)系圖)等的自動(dòng)生成等等． 已經(jīng)知道確定圖的交叉數(shù)是一個(gè)NP完全問題(見文獻(xiàn))，因此，到目前為止有關(guān)交叉數(shù)的結(jié)果比較少，特別是對(duì)于星圖Sm與輪Wn的笛卡兒積的

2、交叉數(shù)，六階圖與星圖Sn的笛卡兒積的交叉數(shù)的研究更少．本文首先介紹了交叉數(shù)的背景和預(yù)備知識(shí)，然后在第二章證明了星圖S3與輪Wn的笛卡兒積的交叉數(shù)為2[(n-1)2/4]+[n/2]+5,n≥3，在第三章證明了輪W4與星圖Sn的笛卡兒積的為交叉數(shù)為Z(5，n)+2n+[n/2]，n≥1，在第四章確定一個(gè)六階圖F與星圖Sn的笛卡兒積的交叉數(shù)為Z(6，n)+2[n/2]，n≥1，在第五章確定了兩個(gè)完全二部圖去邊后的交叉數(shù)即cr(K3,n/e)