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

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

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

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

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

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