版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)
文檔簡介
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)=
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 眾賞文庫僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
- 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- Flower Snark和K-,m--e□P-,n-的交叉數(shù).pdf
- 完全三部圖K-,n-,1-,n-,2-,n-,3--的競爭數(shù).pdf
- m-,0,n-上的S-,n-作用.pdf
- K-,n,n-的[r,s,t]-染色.pdf
- k-元n-立方體的路和圈.pdf
- 3色Ramsey數(shù)R(C-,m-,1--,C-,m-,2--,C-,m-,3--).pdf
- 研究N-Σ和N-Λ相互作用.pdf
- 完全二部圖K-,m,n-的k-good邊著色.pdf
- 完全二部圖K-,n,n-的循環(huán)圈分解.pdf
- 相對n-星模和n-傾斜模.pdf
- n-同態(tài),保n-零積映射和局部n-同構(gòu).pdf
- ZI-,n-環(huán)和ZC-,n-環(huán).pdf
- M-,n+1-AX-,n-可加工陶瓷材料的腐蝕行為研究.pdf
- W-,3,n-的支配問題與二部圖的弧的公有性研究.pdf
- 循環(huán)圖C(n;{1,k})的交叉數(shù).pdf
- Si-,n-(n=2-19)團簇和C-,50-,C-,60-富勒烯的摻雜研究.pdf
- 關(guān)于n-平移代數(shù)和n-阿貝爾范疇的研究.pdf
- N-烷基酰胺和N-烷基磺胺衍生物的合成.pdf
- n-表現(xiàn)維數(shù)的若干研究.pdf
- N-(k,zp)的截斷子群的擴展.pdf
評論
0/150
提交評論