幾類重要互連網(wǎng)絡(luò)拓撲結(jié)構(gòu)圖的反饋數(shù)研究.pdf

1、圖的反饋數(shù)問題是在實際應(yīng)用中提出來的。計算機操作系統(tǒng)中解決“死鎖”問題、網(wǎng)絡(luò)攻擊中最小攻擊點集問題等都可以轉(zhuǎn)化為在圖中求一個最小反饋點集的問題。
　　求圖的反饋數(shù)問題已被證明是NP困難問題，其每一個進展都十分艱辛。到目前為止，只有少數(shù)的圖類得到了其反饋數(shù)，已經(jīng)得到反饋數(shù)界的圖類也不多。
　　本文對與互連網(wǎng)絡(luò)拓撲結(jié)構(gòu)設(shè)計方法（笛卡兒乘積方法、線圖方法、Cayley方法）密切相關(guān)的幾個重要的圖類的反饋數(shù)進行了研究，分別給出了Fl

2、ower Snark相關(guān)圖Jn、Kn(o)del圖W△，n和循環(huán)圖Cn（1,k）的反饋數(shù)、增廣立方體AQ反饋數(shù)的上下界、局部扭立方體LTQn反饋數(shù)的上界以及Kautz有向圖K(d，n)反饋數(shù)的上界。
　　(1)對Flower Snark相關(guān)圖Jn、Kn(o)del圖W3,n和W4,n、循環(huán)圖Cn（1,k）的反饋數(shù)進行了研究。利用Jn、W3,n、W4,n和C，n（1,k）的循環(huán)結(jié)構(gòu)，分別找到了相應(yīng)的帶循環(huán)節(jié)的無圈子圖頂點集的構(gòu)造方法

3、，基于這些頂點集分別得到了如下結(jié)論。
　?、俳o出了Flower Snark相關(guān)圖Jn反饋數(shù)為:f（Jn）=n+1;
　　②給出了W3,n反饋數(shù):f（W3,n）=「n+2/4(]);
　?、劢o出了W4,n反饋數(shù):f（W4,n）=「n+1/3(]);
　　④給出了偶數(shù)n≥5k+1+2（（k+1/2）mod3）且3≤奇數(shù)k＜m/2時的Cn（1,k）反饋數(shù):f(Cn（1,k））=「n+1/3(])。
　　(2)對增

4、廣立方體AQ、局部扭立方體LTQn兩種變型超立方體網(wǎng)絡(luò)的反饋數(shù)進行了研究。利用AQ和LTQn頂點遞推結(jié)構(gòu)和邊集性質(zhì)，分別構(gòu)造出了相應(yīng)的可遞推的無圈子圖頂點集函數(shù)，基于這些函數(shù)，分別給出如下結(jié)論。
　?、俳o出了AQ反饋數(shù)緊的上下界為:2n-3×2n-3≤f（AQn）≤2n-（2n-2+2([)n-1/2」）;
　?、诮o出了LTQn反饋數(shù)的上界為:f(LTQn)≤2n-1。
　　(3)對有向Kautz圖K(d，n)的反饋數(shù)