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

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

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