(完整word版)通信网理论作业及答案0001

1、3.4 1. 环上有k个端（3w kw n）,此k个端的选择方式有 Ck种；对于某固定的k端来说，考 虑可以生成的环，任指定一个端，下个端的选取方法共有 种，等等，注意，这样生成的环可按两种试图顺序取得，故有 k-1种，再下端的选法有 k-2 （k 种，总的环数为 2 2. 3. ；Ck (k -1)! _ Cn小 k J2 某一固定边e确定了两个端，经过e的环数按其过余下端进行分类，若环再过k个端（1 w kwn-2）,有选法C：工种；对于某固定端来说，自然可以生成 k!个环，从而总的环数 两个固定端之间的径按其经过端数分类，其中有一条不经过其他端的径，若经过k个端， （1w k w n-2

2、）,则对于第一个端有（n-2）种选择，第二个端有（n-3）种选择，第k个 端有（n-k-1 ）种选择，共有 3 型，总的径数为1型一 （n k 2）!心（n k 2）! 3.5试求图3-52中图的主树数目 并列举所有的主树。 图 3-52 解：为图的端点编号为v1,v2,v3,v4。 取v3为参考点，有： 3-1-1 S = -120=8 -102 所得主树如下： vl vlv2 3.11求下图中V到Vt的最大流量fst,图中编上的数字是该边的容量。 Vt 32) 解： 本题可以利用M算法，也可以使用最大流-最小割简单计算可知: X = *vs ,v3, V4 匚 C X,X =3 513=1

3、2 可知：最大流为12,可以安排为fsi= 3, , fs2 =5 ,f21=1 ,f2t= 4,fit=4 ,fs3=1,fs4=3,f3t=1 , f4t=3 o 3.13图3.55中的Vs和Vt间要求有总流量fst= 6,求最佳流量分配，图中边旁的两个数字 前者为容量，后者为费用。 解： 本题可以任选一个容量为6的可行流，然后采用负价环法，但也可用贪心算法，从Vs 出发的两条线路费用一样，但进入Vt的两条路径费用为 7和2，故尽可能选用费用为 2的 线路，得下图1 o r 6,3 Vs 23 11 再考虑V0 ,进入V0的两条路径中优先满 足费用为3的路径，得：图2，很容易得到 最后一个

4、流量为fst=6的图3，边上的数字 V为流量安排。总的费用为 L=32+3汇2+1汇3 + 2汇4+1汇1 + 23 + 4 汇 2+2沢7 = 52 3,4 易用负价环验证图4的流量分配为最佳流 量分配。 图2 4.3 试证M | M | m（n）中的列德尔公式也成立 证明: n -1 k _ m 1 f Pk k =m n 、Pk k =0 2 k - m 1 =Z k =m mH ?kPo 二 k 心m =Z k =ok! Po n J m k zm m! ?kPo r. nJ A . k -m m，k“ -mk J _k z m1 & m 1 mkPo m! k! Po n-1m +

5、Z PkPo km m! k =m m! k z=o k! m -1 =z mk 1 Po n J + z k m m k 1 | k =o k! k m! m -1 mk n m m 、 k k Po + z k Po k =o k! k刃 m! Po n n .1 二 k m -m 1 k dPo n d m 、 m m 5 m! k1Po m 又 k =亠 kR k ?kF0 k=ok! k=mm! m4 m -有列德尔公式 k = - S成立，证毕。 4.10有一个三端网络，端点为V1,V2, V3 ,边为0（V1,V2）及e2（V2,V3）, v1到v3的业务由 v2转接，设所有的端

6、之间的业务到达率为，线路的服务率为 邛勺A.V .问题，当采用即时 拒绝的方式时，求： 1）各个端的业务呼损。 2）网络的总通过量。 解: 3）线路的利用率。 令：00表示e1,e2均空闲。 10表示el忙,e2闲（即el由v1,v2间业务占用） 01表示el闲,e2忙（即e2由v2,v3间业务占用） 11表示e1,e2均忙，且分别由 v1v2,v2v3 间业务占用。 表示e1,e2均忙，且由v1，v3间业务占用。 状态转移图如右: 有下列关系： APt =Poo 3冷0 = % P01 + P10 + A ) “(几 + 4 )Pw =丸P00 + 和1 (丸 + A P01 =入P00 *

7、 pi1 、_2卩卩11 =九(P01 + P10 ) P* = P01 = P10 J P11 = p2 P00 这里 呼损 P13 =1 - P00 而 P23 - P12 =1 - P00 - P01 通过量T (1 - P12)(1 - P13) ：(1 - P23) 线路利用率 P*P11 (P10 P01)/2 2” 亠!.= 2 13尸亠T2 54 一个复杂系统有n级梯形结构组成如图所示。其中有n个子系统作为桥，2（n+1）个子系 统作为梯边，它们都是可靠度为R的可以修复系统。求这个复杂系统的可靠度递推公式， 假定所有子系统都互相独立。 解： 依次考虑1, 2, 3,n。依照各个

8、桥的情况可以分类，根据1, 2, 3,n的好坏情 况可以得到以下结果： 情况 概率 可靠度 I R 2 1-(1-R) 2Rn-1 n R(1-R) 1-(1-R 2)2Rn-2 出 R(1-R)2 3 2 1-(1-R ) Rn-3 1 1 1 N R(1-R)n-1 1-(1-R n)2Ro N+1 (1-R)n .,.n+ 2 1-(1-R) Rn 二R2R-R2 Rn 二 R1-R 2R2 - R4 + R(1 R_R2n R0 +(1 _ R y(2Rn申 _ R2n42 ) 2 其中：R0=2RR n_0 5.8有一网络结构如图: 1. 验证网络是否为保证网。 2. 求联接度:和结

9、合度1。 3. 4. 若每边的可靠度都是 Re，每端的可靠度 Rn,求线路故障下网络的可靠度和局故障 的网络的可靠度。 求V1和v2间联接的概率。 5. 要使和：都为2,如何添加一条边来 满足。 解: 1. 原网收缩为: 从而是保证图。 2. 去掉U1,U2可使网中断，故:-=1,: =2。 局故障下网的可靠度: 端的不可靠度为 Fn=1- Rn n =1 八 CiFRn i d n 网络的可靠度 艮=1 - a CjF,(1 -Fn)n_i i =GL 当 Fn 氷1R1M-C.F-2Fn 边故障下： 边的不可靠度为 Fe=1_Re : mm 网的可靠度 R2=_7 BjFet _Fe)m_L