關(guān)于圖的邊添加和邊減少問題研究.pdf

1、本文用圖G來作為互連網(wǎng)絡(luò)拓撲結(jié)構(gòu)的模型.圖G的直徑是網(wǎng)絡(luò)延遲和通信有效性的重要度量.在實時系統(tǒng)中，信息傳輸延遲被限制在某個時間內(nèi)，超出這個時間接收到的信息是無效的.一種減小傳輸延遲的辦法是給網(wǎng)絡(luò)增加連線，使得信息傳輸時間限制在給定范圍內(nèi).前人已經(jīng)證明在任意一個直徑為d的圖中添加t條邊后得到的變更圖的直徑不會小于一條長為d的路添加t條邊后所得圖的直徑. 本文研究的是“加邊問題”和“減邊問題”.確定了以下參數(shù)值的范圍和某些精確值.

2、 用P(t，d)和C(t，d)分別表示在n階無向路和n階無向圈中添加t條邊后得到的變更圖的最小可能直徑. 用TP(p，d)和TC(p，d)分別表示在n階無向路和n階無向圈中至少需要添加的邊數(shù)，使得變更圖的可能直徑不大于p. 用f(t，d)表示在直徑為d的連通圖中去掉t條邊后得到的連通圖的最大可能直徑. 在第二章中，我們對某些滿足與k相關(guān)條件的t和d證明了P(t，d)≤2k或P(t，d)≤2k+1.主定理證明

3、中用到了不等式的上界. 在第三章中，我們得到以下結(jié)果： 1.當t≥4，d≥3時，有[d-2/t+1]≤P(t，d)≤[d-2/t+1]+1；對t≥4和某些d值有P(t，d)=[d-2/t+1]+1. 2.當t≥3，d≥2時，有C(t，d)≥[d-1/t+2]，并且對某些特殊的t和d值不等式取等號.對某些t和d值也得到了C(t，d)的最優(yōu)界. 3.當p≥4,d≥12時；有[d/p]-1≤TP(p,d)≤[d

4、-7/p-3]-1.當P(t，d)=[d-2/t+1]+1和t≥4時;有[d-2/p-1]-1≤TP(p,d)≤[d-2/p-2]-1.當d≥11時，有d-7≤TP(3，d)≤d-3;TC(3，d)=d-8;其中后者是Grigorescu的猜想. 4.對于t≥3，d≥3；當P(t，d)=[d-2/t+1]+1時有f(t，d)≥(t+1)d-t+1；其它情形有f(t，d)≥(t+1)d+t.對某些t和d值證明了Schoone等人的