通信網(wǎng)理論基礎課后習題答案

1、第 頁共23頁第 頁共23頁3.4壞上有k個端（3WkWn）,此k個端的選擇方式有C：種：對J：某固定的k端來說，考慮可以生成的壞，任指定一個端，卜個端的選取方法公有k-1種，再卜端的選法有k-2種，等等，注意，這樣生成的壞可按兩種試圖順序取得，故有種,總的環(huán)數(shù)為2董導k=3L某一固定邊e確定了兩個端，經過e的環(huán)數(shù)按其過余I、端進行分類，若環(huán)再過k個端（1WkWn-2）,有選法C：2種；對于某固定端來說，自然可以生成k!個環(huán)，從而總的環(huán)數(shù)兩個固定端Z間的徑按其經過端數(shù)分類，其中有一條不經過其他端的徑,若經過k個端,（lWkWm2）,則對丁第一個端有（m2）種選擇，第二個端有（m3）種選擇，第k

2、個端有（n-k-1）種選擇，共有(-2)!(-k_2)!總的徑數(shù)為1+苧（2）!3.5試求圖352中圖的主樹數(shù)目，并列舉所有的主樹。解:為圖的端編號為vl,v2,v3,v4o取v3為參考點，有：-1-1S=_120=8-102所得主樹見卜：v3vlv2v3v4vlv2vlv2v3v43.6試證明端數(shù)n人丁4的連接圖都是非平而圖，并求n=2,3,4的全連接圖為對偶圖。證明：設有n個端的全聯(lián)接圖為Kn因為口是非平面圖，而當n5時念是心的子圖，從lfljKfl(n5)均不是平面圖。一下是對偶圖(注意2為自對偶圖)。3.7*圖氐對偶圖v2氐建七對偶圖心對偶圖0101001000010000解：首先作出

3、圖形:已知一個圖的鄰接矩陣如左，畫出此圖，并求各端之間的最小有向徑長。對所繪制圖形的端點進行編號，得鄰接矩陣。V1冬10000000v410100100第 頁共23頁經計算:00010001C2=00000000因而有d(vl,v2)=ldg%)=100010000C3=00000000J(vnv3)=2d(兒宀)=1f/(vv4)=2(v3,v4)=1其余有向徑長均為8,或不存在。3.8圖有六個端，其無向距離矩陣如2V1V2V3V4V561.V.01232r12.V21012323.匕210123V4321012匕232101%123120用P算法，求出最短樹。用K算法，求出最短樹。限制條件

4、為兩端間通信的轉接次數(shù)不超過2的最短樹。解：P算法求解：伉仏，冬亠一伉，冬，叫伉，冬川3，%，冬，叫，叫K算法求解:按最小邊長順序取得：e12=幻=幻=即=咳=1此結果意味著最短樹不唯一。V3第 頁共23頁原圖有一個邊長全為1的基本子圖G“耍求轉接次數(shù)小丁等丁2,若選取6的任何4個連續(xù)頂點，片V/+1v.+2叫+,作為基礎,然后再按要求增加邊,例如以叫v2v3卩為基礎,增加v5v6,得到一個樹長為7轉接次數(shù)小J：等J：2的樹T1,事實上，以任何4個連續(xù)頂點均可得到樹長為7的轉接次數(shù)小等2的樹V33.9圖有六個端，端點之間的有向距離矩陣如卜:V1V2V3V4V5V61用D算法求VI到所有其他端的

5、最短徑長及其路徑。V10913COCO2用F算法求最短徑矩陣和路由矩陣，并找到V2至V2104co7COV4和VI至V5的最短徑長及路由。2CO0co1CO3.求圖的中心和中點。00CO50270062805%7CO2CO20解:1.D算法v2V3V4V5V6指定最短徑長0OOOOOOOOOOW=09丄3OOOOv3w13=0932_OOV5W15=0837V4W14=08zV3W16=Ov2W12=02.F算法最短路徑矩陣及最短路由陣為W5,R5冬T匕一卩4有向距離為4兒T比冬有向距離為2第 頁共23頁0_006600050505606500913oOCO104oO7CO2oO0oO1COo

