圖的交叉數(shù)問題研究.pdf

1、圖的交叉數(shù)問題是在實際應用中提出來的，在電子線路板的設計，CAD領域有廣闊的應用．目前已經(jīng)確定交叉數(shù)的圖類主要集中于頂點數(shù)較小或者交叉數(shù)較小的圖．本文對一些頂點數(shù)較大或交叉數(shù)較大的圖的交叉數(shù)問題進行研究，將計算機構造性證明和數(shù)學證明相結合，取得了較好的結果． 本課題組給出的交叉數(shù)算法CCN已被成功地用于計算頂點數(shù)較小的圖的交叉數(shù)．但由于圖的交叉數(shù)問題是NP困難問題，對頂點數(shù)較大或交叉數(shù)較大的圖，所需要的計算時間仍然太多．針對這一

2、問題，本文給出了計算圖的交叉數(shù)上界的算法CCN><'+>，把計算圖的交叉數(shù)上界問題轉化為計算往其子圖的較少交叉點畫法中回添邊時所產(chǎn)生的交叉數(shù)的問題，從而可以對較大規(guī)模的圖的交叉數(shù)性質(zhì)進行研究．利用該算法計算了頂點數(shù)p≤12的所有路徑冪圖P<'k><,n>和13≤p≤20且k≤9的所有P<'k><,n>的較好的交叉數(shù)上界． 對與圈C<,n>交圖的交叉數(shù)，目前研究的較多的是兩個圈的交圖以及頂點數(shù)較小的圖與圈交圖的交叉數(shù)．RJngei

3、sen和Beineke對K<,m>口C<,n>，m≤4進行了研究．本文對K<,m>口C<,n>進行研究，給出了相應的交叉數(shù)計數(shù)方法，確定了這類圖的交叉數(shù)下界．對m=5，6，7或者n為不小于4的偶數(shù)，給出了交叉數(shù)上界及對應的畫法；如果著名的完全圖交叉數(shù)猜想對K<,m+2>成立，則本文給出的交叉數(shù)上界就是完全圖K<,m>與圈G<,n>交圖的交叉數(shù)． 對與路徑P<,n>交圖的交叉數(shù)，目前研究的較多的也是頂點數(shù)較小的圖與路徑交圖的交叉數(shù)

4、．Klesc等人對K<,m>口R<,n>，m≤5進行了研究．Bokal對K<1,l>．口P<,n>進行了研究．黃元秋與Klesc分別研究了W<,m>口P<,n>的n≤3與m=3，4的情形；Klesc對W<,2.3>口P<,n>進行了研究．本文針對K<,m>口P<,n>,K<,m,l>口P<,n>W<,l,m>口P<,n>進行了研究，給出了這些圖的交叉數(shù)上界．并對其中K<,m>口P<,n>L<,2,l>口P<,n>，W<,m>口P<,n>

5、,W<,2,m>口P<,n>給出了相應的交叉數(shù)計數(shù)方法，進而導出了這些圖的交叉數(shù)下界．并最終確定了K<,6>口P<,n>，K<,2,l>，口P<,n>，W<,2,m>口P<,n>，W<,2,m>口P<,n>的交叉數(shù)，擴展了與路徑交圖的交叉數(shù)的研究結果． 本文所給出的交叉數(shù)研究方法還可以用于研究其它圖的交叉數(shù)問題．作為應用實例，本文確定了兩類三正則圖Kn6del圖以J<,3,n>和Flower Snarlk及其相關圖F<,n>的交