通信網(wǎng)理論作業(yè)及答案

1、3.41. 環(huán)上有k個端（3kn），此k個端的選擇方式有種；對于某固定的k端來說，考慮可以生成的環(huán)，任指定一個端，下個端的選取方法共有k-1種，再下端的選法有k-2種，等等，注意，這樣生成的環(huán)可按兩種試圖順序取得，故有種，總的環(huán)數(shù)為2. 某一固定邊e確定了兩個端，經(jīng)過e的環(huán)數(shù)按其過余下端進(jìn)行分類，若環(huán)再過k個端（1kn-2），有選法種；對于某固定端來說，自然可以生成k!個環(huán)，從而總的環(huán)數(shù)為個。3. 兩個固定端之間的徑按其經(jīng)過端數(shù)分類，其中有一條不經(jīng)過其他端的徑，若經(jīng)過k個端，（1kn-2），則對于第一個端有（n-2）種選擇，第二個端有（n-3）種選擇，第k個端有（n-k-1）種選擇，共有 ，總

2、的徑數(shù)為 3.5 試求圖3-52中圖的主樹數(shù)目，并列舉所有的主樹。圖3-52解：為圖的端點(diǎn)編號為v1,v2,v3,v4。取v3為參考點(diǎn)，有：所得主樹如下:3.11求下圖中Vs到Vt的最大流量fst,圖中編上的數(shù)字是該邊的容量。解：本題可以利用M算法，也可以使用最大流最小割簡單計算可知：可知：最大流為12，可以安排為fs1 = 3,，fs2 =5，f21=1，f2t4，f1t=4，fs3=1，fs4=3，f3t=1，f4t=3。3.13圖3.55中的Vs和Vt間要求有總流量fst6，求最佳流量分配，圖中邊旁的兩個數(shù)字前者為容量，后者為費(fèi)用。解：本題可以任選一個容量為6的可行流，然后采用負(fù)價環(huán)法，

3、但也可用貪心算法，從Vs出發(fā)的兩條線路費(fèi)用一樣，但進(jìn)入Vt的兩條路徑費(fèi)用為7和2，故盡可能選用費(fèi)用為2的線路，得下圖1。圖1再考慮V0，進(jìn)入V0的兩條路徑中優(yōu)先滿足費(fèi)用為3的路徑，得：圖2，很容易得到最后一個流量為fst=6的圖3，邊上的數(shù)字為流量安排?？偟馁M(fèi)用為易用負(fù)價環(huán)驗(yàn)證圖4的流量分配為最佳流量分配。4.3 試證M | M | m(n) 中的列德爾公式也成立證明：又有列德爾公式成立，證畢。4.10有一個三端網(wǎng)絡(luò)，端點(diǎn)為，邊為及，v1到v3的業(yè)務(wù)由v2轉(zhuǎn)接，設(shè)所有的端之間的業(yè)務(wù)到達(dá)率為l，線路的服務(wù)率為m的M/M/1問題，當(dāng)采用即時拒絕的方式時，求：1) 各個端的業(yè)務(wù)呼損。2) 網(wǎng)絡(luò)的總通

4、過量。3) 線路的利用率。解：令：00表示e1,e2均空閑。10表示e1忙,e2閑（即e1由v1,v2間業(yè)務(wù)占用）。01表示e1閑,e2忙（即e2由v2,v3間業(yè)務(wù)占用）。11表示e1,e2均忙，且分別由v1v2,v2v3間業(yè)務(wù)占用。表示e1,e2均忙，且由v1，v3間業(yè)務(wù)占用。狀態(tài)轉(zhuǎn)移圖如右：當(dāng)時有下列關(guān)系:又 解之得:呼損而通過量線路利用率5.4一個復(fù)雜系統(tǒng)有n級梯形結(jié)構(gòu)組成如圖所示。其中有n個子系統(tǒng)作為橋，2(n+1)個子系統(tǒng)作為梯邊，它們都是可靠度為R的可以修復(fù)系統(tǒng)。求這個復(fù)雜系統(tǒng)的可靠度遞推公式，假定所有子系統(tǒng)都互相獨(dú)立。解：依次考慮1，2，3， n。依照各個橋的情況可以分類，根據(jù)1，2，3， n的好壞情況可以得到以下結(jié)果：情況概率可靠度R1-(1-R)2Rn-1R(1-R)1-(1-R2)2Rn-2R(1-R)21-(1-R3)2Rn-3NR(1-R)n-11-(1-Rn)2R0N+1(1-R)n1-(1-Rn+1)2其中： 5.8有一網(wǎng)絡(luò)結(jié)構(gòu)如圖：1. 驗(yàn)證網(wǎng)絡(luò)是否為保證網(wǎng)。2. 求聯(lián)接度和結(jié)合度。3. 若每邊的可靠度都是Re，每端的可靠度Rn,求線路故障下網(wǎng)絡(luò)的可靠度和局故障的網(wǎng)絡(luò)的可靠度。4. 求v1和v2間聯(lián)接的概率。5. 要使和都為2，如何添加一條邊來滿足。解：1. 原網(wǎng)收縮為：從而是保證圖。2. 去掉U1,U2可使網(wǎng)中斷