6、OoO5027oO628057oO2oO200913COCO10247CO211051COCOoO5027CO6280571621020_091316OO10247oO211051ocIKCOoO502776280571621020_09132co-10243co211051co71650274628054132720_0913210_10243112110511271650274627054132720_081321102438270516ws5684027462705482720TOC o 1-5 h z0005R0003050234010345023410111101I003002342

7、010115011015000305623406113150023430110113011015033056323306313350_923434101134110154R4333056101135TOC o 1-5 h z15015555056323306353350_第 頁共23頁第 頁共23頁則情況將如何?換句話說就是11已是最人流。3.MaxW=(&7、&7,8)中心為V3iJcV5工W；=(21,1&21,27,24,23)中心為V?3.11求下圖中匕到M的最大流量&圖中編上的數(shù)字是該邊的容量。解：本題可以利用M算法，也可以使用最人流一最小割簡單計算可知：X=匕川3宀f=仏，叫，叫C

8、（X,乂）=3+5+1+3=12可知:最大流為12,可以安排為f“=3fs2=5,f】2=l，&t=4，fit=4,站=1,fU=3，f3t=l，仃=3。3.12試移動3.54圖中的一條邊，保持其容量不變,是否能增人fst?如果可以,求此時的最人值，但若所有轉接端vlv2v3和v4的轉接容鼠限制在4,解:依然按照最人流一最小割定理，若能依一邊從X找到乂內部至割（X,y）中，自然可以増人流鼠，可以將乞“移去，改為：e4i或者e,均可，使總流量增至12+2=14。當vi（i=1,.4）的轉接容彊限制到4時,等效圖為右圖，對丁3.11中的流量分配,在本題限制下,若將fs2由5改為4即得到一個流鼠為1

9、1的可行流。但若=vs,v3,v；v45v；,v2,F=也我,心訂則C(XX*)=l+3+4+3=ll,3.13圖3.55中的S和M間耍求有總流最気=6,求最佳流彊分配，圖中邊旁的兩個數(shù)字前者為容量，后者為費用。解：本題可以任選一個容量為6的可行流，然后采用負價壞法，但也可用貪心算法，從Vs出發(fā)的兩條線路費用一樣，但進入Vt的兩條路徑費用為7和2,故盡可能選用費用為2的線路，得卜圖lo再考慮V0,進入V0的兩條路徑中優(yōu)先滿足費用為3的路徑，得：圖2,很容易得到最后一個流螢為fst=6的圖3,邊上的數(shù)字為流量安排?？偟馁M用為=3x2+3x24-1x3+2x4+1x1+2x3+4x2+2x7=52

10、易用負價環(huán)驗證圖4的流起分配為最佳流4.1求WbM/m（n）中，等待時間w的概率密度函數(shù)。解：WM/m（n）的概率分布為：-iPo=1一0（7MQ）k0Po0k/n-lmkn假定nm,d$0,現(xiàn)在來計算概率Pwx,既等待時間人J：x的概率。px=PP.wx；=O其中，Pjwx的概率為：P.wx=0j-nif=oP,wx=10J/H-1（加陽mjx=-凹以曠小1一pm特別的，新到顧客需等待的概率為：pwo=l.四r1-pm而皿）=晉鼻嚴0（刃丈竿-財戶G加（1_）盤i”（叱1）-心,-MPn,l（ii-m-1）!第 #頁共23頁(1-P)第9頁共23頁在ms於p加(i_p)注:Pw=O=工4Pw

