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

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

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