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

1、本文用圖G來作為互連網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的模型.圖G的直徑是網(wǎng)絡(luò)延遲和通信有效性的重要度量.在實(shí)時(shí)系統(tǒng)中，信息傳輸延遲被限制在某個(gè)時(shí)間內(nèi)，超出這個(gè)時(shí)間接收到的信息是無效的.一種減小傳輸延遲的辦法是給網(wǎng)絡(luò)增加連線，使得信息傳輸時(shí)間限制在給定范圍內(nèi).前人已經(jīng)證明在任意一個(gè)直徑為d的圖中添加t條邊后得到的變更圖的直徑不會(huì)小于一條長(zhǎng)為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條邊后得到的連通圖的最大可能直徑. 在第二章中，我們對(duì)某些滿足與k相關(guān)條件的t和d證明了P(t，d)≤2k或P(t，d)≤2k+1.主定理證明

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

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