環(huán)和環(huán)形樹負(fù)載問題的一些結(jié)果.pdf

1、　　論文分三部分,第一部分討論無向環(huán)和無向環(huán)形樹的負(fù)載問題,包括第一,二章：第二部分討論有向環(huán)和有向環(huán)形樹的路徑選擇問題,包括第三,四章。第三部分提出改進的有向環(huán)負(fù)載問題的多項式時間近似方案,包括第五章。
　　環(huán)形樹在通訊網(wǎng)絡(luò)中有著廣泛的應(yīng)用。一個環(huán)形樹G是一個由一棵樹T得到的圖：把樹的每個頂點換成一個環(huán)(叫做頂點環(huán)),然后收縮樹的邊,使得兩個對應(yīng)于一邊的兩個頂點的環(huán)有且只有一個相同的頂點,且沒有三個頂點環(huán)共用一點。(一個更廣的定

2、義允許三個環(huán)共用一點)。第一,二章的問題是,給定一個要求的集合,D={d(i,j),i,j∈V(G)}每個要求是定義在一對頂點之間的一個非負(fù)實數(shù)。在同一個環(huán)上,每對頂點之間的所有要求必須且只能在兩條可能道路中選擇同一條道路來輸送。算法的目的是找出一個路徑選擇方案,對每個要求,在環(huán)形樹上找出一條路來滿足它,且使得環(huán)形樹上的各邊的最大負(fù)載最小化,在這里一條邊的負(fù)載指的是通過這條邊的所有路的要求值之和。我們提出一個多項式時間近似方案來解決此問

3、題。
　　對于這個問題,主要有以下結(jié)果：
　　算法2.1：環(huán)形樹負(fù)載問題的多項式時間近似算法
　　定理2.1：算法2.1是一個多項式時間近似方案
　　定理2.2 程序結(jié)束時每個要求所對應(yīng)的兩點之間的路徑是唯一的。
　　第三,四章討論有向環(huán)和有向環(huán)形樹的負(fù)載問題。有向環(huán)形樹由有向雙環(huán)構(gòu)成,構(gòu)造方法與環(huán)形樹的構(gòu)造方法相同。只是把原來無向環(huán)形樹上的每個無向環(huán)Ci換成有向雙環(huán),即兩個方向相反的有向環(huán)Ci_+和Ci_