通信网理论基础课后习题答案

1、第 页共23页第 页共23页3.4坏上有k个端（3WkWn）,此k个端的选择方式有C：种：对J：某固定的k端來说，考虑可以生成的坏，任指定一个端，卜个端的选取方法公有k-1种，再卜端的选法有k-2种，等等，注意，这样生成的坏可按两种试图顺序取得，故有种,总的环数为2董导k=3L某一固定边e确定了两个端，经过e的环数按其过余I、端进行分类，若环再过k个端（1WkWn-2）,有选法C：2种；对于某固定端來说，自然可以生成k!个环，从而总的环数两个固定端Z间的径按其经过端数分类，其中有一条不经过其他端的径,若经过k个端,（lWkWm2）,则对丁第一个端有（m2）种选择，第二个端有（m3）种选择，第k

2、个端有（n-k-1）种选择，共有(-2)!(-k_2)!总的径数为1+苧（2）!3.5试求图352中图的主树数目，并列举所有的主树。解:为图的端编号为vl,v2,v3,v4o取v3为参考点，有：-1-1S=_120=8-102所得主树见卜：v3vlv2v3v4vlv2vlv2v3v43.6试证明端数n人丁4的连接图都是非平而图，并求n=2,3,4的全连接图为对偶图。证明：设有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、为两端间通信的转接次数不超过2的最短树。解：P算法求解：伉仏，冬亠一伉，冬，叫伉，冬川3，%，冬，叫，叫K算法求解:按最小边长顺序取得：e12=幻=幻=即=咳=1此结果意味着最短树不唯一。V3第 页共23页原图有一个边长全为1的基本子图G“耍求转接次数小丁等丁2,若选取6的任何4个连续顶点，片V/+1v.+2叫+,作为基础,然后再按要求增加边,例如以叫v2v3卩为基础,增加v5v6,得到一个树长为7转接次数小J：等J：2的树T1,事实上，以任何4个连续顶点均可得到树长为7的转接次数小等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的最大流量&图中编上的数字是该边的容量。解：本题可以利用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,求最佳流彊分配，图中边旁的两个数字前者为容量，后者为费用。解：本题可以任选一个容量为6的可行流，然后采用负价坏法，但也可用贪心算法，从Vs出发的两条线路费用一样，但进入Vt的两条路径费用为7和2,故尽可能选用费用为2的线路，得卜图lo再考虑V0,进入V0的两条路径中优先满足费用为3的路径，得：图2,很容易得到最后一个流萤为fst=6的图3,边上的数字为流量安排。总的费用为=3x2+3x24-1x3+2x4+1x1+2x3+4x2+2x7=52

