廣義Kautz有向圖GK(2，n)和交錯群圖AG-,n-的反饋數(shù).pdf

1、對簡單圖G=(V，E)，F(xiàn)是G的點(或邊)子集，如果由V\F(或E\F)導出的子圖不含圈，則稱F是G的反饋點(或邊)集。記fv(G)(或fa(G))為所有反饋點(或邊)集的最小的階數(shù)，稱為G的反饋點(或邊)數(shù)。 確定圖的最小反饋點集問題因其在諸多領域內(nèi)具有廣泛的應用而得到重視。例如，光纖網(wǎng)絡中波長轉換器的安裝問題；網(wǎng)絡傳輸過程中避免廣播風暴問題；計算機操作系統(tǒng)避免死鎖問題等都可以轉化為確定圖的最小反饋點集問題。 鑒于其理

2、論和實際意義，本文通過計算機構造和數(shù)學推理證明相結合的方法，研究了廣義Kautz有向圖GK(2，n)和交錯群圖AGn的反饋數(shù)。 對于廣義Kautz有向圖GK(2，n)，通過將其頂點集合V(GK(2，n))劃分為六個子集，本文給出并證明了GK(2，n)的反饋數(shù)的上界為 對于交錯群圖AGn，本文定義了其頂點集合V(AG，)的n-1個子集，然后證明了這些子集構成了AGn的剩余無圈子集。在此基礎上，本文證明了當n≥5時，AGn的