Kautz圖K(d,n)和Kn_del圖W(4n)的反饋數研究.pdf

1、對簡單圖G=（V，E），子集F(C)V，如果由子集V\F導出的子圖不含圈，那么稱子集F是圖G的反饋點集，頂點數最小的子集F的頂點數稱為圖G最小反饋數。反饋數是互連網絡拓撲結構圖的一個重要參數，它可以用來估計并行處理器計算機的性能。
　　人們重視確定圖的最小反饋點集問題研究，是由于在諸多領域內它都具有廣泛的應用。例如，波長改變器在光纖網絡中的安裝問題、廣播風暴在網絡傳輸過程中的避免問題以及圖的最小反饋點集問題都可以由計算機操作系統(tǒng)避

2、免死鎖問題等轉化而來。
　　實踐表明，圖論在設計和分析互連網絡方面發(fā)揮著不可替代的作用，因為互連網絡的結構可以抽象為圖。通過對某些特殊互連網絡拓撲結構圖的研究，為設計出新一代的計算機系統(tǒng)提供更堅實的理論基礎。
　　本文主要采用數學歸納法與計算機算法相結合的研究方法，對以下兩種類型圖的反饋數的界進行研究:
　　首先，對n≥8，本文將Kautz圖K(d,n)的反饋數f(d,n)的漸近公式由f(d,n)=dn/n+dn-1/