W-,3，n-和K-,m-□C-,n-的交叉數(shù).pdf

1、圖的交叉數(shù)是衡量圖的非平面性的一個重要參數(shù)，Garey和Johnson證明了計算圖的交叉數(shù)問題是NP完全的。目前僅確定了少數(shù)幾類圖的交叉數(shù)。完全圖，完全二分圖，廣義Petersen圖，循環(huán)圖，頂點數(shù)較小的圖與路徑、圈或者星圖的交圖是交叉數(shù)問題中活躍的研究對象。 Kn(o)del圖是一種互連網(wǎng)絡(luò)，研究互連網(wǎng)絡(luò)的交叉數(shù)有助于更好地理解其拓撲性質(zhì)。本文研究了Kn(o)del圖W3，n(n≥8，n為偶數(shù))的交叉數(shù)。首先利用計算機構(gòu)造了W

2、3,n交叉數(shù)較少的畫法，給出交叉數(shù)上界；然后設(shè)計了W3,n的邊分組方式和交叉點計數(shù)函數(shù)給出其下界。最終證明：cr(W3，8)=0；cr(W3，10)=1；cr(W3，n)=[n/6]+n mod 6/2，當n≥12時. Ringeisen和Beineke給出了K3□Cn以及K4□Cn的交叉數(shù)。本文進一步研究了完全圖和圈的交圖Km□Cn的交叉數(shù)。通過設(shè)計Km□Cn的分組方式和交叉點計數(shù)方法，給出了Km□Cn交叉數(shù)的下界：

3、cr(Km□Cn)≥n cr(Km+2).通過改進計算圖的交叉數(shù)算法CCN的限界條件，利用計算機構(gòu)造了Km□Cn好的畫法，給出了Km□Cn交叉數(shù)的上界：cr(Km□Cn)≤n/4[m+2/2][m+1/1][m/2][m-1/2](n為偶數(shù))；cr(Km□Cn)≤n/4[m+2/2][m/2][m-1/2]+[m-1/2]2(n為奇數(shù)).因為m≤12時Guy給出的完全圖交叉數(shù)猜想成立，所以當m≤10，n為偶數(shù)時，有：cr(Km□Cn)=