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

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

2、ower Snark相關圖Jn、Kn(o)del圖W△，n和循環(huán)圖Cn（1,k）的反饋數(shù)、增廣立方體AQ反饋數(shù)的上下界、局部扭立方體LTQn反饋數(shù)的上界以及Kautz有向圖K(d，n)反饋數(shù)的上界。
　　(1)對Flower Snark相關圖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)結構，分別找到了相應的帶循環(huán)節(jié)的無圈子圖頂點集的構造方法

3、，基于這些頂點集分別得到了如下結論。
　　①給出了Flower Snark相關圖Jn反饋數(shù)為:f（Jn）=n+1;
　?、诮o出了W3,n反饋數(shù):f（W3,n）=「n+2/4(]);
　　③給出了W4,n反饋數(shù):f（W4,n）=「n+1/3(]);
　?、芙o出了偶數(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)絡的反饋數(shù)進行了研究。利用AQ和LTQn頂點遞推結構和邊集性質，分別構造出了相應的可遞推的無圈子圖頂點集函數(shù)，基于這些函數(shù)，分別給出如下結論。
　?、俳o出了AQ反饋數(shù)緊的上下界為:2n-3×2n-3≤f（AQn）≤2n-（2n-2+2([)n-1/2」）;
　　②給出了LTQn反饋數(shù)的上界為:f(LTQn)≤2n-1。
　　(3)對有向Kautz圖K(d，n)的反饋數(shù)