通信网理论基础(修订版)习题解答

2.2 求 M/M/m（n）中，等待时间 w的概率密度函数。 解： M/M/m（n）的概率分布为： 11 0 1 00 1 1 ! )( ! )( −− = −− ⎥⎦ ⎤⎢⎣ ⎡ − −+= ∑m r mnmk m mp k mp ρ ρρρ ⎪⎪⎩ ⎪⎪⎨ ⎧ > ≤≤ −≤≤ = nk nkmp k m mkp k m p km k k 0 ! 10 ! )( 0 0 ρ ρ 假定 n>m，n≥0，现在来计算概率 P{w>x}，既等待时间大于 x的概率。 j jj xwPpxwP 0 }{}{ 其中，Pj{w>x}的概率为： ∑ = >•=> n njmxwP njm i xmexwP mjxwP j mj i i xm j j ≤≤=> −≤≤⋅=> −≤≤=> 0}{ ∑− = − 1}{ 1 ! )(}{ 10 0 µµ 可得： xm m n nimmn i i xm m n mj n mj i i xmj m n n mj mj i i xm j e m mPxwP则若n P i xmeP m m i xmeP m m P i xmePxwP )(0 1 0 0 1 0 0 1 0 ! )( 1 }{ 1! )( ! ! )( ! ! )(}{ λµ µ µ µ ρ ρ ρ ρρµ ρµρ µ −− +−− = − − = − = − − = − = − ⋅−=>∞→ +− −⋅= ⎥⎦ ⎤⎢⎣ ⎡ +⋅⋅= +⋅⋅=> ∑ ∑ ∑ ∑ ∑ 特别的，新到顾客需等待的概率为： ! )( mP mρ 1 }0{ 0 m WP ρ ⋅−=> ] )!1( )( )!1( )( ! )()([ )1(! )(而 1 2 0 1 0 −−− −−−−−= −− −− = −− − ∑ mn mm mn xm i xme m Pm xf mn n mn i mn m i mxm m w µλµρ λµρλλµρρ µ 第 1 页 共 26 页 n m k k xmm m w PwPPwP注： em m Pm xf在n =∞=== −−=∞→ ∑− = −− }{}0{ )( )1(! )( 1 0 )(0 λµλµρρ 2.4 求M/D/1 排队问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 中等待时间W的一、二、三阶矩m1、m2、m3，D 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示服务时间为定值 b，到达率为λ。 解： )( )1()( SBs ssG λλ ρ +− −= 其中 sbst edtebtsB −∞ − =−= ∫0 )()( δ 从而 sbes ssG −+− −= λλ ρ )1()( 又 ∑∞ = = 0 )( i i i sgsG )1( ! )( 00 ρλλ −=⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛ −⋅+−⎟⎠ ⎞⎜⎝ ⎛∴ ∑∑ ∞ = ∞ = s j sbssg j j i i i b g λ ρ − −= 1 1 0 2 2 1 )1(2 )1( b bg λ ρλ − −−= 3 423 2 )1(12 )2)(1( b bbg λ λλρ − +−= 3 4 33 2 3 22 2 11 4 4 3 )1(4 )21(6)0( )1(6 )2(2)0( )1(2 )0( )( )1(24 )1)(21( ρ λρ ρ λρ ρ λ ρλλ λρλ − +=×=′′′−= − +=×=′′= −=−=′−= =− −+−= bgGm bgGm bgGm b b bbg L 2.5 求 M/B/1，B/M/1 和 B/B/1 排队问题的平均等待时间W ，其中 B 是二阶指数分布： 100,)1()( 2121 21 <<>−+= −− αλλλααλ λλ tt eetf 解：M/B/1 ( )[ ] 2 2 1 2 21 2 2 2 1 2 2 2 12 21 12 2 2 1 2 21 1 2 2 1 1 0 )1( 1 )1( 1)1(22)0(1)0( )1( )()( λλλαλαλλλλ αλλαλ ρ λ λ α λ αλλρλ α λ α λ α λ α λ λα λ αλ −−− +−=−= ⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛ −+==−+=′′=−+=′−= + −++== ∫ ∞ − m w wBwBw ss dtetfSB st 第 2 页 共 26 页 B/M/1 )))(21(2)(11( ))(21(2)(11 )1( 2 ))(21(2)(11 10 )1( )( 21 2 2121 21 2 2121 21 2 2121 2 2 1 1 2 2 1 1 ρραρρρρµ ρραρρρρ σµ σ ρραρρρρσ α λµσµ λα λµσµ αλσ ρµλρµλµσµσ −−+−++−− −−+−+−++=−= −−+−+−++= << +− −++−= ==−= w 的根取 令B B/B/1 设到达的概率密度函数为 tt eetf 21 21 )1()( λλ λααλ −− −+= 设离去的概率密度函数为 tt eetf 43 43 )1()( λλ λααλ −− −+= 假设 423121 λλλλααα ==== ( )[ ] [ ] 21 2 2 22 1 22 21 2 2 2 1 21 2121' 0 21 21 0 2121 2121 422 2121 422 21 2 2 2 1 2 2 1 1 2 2 1 1 2 2 1 1 )1(2)2()1())1(( )()( )( ))(()( )( )()(lim ))(( )()( ))(( )()( ))()()(())()()(( )1( 1)1()1(1)()( )1()()( λλααλααλαλααλλλ λλ λλλλλλ λλ λλλλ λλλλλλλλ λααλλλ λ λα λ αλ λ λα λ αλ λ λα λ αλ −−−+−=−+−+= +−=−=+ ++= Φ== Φ= −− −=Φ++ +=Φ ++−− −=++−− −−+−+= −⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛ + −++⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛ − −+−=−− + −++== = + + → −+ t其中 t tsSw st ssksS s kswt s sk ss stss ss stss取 ssss sst ssss ss ssss sBsA ss sBsA sww s 2.6 在 D/D/1 排队问题中，顾客到达的时间间隔为 a，服务时间为 b，均为恒定值，且 a>b， 求：稳定状态时系统的队列长度为k的概率pk，顾客到达时队列的长度为k的概率vk，顾 客离去时队列的长度dk，以及平均等待时间，并用G/G/1 上界 公式 小学单位换算公式大全免费下载公式下载行测公式大全下载excel公式下载逻辑回归公式下载 求出此时的平均等待时间， 评论计算结果，并讨论a≤b的情况。 解： 由于是 D/D/1 问题，故子系统运行情况完全确定，第一个顾客到达后，系统无顾客， 第 3 页 共 26 页 经过 b后，服务完毕，顾客离去，再经过 a-b 后，下一个顾客到达。 此时有： ⎩⎨ ⎧ ≠ === ⎪⎩ ⎪⎨ ⎧ =− == 00 01 0)( 1 k k dr ka ba ka b p kk k 顾客不等待时 0=w G/G/1 上 界 公 式 00 )1(2 0)()()()( )1(2 22 22 22 =∴=− +≤∴ ==∴−=−=− +≤ w t w bttpap t w t t tr ρ σσ σσδτδτρ σσ τ τQ 当 aτ ，将造成呼损， t≤τ 时无呼损。 2 2 22 00 )2( 4)2()()( )()( µλ λµλττµλττ ττ µτλ + +=⋅=⋅= =∴ ∫∫∫∫ ∫ ∞ −∞ −∞∞ ∞ dtdeedtdbtap 则dbtp t t tc tc 2.8 在优先级别队列中，A 队为优先级，不拒绝，B 队为非优先级，只准一人排队等待（不 计在服务中的），且当A队无人时才能被服务，求各状态概率，A队的平均等待时间和 B队 的拒绝概率。 解： 0 0 0 0 1 1 11 0 λ1+λ2 λ2 λ2 µµ λ1 µµ λ1 µλ1 µλ1 说明： 0 状态代表系统中无顾客状态； i，j 状态代表系统中正在服务且 A 队中有 i 个顾客，B队列中有 j 个顾客排 队的状态。 状态转移图如右，A队到达率为 1λ ， B队到达率为 2λ ，服务率µ，系统稳定 时，应有 111 <= µλρ 可得到特征方程如下: 第 4 页 共 26 页 ⎪⎪ ⎪ ⎩ ⎪⎪ ⎪ ⎨ ⎧ >++=+ >+=++ +=+ +++=++ =+ +− +− 5 4 3 2 1 0)( 0)( )( )()()( )( 0,21,11,111,1 0,10,110,21 11002011 02110010021 00021 L L L L L iPPPP iPPP PPP PPPP PP iiii iii λµλλµ µλλλµ µλλµ λλµλλµ µλλ 由于 4 是差分方程，不妨设其通解为： 代入有： ii xpp 000 = 2 22211 10 0)1()1( 2121 2 2 2 121 0 121 21 00 1 0010021 ρρρρρρρρ ρρρρρρ ++−++−++=∴<< =+++−⇒+=++ +− xx xxxpxpxp iii Q 由于 5 是非齐次差分方程： 0)1( 0,21,111,11,1 =+++− −+ iiii ppppp ρρ 其特征根为： 1ρ=a 假设其通解为： 代入前式得： iii BxAp 011, += ρ 0)1( 0002 1 0101 1 0 =⋅+⋅+⋅+−⋅ −+ iiii xpxBxBxB ρρρ 解之，得： iii xpAppB 00011,00 −=−= ρQ 代入 3式得： ( ) 110020111 ppp +=+ ρρ 即： ( ) ( )[ ] ( )⎪⎩ ⎪⎨ ⎧ += = −−++= −++= 02100 000 1021001 02100 1 1 pp xpp xxpp xpA i i ii i ρρ ρρρ ρρ ， ， 由正则条件： ( ) ( ) ( )( ) ( )[ ] ( ) ( ) ( ) ( )21 02100 0 102100 0 10 021211 1 0 0 10210210 1 1 11111 11 1 11 ρµ ρρ ρρρµµ ρρρρρ ρ ρρρρρ − −++= −+++=++=∴ −++++− −=∴ =−++++ ∑∑ ∑ ∞ = ∞ = ∞ = xp xprpprw x p xpp r r r rrA i i ，， 第 5 页 共 26 页 ( )[ ] ( ) ( ) 0 00 1 02100 0 0102100 0 1 11 1 1 x pxp xxppP r rr r rCB −−− −++= −−++== ∑∑ ∞ = ∞ = ρ ρρ ρρρ， 2.9 排队系统中有三个队列,其到达率分别为 cba λλλ ,, 公用同一出线路，其中a类最优先， 即线路有空闲就发送；b类次之，即a无排队时 可以发送，c类最低，即a，b类均无排队时可 以发送，不计正在传送的业务，各个队列的截 至队长为na＝2，nb=1，nc＝0，试列出稳定状 态下的状态方程，并计算 cba λλλ == 时，各 状态的概率和三类呼叫的呼损。 0 0 0 1 0 0 2 0 0 0 1 0 1 1 0 2 1 0 0 λa+λb+λc µ λa µ λa µ λa µ λa µ µλb λb λb 解： r，s，k 分别表示 a，b，c 三队中等待的呼叫数，状态以（r，s，k）表示。 稳态方程： 210010100110 200110210 110000010 100200 000200100 0100010000 0000 )( )( )( )( )()()( )( pppp ppp ppp pp ppp pppp pp aba ba ba ab aba cbaba cba µλλµλ λλµ µλµλ λµλ λµµλλ λλλµµλλ µλλλ ++=+ += +=+ =+ +=++ ++++=++ =++ 归一条件 1,,0 =+ ∑ kjipp 若 cba λλλ == 令 µλρ a= 151427362712 122 122 12156 122 3 122 12156 122 33 122 12933 23456 2 0 02 654 21002 3 200 02 543 11002 32 100 02 432 0100000 ++++++ ++= ++ ++=++= ++ ++=++ += ++ ++== ρρρρρρ ρρ ρρ ρρρ ρρ ρ ρρ ρρρ ρρ ρρ ρρ ρρρρ p pppp pppp pppp C 类呼损为： L=−= 01 ppc B 类呼损为： 210110010 ppppB ++= 第 6 页 共 26 页 A类呼损为： 200210 pppA += 2.10 有一个三端网络，端点为 ，边为 )及 )，v1 到 v3 的业务由 v2 转接，设所有的端之间的业务到达率为 321 ,, vvv ,( 211 vve ,( 322 vve λ，线路的服务率为µ的M|M|1(1)问题，当采用 即时拒绝的方式时，求： 1) 各个端的业务呼损。 2) 网络的总通过量。 3) 线路的利用率。 解： 令：00 表示 e1,e2 均空闲。 10 表示 e1 忙,e2 闲（即 e1 由 v1,v2 间业务占用）。 01 表示 e1 闲,e2 忙（即 e2 由 v2,v3 间业务占用）。 11 表示 e1,e2 均忙，且分别由 v1v2,v2v3 间业务占用。 ★表示 e1,e2 均忙，且由 v1，v3 间业务占用。 状态转移图如右： 当 λλλλ === 231312 时 有下列关系: ( ) ( ) ( ) ( )⎪⎪ ⎪ ⎩ ⎪⎪ ⎪ ⎨ ⎧ += +=+ +=+ ++= = 100111 110001 110010 *100100 00 2 3 ppp ppp ppp pppp ppt 关于艾滋病ppt课件精益管理ppt下载地图下载ppt可编辑假如ppt教学课件下载triz基础知识ppt λµ µλµλ µλµλ µλ λµ 又 解之得: 1=∑ p 200 00 2 11 001001* 31 1 ρρρ ρ ++=⎩⎨ ⎧ = === p这里 pp pppp 呼损 2 2 0013 31 31 ρρ ρρ ++ +=−= pp 而 2 2 01001223 31 21 ρρ ρρ ++ +=−−== pppp 通过量 2 2 231312 31 23)1()1()1( ρρ ρρρρρ ++ +=−+−+−= pppT 线路利用率 2 2 011011* 31 22/)( ρρ ρρη ++ +=+++= pppp 2.11 上题中的网若用于传送数据包,到达率仍为　每秒　平均包长为 b 比特,边的容量为 c比特/秒,采用不拒绝的方式,并设各端的存储容量足够大,求: (1)稳定条件。 (2)网络的平均时延。 (3)总的通过量。 ★ 0 0 0 1 1 11 0 λ13 λ23 λ23 µµ λ12 µµ λ12 µ λ23 第 7 页 共 26 页 (4)线路的平均利用率。 解：这是一个无损但有时延的系统。 两条线路上到达率为：2　，而服务率为：c/b 的 M/M/1 系统。 (1)稳定条件为： 2　b/c<1。 (2)网络的平均时延： 对 v1v2 和 v2v3 间的业务： λρµ 2 1 )1( 1 1 −=−= bc w 对 v1v3 间的业务： λ2 22 12 −== bc ww (3)系统稳定时，总的通过量为：3　b/c。 (4)线路的平均利用率　=　=2　b/c。 一般来说，通过率与利用率均有增加，这是以稳定性和时延为代价换来的。 2.12 在分组交换系统中，设信息包以泊松率到达，平均到达率为　，但信息包的长度为固定 b 比特，信道容量为 c 比特/秒。由于端内存储量的限制，设除了在传送的包外，只允许有 两个信息包等待传送，试： (1)列出关于dr(顾客离去时的队长)的系统方程 (2)解出个dr. (3)求平均时延。 (4)求信息包被拒绝的概率。 解： ⎪⎪ ⎪ ⎩ ⎪⎪ ⎪ ⎨ ⎧ = −+++= +++= ++= += ∑ = 1 1 3 0 032231303 031221202 0211101 01000 i id pdqdqdqdd pdqdqdqdd qdqdqdd qdqdd ）（ 其中 p0 是第 4个顾客被拒绝离去之后，第 3个顾客的残余寿命中无顾客到达的概率。 这里到达是随机的，可知： b cedte b cp c btcb λ λλ ⎟⎠ ⎞⎜⎝ ⎛ −=⋅= −−∫ 1/00 设 ρλ =cb 则 ( ) ( ) ( ) ( ) ( ) ( )[ ] 0220 0 0 1 2 0 2 2 1 000 1 1 22 deedd q q d edbeq edbeq edc bedbeq b ρρ ρλτ ρλτ ρλτλτ ρ ρττλτ ρττλτ ττδττ +−=−=∴ == == =−== −∞ − −∞ − −∞ −∞ − ∫ ∫ ∫∫ 第 8 页 共 26 页 ( ) ( ) ( ) ( ) ( ) ρρρ ρ ρ ρρρ ρρρρρ ρρρρ eee edd e deee d i 2 42211 11 1 2 221 2 223 0 0 2 23 3 ++++−+ −== − ⎥⎦ ⎤⎢⎣ ⎡ +++− = ∑Q 平均时延： 0 2 21 1 1 1 2 1 2 32 2 3 22 d c beec bdm m md m mcbws vv ⎥⎦ ⎤⎢⎣ ⎡ +⎟⎠ ⎞⎜⎝ ⎛ +−=+⎥⎦ ⎤⎢⎣ ⎡ ⎟⎟⎠ ⎞ ⎜⎜⎝ ⎛ ++=+= ρρ ρ 拒绝概率： 3dpC = 2.13 有四个端三条边组成的数据网，如图所示。端间的信息包分别为和每秒，信息包长度为 负指数分布，平均包长为k比特，各信道容量分别为c1，c2和c3，和一起排队，和一起排队， 和一起排队，均不拒绝，求 (1)各种业务的平均时延。 (2)网络的平均时延。 (3)各信道的平均利用率。 解: 由于均不拒绝且到达和离去均随机，故 3个 信道均等效于 3个M/M/1 系统，其中： C1：到达为 1312 λλ + 。服务为：c1/b C2：到达为 4212 λλ + 。服务为：c2/b C3：到达为 4313 λλ + 。服务为：c3/b C1 的平均迟延为 1312 111 1 )1( 1 λλρµ −− =− b c C1 的平均迟延为 4212 222 1 )1( 1 λλρµ −− =− b c C1 的平均迟延为 4313 333 1 )1( 1 λλρµ −− =− b c 第 9 页 共 26 页 4212 2 1312 1 2112 11 λλλλ −− + −− =+= b c b csss cc 4313 3 1312 1 3113 11 λλλλ −− + −− =+= b c b c sss cc 4313 1 343 4212 2 242 11 λλλλ −− == −− == b css b css cc 网络的平均时延为： 43421312 4343424213131212 λλλλ λλλλ +++ +++= sssss 各信道利用率为： ( ) ( ) ( ) 3431333 2421222 1131211 / / / cb cb cb c c c λλρη λλρη λλρη +== +== +== 2.14 总线上有 4 个用户 v1,v2,v3 和 v4，它们之间以 Alopha 方式互相通信，信包到达率均为 每秒，信息包的长度为 b比特；总线上的传输速率为 c比特/秒，试求通过率 r，并大致画出 r 与 b的曲线关系。 解：r 与 b 的曲线关系如右图，从直观上来看，这也是显然的。 总线上一个包的服务时间 cb=τ 秒， 总的呼叫量为： cba λ12= ， 通过量为： aear 2−⋅= 通过率： ae c b rr 212 −== λ 3.2 设在一个纯 ALOHA 系统中，分组长度 20=τ ms，总业务到达率 10=tλ pkt/s， 试求一个消息成功传输的概率。若为 S-ALOHA系统，试求这时消息成功传输的概率，并求 一个消息分组传输时和另一个分组碰撞的概率。 解：由题意， 20=τ ms， 10=tλ pkt/s，则系统的总业务量为 2.0102010 3 =××== −τλtP 纯 ALOHA系统吞吐量满足 ，一个消息成功传输的概率为 PPp 2e−= 67.0eee 4.02.022 ===== −×−− Ps PpP 第 10 页 共 26 页 S-ALOHA系统的吞吐量满足 ，这时消息成功传输的概率为 PPp −= e 82.0ee 2.0 ≈=== −−Ps PpP 一个消息分组传输时和另一个分组碰撞的概率为： 18.082.011 =−=− sP 。 3.3 设在一个 S-ALOHA 系统中每秒共发送 120 次，其中包括原始发送和重发。每次 发送需占用一个 12.5 ms 的时隙。试问： （1） 系统的归一化总业务量等于多少？ （2） 第一次发送就成功的概率等于多少？ （3） 在一次成功发送前，刚好有两次碰撞的概率等于多少？ 解：由题意， tλ =120 次/秒， τ =12.5 ms。 （1） 。 5.1105.12120 3 =××== −τλtP （2） 。 ( ) 223.00 5.1 === −− eeP tτλ （3） 。 ( ) ( ) 135.0223.0223.011 223 =×−=−= −− PP eep 3.4 设一条长度为 10 km 的同轴电缆上，接有 1000 个站，信号在电缆上传输速度为 200 m/us，信号发送速率为 10 Mb/s，分组长度为 5000 b。试问： （1） 若用纯ALOHA系统，每个站最大可能发送分组速率等于多少？ （2） 若用 CSMA/CD系统，每个站最大可能发送分组速率等于多少？ 解：（1）纯 ALOHA中，发送分组不用等待。理想情况下，各站一个接一个发送分组， 互不干扰，发送分组的最大速率为 ( ) 210005000/10 =×M pkt/s （2）对于 CSMA/CD系统，信号传输速率为 200 m/s，对于 10 km 电缆，单程传播时间 为 s 50200/1010 3 µ=×=t CSMA/CD系统发送一个分组必须等待的时间为：2t=100 us=0.1 ms。 故每个站的最大可能发送分组速率为： pkt/s 0.2ms/5000 1.010 =×M 。 4.4 有一个 n端的全连接图。试证： （1）无重复端的环数为 ( )∑ = −n k k n kC 3 2 !1 （2）经过某一固定边 e的环数为∑ = − n k k nCk 3 2! 第 11 页 共 26 页 （3）两个固定端之间的径数位 ( )( )∑ − = −− −+ 2 1 !2 !21 n k kn n (1)环上有 k个端（3≤k≤n），此 k个端的选择方式有 种；对于某固定的 k端来说，考虑 可以生成的环，任指定一个端，下个端的选取方法公有 k-1 种，再下端的选法有 k-2 种，等 等，注意，这样生成的环可按两种试图顺序取得，故有 k nC 2 )!1( −k 种，总的环数为∑ = −n k k n kC 3 2 )!1( (2)某一固定边 e 确定了两个端，经过 e 的环数按其过余下端进行分类，若环再过 k 个端 （1≤k≤n-2），有选法 种；对于某固定端来说，自然可以生成 k!个环，从而总的环数为 个。 k nC 2− ∑ = − n k k n kC 3 2 ! (3)两个固定端之间的径按其经过端数分类，其中有一条不经过其他端的径，若经过 k 个 端，（1≤k≤n-2），则对于第一个端有（n-2）种选择，第二个端有（n-3）种选择，第 k个端 有（n-k-1）种选择，共有 )!2( )!2( −− − kn n 总的径数为 ∑− = −− −+ 2 1 )!2( )!2(1 n k kn n 4.5 试求图 4-44 中图的主树数目，并列举所有的主树。 解：为图的端编号为 v1,v2,v3,v4。 取 v3 为参考点，有： 8 201 021 113 = − − −− =S 所得主树见下: 图 4-44 第 12 页 共 26 页 4.6 试 证明 住所证明下载场所使用证明下载诊断证明下载住所证明下载爱问住所证明下载爱问 端数 n大于 4的连接图都是非平面图，并求 n=2，3，4 的全连接图为对偶图。 证明：设有n个端的全联接图为Kn因为K5是非平面图，而当n>5 时K5是Kn的子图，从而Kn （n>5）均不是平面图。一下是对偶图（注意K4为自对偶图）。 4.7 已知一个图的邻接矩阵如左，画出此图，并求各 端之间的最小有向径长。 解：首先作出图形： ⎥⎥ ⎥⎥ ⎦ ⎤ ⎢⎢ ⎢⎢ ⎣ ⎡ = 0000 1000 0100 1010 C 对所绘制图形的端点进行编号，得邻接矩阵。 ⎥⎥ ⎥⎥ ⎦ ⎤ ⎢⎢ ⎢⎢ ⎣ ⎡ = 0000 1000 0100 0101 4321 vvvv C 第 13 页 共 26 页 经计算： ⎥⎥ ⎥⎥ ⎦ ⎤ ⎢⎢ ⎢⎢ ⎣ ⎡ = 0000 0000 1000 0100 2C ⎥⎥ ⎥⎥ ⎦ ⎤ ⎢⎢ ⎢⎢ ⎣ ⎡ = 0000 0000 0000 1000 3C 因而有 1),( 21 =vvd 2),( 1vd 3 =v 1),( 41 =vvd 1),( 32 =vvd 2),( 42 =vvd 1),( 43 =vvd 其余有向径长均为 ∞，或不存在。 4.8 图有六个端，其无向距离矩阵如下： ⎥⎥ ⎥⎥ ⎥⎥ ⎥ ⎦ ⎤ ⎢⎢ ⎢⎢ ⎢⎢ ⎢ ⎣ ⎡ 021321 101232 210123 321012 232101 123210 6 5 4 3 2 1 654321 v v v v v v vvvvvv 解： (1)P 算法求解： { } { } { } { } { } { }456321 563216321321211 ,,,,, ,,,,,,,,,, 34 65162312 vvvvvv vvvvvvvvvvvvvvv e eeee ⎯→⎯ ⎯→⎯⎯→⎯⎯→⎯⎯→⎯ (2)K 算法求解： 按最小边长顺序取得： 15645342312 ===== eeeee 此结果意味着最短树不唯一。 用 P 算法，求出最短树。 用 K算法，求出最短树。 限制条件为两端间通信的转接次数不超过2的最 短树。 第 14 页 共 26 页 (3)原图有一个边长全为 1的基本子图G1，要求转接次数小于等于 2，若选取G1的任何 4个连 续顶点， ,作为基础，然后再按要求增加边，例如以 为基础，增加 ，得到一个树长为 7转接次数小于等于 2的树T1，事实上，以任何 4个连续顶点均可 得到树长为 7的转接次数小于等于 2的树 iv 1+iv 2+iv 3+iv 1v 2v 3v 4v 5v 6v 4.9 图有六个端，端点之间的有向距离矩阵如下： ⎥⎥ ⎥⎥ ⎥⎥ ⎥ ⎦ ⎤ ⎢⎢ ⎢⎢ ⎢⎢ ⎢ ⎣ ⎡ ∞∞ ∞ ∞∞ ∞∞∞ ∞∞ ∞∞ 0227 50826 7205 102 7401 3190 6 5 4 3 2 1 654321 v v v v v v vvvvvv 解： (1)D 算法 (1)用 D算法求 V1 到所有其他端的最短径长及其路径。 (2)用 F 算法求最短径矩阵和路由矩阵，并找到 V2 至 V4 和 V1 至 V5 的最短径长及路由。 (3)求图的中心和中点。 V1 V2 V3 V4 V5 V6 指定 最短径长 0 ∞ ∞ ∞ ∞ ∞ V1 W1＝0 9 1 3 ∞ ∞ V3 W13＝0 9 3 2 ∞ V5 W15＝0 8 3 7 V4 W14＝0 8 7 V3 W16＝0 8 V2 W12＝0 (2)F 算法 最短路径矩阵及最短路由阵为W5，R5 有向距离为 4 412 vvv →→ 有向距离为 2 531 vvv →→ 第 15 页 共 26 页 ⎥⎥ ⎥⎥ ⎥⎥ ⎥ ⎦ ⎤ ⎢⎢ ⎢⎢ ⎢⎢ ⎢ ⎣ ⎡ ⎥⎥ ⎥⎥ ⎥⎥ ⎥ ⎦ ⎤ ⎢⎢ ⎢⎢ ⎢⎢ ⎢ ⎣ ⎡ ⎥⎥ ⎥⎥ ⎥⎥ ⎥ ⎦ ⎤ ⎢⎢ ⎢⎢ ⎢⎢ ⎢ ⎣ ⎡ ⎥⎥ ⎥⎥ ⎥⎥ ⎥ ⎦ ⎤ ⎢⎢ ⎢⎢ ⎢⎢ ⎢ ⎣ ⎡ ⎥⎥ ⎥⎥ ⎥⎥ ⎥ ⎦ ⎤ ⎢⎢ ⎢⎢ ⎢⎢ ⎢ ⎣ ⎡ ⎥⎥ ⎥⎥ ⎥⎥ ⎥ ⎦ ⎤ ⎢⎢ ⎢⎢ ⎢⎢ ⎢ ⎣ ⎡ ∞ ∞ ∞ ⎥⎥ ⎥⎥ ⎥⎥ ⎥ ⎦ ⎤ ⎢⎢ ⎢⎢ ⎢⎢ ⎢ ⎣ ⎡ ⎥⎥ ⎥⎥ ⎥⎥ ⎥ ⎦ ⎤ ⎢⎢ ⎢⎢ ⎢⎢ ⎢ ⎣ ⎡ ∞∞ ∞ ∞ ∞ ⎥⎥ ⎥⎥ ⎥⎥ ⎥ ⎦ ⎤ ⎢⎢ ⎢⎢ ⎢⎢ ⎢ ⎣ ⎡ ⎥⎥ ⎥⎥ ⎥⎥ ⎥ ⎦ ⎤ ⎢⎢ ⎢⎢ ⎢⎢ ⎢ ⎣ ⎡ ∞ ∞∞ ∞ ∞ ∞∞ ⎥⎥ ⎥⎥ ⎥⎥ ⎥ ⎦ ⎤ ⎢⎢ ⎢⎢ ⎢⎢ ⎢ ⎣ ⎡ ⎥⎥ ⎥⎥ ⎥⎥ ⎥ ⎦ ⎤ ⎢⎢ ⎢⎢ ⎢⎢ ⎢ ⎣ ⎡ ∞∞ ∞ ∞∞ ∞∞∞ ∞∞ ∞∞ 053353 603323 650555 551051 531101 534350 027284 507264 720486 615072 834201 723180 053313 603323 650333 451011 431101 434320 0272134 507264 7205167 12150112 1134201 1023190 053313 603323 650333 051011 031101 034320 0272134 508264 7205167 150112 34201 23190 051311 604322 650300 051011 051101 024320 02102167 508267 7205 150112 74201 163190 051311 604320 650300 051011 051101 004320 02102167 50826 7205 150112 74201 3190 054301 604320 650300 050001 050301 004320 0227 50826 7205 102 7401 3190 55 44 33 22 11 00 RW RW RW RW RW RW 第 16 页 共 26 页 (3) 中心为V)8,7,8,7,8,8(5 =ijj WMax 3或V5 ∑ = j ijW )23,24,27,21,18,21( 5 中心为V2 补充习题：试计算完全图Kn的主树的数目。 解：设 A为 Kn 的关联阵，那么主树的数目为： 21 1 0 0 00 111 1 0 01 11 11 1 1 001 11 1 11 11 −− =⋅= −− == − − − = −− − −− −− =⋅= nn T n n n n n n n dct n n dct n n dct n n n dctAAdctN OM OM LLL OM OM LLL OM OM M LL O O 证毕。 5.1 求下图中Vs到Vt的最大流量fst,图中编上的数字是该边的容量。 解： 本题可以利用 M 算法，也可以使用最大流－ 最小割简单计算可知： { }43 ,, vvvX s= { }tvvvX ,, 21= ( ) 123153, =+++=XXC 可知：最大流为12，可以安排为fs1 = 3,，fs2 =5，f12=1， f2t＝4，f1t=4，fs3=1，fs4=3，f3t=1，f4t=3。 5. 2 试移动上图中的一条边，保持其容量不变，是否能增大 fst？如果可以，求此时的最大值， 但若所有转接端 v1v2v3 和 v4 的转接容量限制在 4，则情况将如何？ 第 17 页 共 26 页 解： 依然按照最大流－最小割定理，若 能依一边从X找到 X 内部至割 ),( XX 中，自然可以增大流量，可以将e34移去， 改为：e41 或者e42均可，使总流量增至 12＋2＝14。 当 vi(i = 1,...4)的转接容量限制到 4时， 等效图为右图，对于 3.11 中的流量分 配，在本题限制下，若将 fs2 由 5 改为 4即得到一个流量为 11 的可行流。 但 若 { }2'44'33* ,,,, vvvvvvX S= ， { }tvvvvX ,,, '2'11* = 则 113431),( ** =+++=XXC ，换句话说就是 11 已是最大流。 5.3 图 5-12 中的Vs和Vt间要求有总流量fst＝6，求最佳流量分配，图中边旁的两个数字前者为 容量，后者为费用。 解： 本题可以任选一个容量为 6 的可行流，然后采用负价环法，但也可用贪心算法，从 Vs 出发的两条线路费用一样，但进入 Vt 的两条路径费用为 7 和 2，故尽可能选用费用为 2 的 线路，得下图 1。 再考虑 V0，进入 V0 的两条路径中优先满 足费用为 3的路径，得：图 2，很容易得到 最后一个流量为 fst=6 的图 3，边上的数字 为流量安排。总的费用为 52722432 1142312323 =×+×+×+ ×+×+×+×+×=L 易用负价环验证图 4的流量分配为最佳流 量分配。 3 5 6 4 6 2 3 1 4 4 4 4 2 2 2 v1 v1' v2 v3 v4 v2' v3' v4' Vs Vt 3,2 3,2 2,3 1 ,1 6,3 3,4 5,7 4,2 Vs Vt 图 1 3 4 2 4 Vt 2 2 2 4 3 3 2 1 1 2 2 4 Vs Vt Vs Vt 图 2 图 3 图 4 Vs 第 18 页 共 26 页 第 19 页 共 26 页 第 20 页 共 26 页 6.1 由 n 个元件构成的一个系统，各元件的平均寿命都是 T。当一个元件失效据使得系统失 效的情况下，已知系统的平均寿命将下降至 T/n，如果采取容错措施，当 m 个以上元件失 效才使系统失效，求证此系统的平均寿命为： ∑ = −= m r m rn TT 0 1 可见比未采取措施前提高至少m倍。当m=n-1 时，这一系统实际上即是 n个元件的并接系 统，试证上式即转化成并连系统的寿命公式。 证：以 i 状态代表有 i 个元件失效的状态，此时系统的状态转移框图如下： 那么状态 i 的平均寿命为： mi in TSi ≤≤−= 0 从而系统的平均寿命为： ∑ = −=+++= m i m in TSSSS 0 10 1L 当 m=n-1 时 ∑ = = n k k TS 0 1 而利用数学归纳法易知： nnnnnn n k C n CCC k 1)1( 3 1 2 11 321 0 −+−+−=∑ = L 6.3 有 n 个不可修复系统，它们的平均寿命都是 T。先取两个作为并接，即互为热备份运行； 当有一个损坏时，启用第三个作为热备份；再损坏一个是起用第四个，已知下去，直到 n 个系统均损坏。忽略起用冷备份期间另一系统损坏的可能性；试计算这样运行下的平均寿命； 并与全冷备份和全热备份是的平均寿命相比较。 解：状态图如下：i 表示有 i 个系统损坏，失效在图中标出。 由上图有： TSniTS ni =−≤≤= −1202 从而，平均寿命： ( ) 冷热 热冷 n SSS T n ＝SnTS TnTnTSSSS << ⎟⎠ ⎞⎜⎝ ⎛ ++++= +=+−×=+++= − 1 3 1 2 11 2 11 2110 L L 0 1 2 m F… 0 1 2 n-1 n 2α 2α α2α 2α ⋯ 第 21 页 共 26 页 6.4 上题目中 n 个子系统都是可修复系统，可靠度都是 R。仍用上述方式运行，一损坏系统 修复后作为最后一个系统排队等候再起用，求稳态可靠度。 解： m，n-m 表示 n个系统中有m个失效，状态转移图及失效率与修复率如图： 用 Pm表示状态m,n-m 的概率（稳态），状态方程如下： ⎪⎪ ⎪⎪ ⎪ ⎩ ⎪⎪ ⎪⎪ ⎪ ⎨ ⎧ = = +=+ −<<++=+ = ∑ = − −− +− 1 2)2( 10)1(2)2( 2 0 1 21 11 10 n i i nn nnn mmm p pnp pnppn nmpmppm pp βα βαβα βαβα βα M M 解状态方程如下：有： ( ) ( ) ⎪⎪⎩ ⎪⎪⎨ ⎧ = <≤= 0 0 2 2 02 p n p nmp m p n n n m m m β α β α ！ ！ 由归一性： 1 1 0 1 0 221 − − = − ⎥⎥⎦ ⎤ ⎢⎢⎣ ⎡ +⎟⎟⎠ ⎞⎜⎜⎝ ⎛= ∑n m n nnm nm p β α β α ！！ 稳态可靠度： ∑ ∑ − +⎟⎟⎠ ⎞⎜⎜⎝ ⎛ ⎟⎟⎠ ⎞⎜⎜⎝ ⎛ =−= n nnm m ns nm m pR β α β α β α ！！ ！ 1221 21 1 其中， R R−= 1β α R 是单一系统的可靠度。 6.5 一个复杂系统有 n 级梯形结构组成如图所示。其中有 n 个子系统作为桥，2(n+1)个子系 解： 统作为梯边，它们都是可靠度为 R 的可以修复系统。求这个复杂系统的可靠度递推公式， 假定所有子系统都互相独立。 0, n 1, n-1 2, n-2 m,n-m n-1, 1 n, 0 2α 2α 2α α2α2α 2α β 2β (m+1)β nβ(n-1)β3β mβ 第 22 页 共 26 页 依次考虑 1，2，3，⋯ n。依照各个桥的情况可以分类，根据 1，2，3，⋯ n 的好坏情 情况 概率 可靠度 况可以得到以下结果： Ⅰ R [1-(1-R)2]Rn-1 Ⅱ R(1-R) [1-(1-R2)2]Rn-2 Ⅲ R(1-R)2 [1-(1-R3)2]Rn-3 ┇ N R(1-R)n-1 [1-(1- )2]R0Rn N+1 (1-R)n 1-(1-Rn+1)2 ( ) ( )( ) ( ) ( ) ( ) ( )221021 2 42 1 2 2121 212 ++− −− −−+−−+ +−−+−=∴ nnnnnn nnn RRRRRRRR RRRRRRRRRR L 其中： 有一个故障率为 2 0 2 RRR −= 0≥n 6.6 α 的系统，为了考虑是否使之成为可修复系统而配备维修力量，分别计 算两类可靠度，试证明作为不可修复系统在时间 T 以内的可靠度大于作为可修复系统的稳 态可靠度的条件是： 01.0995.0 =< TT αβ 解：故障率为的不可修复系统在 T（ 01.0=Tα ）内的可靠度为： 01.0)( −− == eeTR Tα α β 的可修复系统的稳定可靠度为 βα α + 现： >)(TR βα α + 或 > 01.0−e T T TT T β α βα α +=+ 01.0 995.0<∴ Tβ 6.7 有一故障率为α ，修复率为的系统 β ，已知此系统的费用是 小费用。 sr BAC βα += − 其中 A，B，r，s 为已知的非负常量，求可靠度为 0.99 时的最 解： 1999999.0 −⋅⋅+==∴=+ ss r sB AC αααββα αQ 令： 0=αd dc 有 srsssr Bs rAsBA +− ⎟⎠ ⎞⎜⎝ ⎛ ⋅=∴=⋅⋅+− 1 1 99 099 ααα ssr s s sr r s Bs rAB Bs rAAC 99 9999min ++ − ⎟⎠ ⎞⎜⎝ ⎛ ⋅+⎟⎠ ⎞⎜⎝ ⎛ ⋅= 第 23 页 共 26 页 .8 用流量法求图 5－9(b)中的二分网的联接度6 α 和结合度 β ，只考虑端故障，且各端的可靠 均为 R，求 1端和 5'端间的联接概率。 度 解：图 5－9(b)中的二分图，任意一端 度数均为 4， 4=δ 容易知道： 4=== δβα 一知考虑端故障，故中有一，二， 三失效和无失效是等价图入右： 可靠度分别为： ( )[ ] ( )313 111 RRCR −⋅⋅−− ( ) 4411 CR−−[ ] ( ) ( ){ }4443342224 11 RCRRCRR ⋅+−⋅+−⋅ 1 和 5'之间联接概率为： ( ) ( )[ ] ( ) ( ){ } ( )[ ]444433422243314'5,1 1111111 RRCRRCRRCRRRCR −−⋅⋅+−⋅+−⋅+−−−⋅= 1. 验证网络是否为保证网。 2. 6.9 有一网络结构如图： 求联接度α 和结合度 β 。 每端的可靠度 Rn,求线路 络的 和局 网络的 可靠度。 5. 3. 若每边的可靠度都是 Re， 故障下网 可靠度 故障的 4. 求v1和v2间联接的概率。 要使α 和 β 都为 2，如何添加一条边来 满足。 解： 从而是保证图。 2. 去掉U1,U2 可使网中断，故 1. 原网收缩为： α =1, β =2。 3. 网的可靠度： 端的 局故障下 不可靠度为 nn RF −= 1 第 24 页 共 26 页 网络的可靠度 i in n i ni RFCFFC 1 1)1( α FFCR 2111 −=−≈ αα 边故障下： 不可靠度为 ∑∑ = − = − −=−−= n i in n i ni n R1 1 当 nF 1<< nn 边的 ee RF −= 1 ： 1)1 FFBR −=−≈ β 4. 网的可靠度 2 1( ∑∑ = − = − −=−−= m i im e i ei m pi im e i ei RFCF