10、易用负价环验证图4的流起分配为最佳流4.1求WbM/m（n）中，等待时间w的概率密度函数。解：WM/m（n）的概率分布为：-iPo=1一0（7MQ）k0Po0k/n-lmkn假定nm,d$0,现在來计算概率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是二阶指数分布:/(/)=必何

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,求：稳定状态时系统的队列长度为k的概率应，顾客到达时队列的长度为k的概率顾客离去时队列的长度(V以及平均等待时间，并用G/G/1上界公式求出此时的平均等待时间，评论计算结果，并讨论aWb的情况。由J：是D/D/1问题，故子系统运行情况完全确定，第一个顾客到达后，系统无顾客，经到达离去到达此时有

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?,服务率“，系统稳定4.8在优先级别队列中

14、，A队为优先级，不拒绝，B队为非优先级，只准一人排队等待(不计在服务中的)，且当A队无人时才能被服务，求各状态概率，A队的平均等待时间和E队的拒绝概率。解：说明：0状态代表系统中无顾客状态；1，J状态代表系统中正在服务且A队中有1个顾客，B队列中有J个顾客排队的状态。状态转移图如右，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有一个三端网络,端点为v1?v2,v3,边为勺（忖2）及冬（叫*3），V1到v3的业务由v2转接，设所有的端Z间的业务到达率为入，线路的服务率为卩的M/M/1问题，当采用即时拒绝的方式时，求：1）各个端的业务呼损。2）网络的总通过量。3）线路的利用率。解：令：00表示el,e2均空闲。10表示el忙,e2闲（即el由vl,v2间业务占用）。01表示el闲，e2忙（即e2由v2,v3间业务占用）。11表示el,e2均忙，且分别由vlv2,v2v3间业务占用。表示el,e2均忙，且由vl,状态转移图如右：当人2=兄卩=入

18、3=2时有下列关系：PP,=也。3/tp00=/（p01+p10+A）（2+“）门0=勿。+如U+/）p01=2p00+/11询间业务占用。呼损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上题中的网若用J：传送数据包，到达率仍为九每秒，平均包长为b比特，边的容磧为c比特/秒，采用

19、不拒绝的方式，并设各端的存储容量足够人，求：1）稳定条件。2）网络的平均时延。3）总的通过量。4）线路的平均利用率。解：这是一个无损但有时延的系统。两条线路上到达率为：2入，而服务率为：c/b的M/M/1系统。1）稳定条件为：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。当一个元件失效据使得系统失效的情况卜，已知系统的平均寿命将卜降至T/n,如果采取容错措施，当m个以上元件失效“1才使系统失效，求证此系统的平均寿命为：几=T=可见比未采取措施前提高至少m倍。当m=n.l时，这一系统实际上即是D个元件的并接系统，试证上式即转化成并连系统的寿命公式。证：以1状态代表有1个元件失效的状态，此时系统的状态转移框图如卜：n一i第 #页共23页(1-P)第9页共23页第 #页共23页(1-P)第9页共23页从而系统的平均寿命为：5=S0+51+Sn,=TMni911当m=n-

21、l时S=T三k=0k而利用数学归纳法易知:當（七扣第 页共23页(1-P)第9页共23页5.2有n个不可修复系统，它们的平均寿命都是T。先取两个作为并接，即互为热备份运行;当有一个损坏时，启用第三个作为热备份：再损坏一个是起用第四个，已知卜去，直到n个系统均损坏。忽略起用冷备份期间另一系统损坏的可能性：试计算这样运行I、的平均寿命:并与全冷备份和全热备份是的平均寿命相比较。解：状态图如卜：1表示有1个系统损坏，失效在图中标出。从而，平均寿命:S=So+S1+-+S,i_1=Ix(/7-1)+T=1ts*=nT尸卜出+ks热S冷5.3上题目中n个子系统都是可修复系统，可靠度都是R。仍用上述方式运

22、行，一损坏系统修复后作为最后一个系统排队等候再起用，求稳态可靠度。解：m,mm表示n个系统中有m个失效，状态转移图及失效率与修复率如图：第 #页共23页(1-P)第9页共23页第 #页共23页(1-P)第9页共23页用Pm表示状态的概率(稳态)，状态方程如卜：2込=肌(2q+mp)pm=2叽7+(w+1)朋”+】Qmn-1(2a+0)几_=2ap“7+i叽叽t=询”A=11=0解状态方程如卜：有：pm=Pa0m05.5有一个故障率为67的系统，为了考虑是否使Z成为可修复系统而配备维修力駁，分别计算两类可靠度，试证明作为不可修复系统在时间T以内的可靠度人J：作为可修复系统的稳态可靠度的条件是：J

23、3TctT+pr0.01+0T第 #页共23页(1-P)第9页共23页第 页共23页(1-P)第9页共23页/JT0.9955.6有一故障率为a,修复率为的系统0,己知此系统的费用是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)中的二分网的联接度Q和结合度0,只考虑端故障，且各端的可靠度均为R，求1端和亍端间的联接概率。1；2；3冲中有三个失效时1；2；3；4中有三个无失效时解：图5-9(b)中的二分图，任意一端度数均为4,5=4容易知道：a=0=5=4一知考虑端故障，故中有一，二,三失效和无失效是等价图入右：可靠度分别为：l-(l-/?)3Cj/?(1-/?)31和5，Z间联接概率为：他5，=时尺(1_町1_(1_町+.用(1_町+.用(1_尺)+.疋1_(1_町5.8有一网络结构如图:验证网络是否为保证网。求联接度G和结合度0。若每边的可靠度都是Re,每端的可靠度Rn,求线路故障卜网络的