11、=s=代Jt=O4.4求M7D”排隊問題中等待時間W的一、二、三階矩m】、m2.m3,D表示服務時間為定值b,到達率為兄。解：G($)=s(l-P)s-2+2B(S)其中B(5)=5(-b)es,dt=esb從而_1_Q-Ab門_-Ab2(-p)gl2(1-Ab)2(1-p)(2久b+A2b4)12(1-AZ?)3-(1+2肋)(1-p)卅24(1“r(肋=p)“=_G(0)=肋三2(1)m2=G(0)=g2x2=(2+p)Ab6(f第 #頁共23頁(1-P)第9頁共23頁(1+2/?)肋4(14.5求MB/1,E/M/l和B/B/l排隊問題的平均等待時間，其中B是二階指數(shù)分布:/(/)=必何

12、引+(1G)入廠勺A./U00al解：M/B/1B(S)叮側嚴婦能+(1-cx)a2入+SW=二?+Z11-a=肌0)老+2(1第 頁共23頁(1-P)第9頁共23頁論=兄(1-Ct)人-+Q入-jz/2,2-(1-B/M/l(1-&)人b=B(“_/Q)令%=P%=久“一(7+入/-/cr+/U0ab,求：穩(wěn)定狀態(tài)時系統(tǒng)的隊列長度為k的概率應，顧客到達時隊列的長度為k的概率顧客離去時隊列的長度(V以及平均等待時間，并用G/G/1上界公式求出此時的平均等待時間，評論計算結果，并討論aWb的情況。由J：是D/D/1問題，故子系統(tǒng)運行情況完全確定，第一個顧客到達后，系統(tǒng)無顧客，經到達離去到達此時有

13、:過b后，服務完畢，顧客離去，再經過ab后，卜一個顧客到達。k=lk=0k=00顧客不等待時帀=0恥/p(T)=8(t-Cl)p(t)=t-b)/.O-/=a,2=0G/G/上界公式Pr:.waL=0.評=02(1-P)當at,將造成呼損，rG時無呼損。幾(/)=0(r)dr則第 #頁共23頁(1-P)第9頁共23頁第 #頁共23頁(1-P)第9頁共23頁Pc=f/(r)b(r)drdt=AeAl-J(2jLi)2Te2prdrdt=才+4/1“S+2“)，第 #頁共23頁(1-P)第9頁共23頁第 頁共23頁(1-P)第9頁共23頁E隊到達率為/I?,服務率“，系統(tǒng)穩(wěn)定4.8在優(yōu)先級別隊列中

14、，A隊為優(yōu)先級，不拒絕，B隊為非優(yōu)先級，只準一人排隊等待(不計在服務中的)，且當A隊無人時才能被服務，求各狀態(tài)概率，A隊的平均等待時間和E隊的拒絕概率。解：說明：0狀態(tài)代表系統(tǒng)中無顧客狀態(tài)；1，J狀態(tài)代表系統(tǒng)中正在服務且A隊中有1個顧客，B隊列中有J個顧客排隊的狀態(tài)。狀態(tài)轉移圖如右，A隊到達率為入，時,可得到特征方程如卜:（人+入）4=冷0-1(“+人+A)oo=+o)+(A+入)人-204(“+)Pfl=+冷如+人05由J：4是差分方程，不妨設其通解為：pi0=代入有：(1+門+QjAxX=Aoo-1+汁1=F-(1+Q+p2)X+Q=00v牙v1-X=1+XA+門-Jl+R-2p+2q+2

15、PP02由于5是非齊次差分方程：P/+u-(1+A)P/,i+AA-i,i+PPz=0其特征根為：a=P假設其通解為：%=Ap；+Bx,代入前式得：B才-(1+兒+pfiXo_1+pgx；=0解之,得:B=-Poopitl=Ap-代入3式得：(l+p1)p01=p2p00+p11即：A=Poo(1+P+Q7o)PiA=Pooh+A+P：-忑加一*A.o=PooPoO=(A+P2)Po由正則條件：XP.+(0+pJPoQ+0+d_X。)工p；=1+“)P200=AiPioo+)Polo=幾bPooo+PlloZPziO=aPllO+bP200a+)P1K=APlOO+4PoiO+如210第 #頁

16、共23頁(1-P)第9頁共23頁第 #頁共23頁(1-P)第9頁共23頁歸一條件。+工門川=1若=A=K令P=入a/y第 #頁共23頁(1-P)第9頁共23頁第 頁共23頁(1-P)第9頁共23頁Pooo=PPq3p2+3”2j+嚴3P3P迦=2，十2卩+嚴2p2+2p+l3p2+9p3+12p4/乙0=、|Po2p+2p+l6p3+15p4+12p5A10=一皿八|一Po2p+2/?+l6p4+15p5+12p62+I幾P12p6+27p5+36p4+Yip、+14p2+5p+l第 #頁共23頁(1-P)第9頁共23頁第 頁共23頁(1-P)第9頁共23頁C類呼損為：Pc=l-p=E類呼損為

17、:/=Poio+/iio+PzioA類呼損為:PA=P21Q+P2QQ4.10有一個三端網(wǎng)絡,端點為v1?v2,v3,邊為勺（忖2）及冬（叫*3），V1到v3的業(yè)務由v2轉接，設所有的端Z間的業(yè)務到達率為入，線路的服務率為卩的M/M/1問題，當采用即時拒絕的方式時，求：1）各個端的業(yè)務呼損。2）網(wǎng)絡的總通過量。3）線路的利用率。解：令：00表示el,e2均空閑。10表示el忙,e2閑（即el由vl,v2間業(yè)務占用）。01表示el閑，e2忙（即e2由v2,v3間業(yè)務占用）。11表示el,e2均忙，且分別由vlv2,v2v3間業(yè)務占用。表示el,e2均忙，且由vl,狀態(tài)轉移圖如右：當人2=兄卩=入

18、3=2時有下列關系：PP,=也。3/tp00=/（p01+p10+A）（2+“）門0=勿。+如U+/）p01=2p00+/11詢間業(yè)務占用。呼損P13=1-Poo幾=Poi=Pio=PPzPu=P2Poo這里11+3q+3Q+，1+3/9+p21+3p+p22zu=4Poi+Pio）第 #頁共23頁(1-P)第9頁共23頁第 頁共23頁(1-P)第9頁共23頁3Q+2,1+3/9+p1通過量7=0（1-仏）+0（1-件）+Q（1-幾3）=l+3p+p2線路利用率=久+pn+（P10+Poi）/2=411上題中的網(wǎng)若用J：傳送數(shù)據(jù)包，到達率仍為九每秒，平均包長為b比特，邊的容磧?yōu)閏比特/秒，采用

19、不拒絕的方式，并設各端的存儲容量足夠人，求：1）穩(wěn)定條件。2）網(wǎng)絡的平均時延。3）總的通過量。4）線路的平均利用率。解：這是一個無損但有時延的系統(tǒng)。兩條線路上到達率為：2入，而服務率為：c/b的M/M/1系統(tǒng)。1）穩(wěn)定條件為：2Xb/c/C1/c314總線上有4個用戶vl,v2,v3和v4,它們之間以Alopha方式互相通信,信包到達率均為每秒，信息包的長度為b比特：總線上的傳輸速率為c比特/秒，試求通過率r,并人致畫出r與b的曲線關系。解：r與b的曲線關系如右圖，從直觀上來看，這也是顯然的。總線上一個包的服務時間0=%秒,總的呼叫量為：a=122%,通過量為：r=a-e-2a通過率：廠=/=

20、12加第 頁共23頁(1-P)第9頁共23頁51由n個元件構成的一個系統(tǒng)，各元件的平均壽命都是T。當一個元件失效據(jù)使得系統(tǒng)失效的情況卜，已知系統(tǒng)的平均壽命將卜降至T/n,如果采取容錯措施，當m個以上元件失效“1才使系統(tǒng)失效，求證此系統(tǒng)的平均壽命為：幾=T=可見比未采取措施前提高至少m倍。當m=n.l時，這一系統(tǒng)實際上即是D個元件的并接系統(tǒng)，試證上式即轉化成并連系統(tǒng)的壽命公式。證：以1狀態(tài)代表有1個元件失效的狀態(tài)，此時系統(tǒng)的狀態(tài)轉移框圖如卜：n一i第 #頁共23頁(1-P)第9頁共23頁第 #頁共23頁(1-P)第9頁共23頁從而系統(tǒng)的平均壽命為：5=S0+51+Sn,=TMni911當m=n-

21、l時S=T三k=0k而利用數(shù)學歸納法易知:當（七扣第 頁共23頁(1-P)第9頁共23頁5.2有n個不可修復系統(tǒng)，它們的平均壽命都是T。先取兩個作為并接，即互為熱備份運行;當有一個損壞時，啟用第三個作為熱備份：再損壞一個是起用第四個，已知卜去，直到n個系統(tǒng)均損壞。忽略起用冷備份期間另一系統(tǒng)損壞的可能性：試計算這樣運行I、的平均壽命:并與全冷備份和全熱備份是的平均壽命相比較。解：狀態(tài)圖如卜：1表示有1個系統(tǒng)損壞，失效在圖中標出。從而，平均壽命:S=So+S1+-+S,i_1=Ix(/7-1)+T=1ts*=nT尸卜出+ks熱S冷5.3上題目中n個子系統(tǒng)都是可修復系統(tǒng)，可靠度都是R。仍用上述方式運

22、行，一損壞系統(tǒng)修復后作為最后一個系統(tǒng)排隊等候再起用，求穩(wěn)態(tài)可靠度。解：m,mm表示n個系統(tǒng)中有m個失效，狀態(tài)轉移圖及失效率與修復率如圖：第 #頁共23頁(1-P)第9頁共23頁第 #頁共23頁(1-P)第9頁共23頁用Pm表示狀態(tài)的概率(穩(wěn)態(tài))，狀態(tài)方程如卜：2込=肌(2q+mp)pm=2嘰7+(w+1)朋”+】Qmn-1(2a+0)幾_=2ap“7+i嘰嘰t=詢”A=11=0解狀態(tài)方程如卜：有：pm=Pa0m05.5有一個故障率為67的系統(tǒng)，為了考慮是否使Z成為可修復系統(tǒng)而配備維修力駁，分別計算兩類可靠度，試證明作為不可修復系統(tǒng)在時間T以內的可靠度人J：作為可修復系統(tǒng)的穩(wěn)態(tài)可靠度的條件是：J

23、3TctT+pr0.01+0T第 #頁共23頁(1-P)第9頁共23頁第 頁共23頁(1-P)第9頁共23頁/JT0.9955.6有一故障率為a,修復率為的系統(tǒng)0,己知此系統(tǒng)的費用是C=Aar其中A,E,r,s為已知的非負常量，求可靠度為0.99時的最小費用。解：TOC o 1-5 h zzyA7=C虧+?995一deABs-99sJ令：=0有一一+399、daaBs99JrAIB,99”5.7用流量法求圖5-9(b)中的二分網(wǎng)的聯(lián)接度Q和結合度0,只考慮端故障，且各端的可靠度均為R，求1端和亍端間的聯(lián)接概率。1；2；3沖中有三個失效時1；2；3；4中有三個無失效時解：圖5-9(b)中的二分圖，任意一端度數(shù)均為4,5=4容易知道：a=0=5=4一知考慮端故障，故中有一，二,三失效和無失效是等價圖入右：可靠度分別為：l-(l-/?)3Cj/?(1-/?)31和5，Z間聯(lián)接概率為：他5，=時尺(1_町1_(1_町+.用(1_町+.用(1_尺)+.疋1_(1_町5.8有一網(wǎng)絡結構如圖:驗證網(wǎng)絡是否為保證網(wǎng)。求聯(lián)接度G和結合度0。若每邊的可靠度都是Re,每端的可靠度Rn,求線路故障卜網(wǎng)絡的