2.2 求M/M/m（n）中，等待时间w的概率密度函数。 解： M/M/m（n）的概率分布为：
⎡m−1(mρ)k(mρ)m1−ρn−m−1⎤
p0+p0=⎢∑⎥m!1−ρ⎦⎣r=0k!
−1
⎧(mρ)k
⎪k!p0⎪
pk=⎨mmk
⎪k!ρp0⎪0⎩
0≤k≤m−1m≤k≤nk>n
假定n>m，n≥0，现在来计算概率P{w>x}，既等待时间大于x的概率。
P{w>x}=∑pj•Pj{w>x}
j=0
n
其中，Pj{w>x}的概率为：
Pj{w>x}=0
Pj{w>x}=
0≤j≤m−1
−mµx
∑e
i=0
j−m
(mµx)i⋅
i!
m≤j≤n−1 m≤j≤n
Pj{w>x}=1
可得：
P{w>x}=∑Pj⋅∑e
j=m
i=0
n−1j−m
−mµx
(mµx)i⋅+Pn
i!
⎤mm⎡n−1jj−m−mµx(mµx)i
P0⎢∑ρ⋅∑e=⋅+ρn⎥m!⎣j=mi!i=0⎦ mmn−m−1−mµx(mµx)iρm+i−ρn
P0∑e=⋅+Pn
1−ρm!i!i=0
若n→∞则
P0(ρm)m−(mµ−λ)x
P{w>x}=⋅e
1−ρm!
特别的，新到顾客需等待的概率为：
P0(ρm)m⋅P{W>0}= 1−ρm!
而
n−m−1n−m−2
mmP0(λx)i−mµxmm(λx)−mµρ[ρ(mµ−λ)∑fw(x)=e
(n−m−1)!i!m!(1−ρ)i=0
−mµρn
(mµλ)
(n−m−1)!
n−m−1
在n→∞
mmP0
ρm(mµ−λ)e−(mµ−λ)xfw(x)=
m!(1−ρ)
m−1k=0
注：P{w=0}=∑Pk
P{w=∞}=Pn
2.4求M/D/1排队问题中等待时间W的一、二、三阶矩m1、m2、m3，D表示服务时间为定值b，到达率为λ。 解：
s(1−ρ)
G(s)=
s−λ+λB(S)
其中 B(s)=
∫
∞
δ(t−b)e−stdt=e−sb
∞
s(1−ρ)i
又 G(s)=gs 从而 G(s)=∑i−sb
s−λ+λei=0∞
(−sb)j⎛∞i⎞⎛∴⎜∑gis⎟⎜⎜s−λ+λ⋅∑j!j=0⎠⎝⎝i=0
⎞
⎟=s(1−ρ) ⎟⎠
−λb2(1−ρ)(1−ρ)(2λb3+λ2b4)1−ρ
g0= g1= g2=
1−λb2(1−λb)212(1−λb)3−(1+2λb)(1−ρ)λb4g3=L4
24(1−λb)
(λb=ρ)
λb2
m1=−G′(0)=−g1=
2(1−ρ)
m2=G′′(0)=g2×2=
(2+ρ)λb6(1−ρ)2
3
(1+2ρ)λb4
m3=−G′′′(0)=g3×6=
4(1−ρ)3
2.5 求M/B/1，B/M/1和B/B/1排队问题的平均等待时间，其中B是二阶指数分布：
f(t)=αλ1e−λ1t+(1−α)λ2e−λ2t
解：M/B/1
λ1,λ2>0
0
B(S)=∫f(t)e−stdt=
∞
(1−α)λ2αλ1
+λ1+sλ2+s
w2=B′′(0)=
2α
w1=−B′(0)=
α1−α+λ1λ2
λm2λ(1−α)λ12+αλ22==
(1−ρ)λ12λ22−αλλ1λ22−(1−α)λλ12λ2
[]
λ12
+
2(1−α)
λ22
ρ=λw1=λ⎜⎜
⎛α⎝λ1
+
1−α⎞
⎟λ2⎟⎠
B/M/1
(1−α)λ2αλ1
+σ=
µ−µσ+λ1µ−µσ+λ2取0
σ=B(µ−µσ)
令
λ1
=ρ1
λ2
=ρ2
1+ρ1+ρ2−+(ρ1−ρ2)2+2(1−2α)(ρ1−ρ2)σ=
2=
σµ(1−σ)
=
1+ρ1+ρ2−+(ρ1−ρ2)2+2(1−2α)(ρ1−ρ2)
µ(1−ρ1−ρ2++(ρ1−ρ2)2+2(1−2α)(ρ1−ρ2))
−λ1t
B/B/1
设到达的概率密度函数为f(t)=αλ1e
+(1−α)λ2e−λ2t
设离去的概率密度函数为f(t)=αλ3e假设α1=α2=α
−λ3t
+(1−α)λ4e−λ4t
λ1=λ3λ2=λ4
A(s)=B(s)=
αλ1(1−α)λ2
+λ1+sλ2+s
⎛αλ1(1−α)λ2⎞⎛αλ1(1−α)λ2⎞
⎟⎜⎟A(−s)B(s)−1=⎜++⎟−1⎟⎜λ+s⎜λ−sssλλ+−22⎠⎠⎝1⎝1
[λ+λ
=
21
t2s2−s4−(αλ1+(1−α)λ2)s2−s4
=
(λ1−s)(λ2−s)(λ1+s)(λ2+s)(λ1−s)(λ2−s)(λ1+s)(λ2+s)
2
2
2
]
取
Φ+(s)=
s(t+s)(λ1+s)(λ2+s)
w(s)=
kΦ+(s)
Φ−(s)=
s(t−s)(λ1−s)(λ2−s)
k=lim
Φ+(s)t
=
s→0λ1λ2s
k(λ1+s)(λ2+s)
(t+s)
2
2
Sw(s)=
=−[Sw(s)]s=0=
'
λ1λ2−(λ1+λ2)t
λ1λ2t
2
2
其中
t=λ1+λ2−(αλ1+(1−α)λ2)2=(1−α2)λ1+(2α−α2)λ2−2α(1−α)λ1λ2
2.6 在D/D/1排队问题中，顾客到达的时间间隔为a，服务时间为b，均为恒定值，且a>b， 求：稳定状态时系统的队列长度为k的概率pk，顾客到达时队列的长度为k的概率vk，顾客离去时队列的长度dk，以及平均等待时间，并用G/G/1上界公式求出此时的平均等待时间，评论计算结果，并讨论a≤b的情况。 解： 由于是D/D/1问题，故子系统运行情况完全确定，第一个顾客到达后，系统无顾客，
经过b后，服务完毕，顾客离去，再经过a-b后，下一个顾客到达。
此时有：
⎧⎪pk=⎨(a−b)⎪⎩
⎧1
rk=dk=⎨ ⎩0
顾客不等待时=0
G/G/1
上
界
k=1k=0k=0k≠0
公
式
σr2+σt2
≤
2(1−ρ)
2
2
Qp(τ)=δ(τ−a)
p(t)=δ(t−b)
∴στ=σt=0
22
∴≤
στ+σt
=0
21−ρ)
∴=0
ab
时间后，系统队列长度增长1。 a−b
2
−2µτ
当a
2.7求M/E2/1即时拒绝系统的呼损，其中E2是二阶爱尔兰分布，b(τ)=(2µ)τe
解： 设相邻呼叫到达间隔为t，如果服务时间τ>t，将造成呼损，τ≤t时无呼损。
∴pc(t)=∫b(τ)dτ
t∞
∞
t
∞
则
∞
−λt0
pc=∫a(t)⋅∫b(τ)dτdt=∫λe⋅∫(2µ)τe
t
∞
2−2µτ
λ2+4λµ
dτdt=
(λ+2µ)2
2.8在优先级别队列中，A队为优先级，不拒绝，B队为非优先级，只准一人排队等待（不计在服务中的），且当A队无人时才能被服务，求各状态概率，A队的平均等待时间和B队的拒绝概率。 解：
说明： 0状态代表系统中无顾客状态；
i，j状态代表系统中正在服务且A
队中有i个顾客，B队列中有j个顾客排
队的状态。
状态转移图如右，A队到达率为λ1，B队到达率为λ2，服务率µ，系统稳定时，应有ρ1=
λ1
可得到特征方程如下:
⎧(λ1+λ2)P0=µP00
⎪(µ+λ+λ)P=µ(P+P)+(λ+λ)P
[1**********]⎪⎪
⎨(µ+λ1)P01=λ2P00+µP11
⎪(µ+λ+λ)P=λP+µPi>012i,01i−1,0i+1,0⎪⎪⎩(µ+λ1)Pi,1=λ1Pi−1,1+µPi+1,1+λ2Pi,0i>0
i
L1L2
L3 L4L5
由于4是差分方程，不妨设其通解为：pi0=p00x 代入有：
(1+ρ1+ρ2)p00xi=ρ1p00xi−1+p00xi+1⇒x2−(1+ρ1+ρ2)x+ρ1=0
Q0
22
1+ρ1+ρ2−+ρ1+ρ2−2ρ1+2ρ2+2ρ1ρ2
∴x0=
2
由于5是非齐次差分方程：
pi+1,1−(1+p1)pi,1+ρ1pi−1,1+ρ2pi,0=0 其特征根为：a=ρ1
i
i
假设其通解为：pi,1=Aρ1+Bx0代入前式得：
i+1ii−1iB⋅x0−(1+ρ1)B⋅x0+ρ1B⋅x0+ρ2p00⋅x0=0
解之，得：B=−p00Qpi,1=Aρ1i−p00x0
i
代入3式得：(1+ρ1)p01=ρ2p00+p11 即：
A=p00(1+ρ1+ρ2−x0)
ii⎧pi，
1=p00(1+ρ1+ρ2−x0)ρ1−x ⎪i
pi，⎨0=p00x
⎪p00=(ρ1+ρ2)p0⎩
[]
由正则条件：
p0+(ρ1+ρ2)p0(1+ρ1+ρ2−x0)∑ρ1i=1
i=0
∞
∴∴
p0=A=
1−ρ1
1−ρ1+ρ1+ρ21+ρ1+ρ2−x0(r+1)[p∑µ
r=0
1
∞
r，0
+pr，1]=
(r+1)p(1+ρ∑µ
00
r=0
1
∞
1
+ρ2−x0)ρ1
r
=
p00(1+ρ1+ρ2−x0)
µ1−ρ12
⎧(λ1+λ2)P0=µP00
⎪(µ+λ+λ)P=µ(P+P)+(λ+λ)P
[1**********]⎪⎪
⎨(µ+λ1)P01=λ2P00+µP11
⎪(µ+λ+λ)P=λP+µPi>012i,01i−1,0i+1,0⎪⎪⎩(µ+λ1)Pi,1=λ1Pi−1,1+µPi+1,1+λ2Pi,0i>0
i
L1L2
L3 L4L5
由于4是差分方程，不妨设其通解为：pi0=p00x 代入有：
(1+ρ1+ρ2)p00xi=ρ1p00xi−1+p00xi+1⇒x2−(1+ρ1+ρ2)x+ρ1=0
Q0
22
1+ρ1+ρ2−+ρ1+ρ2−2ρ1+2ρ2+2ρ1ρ2
∴x0=
2
由于5是非齐次差分方程：
pi+1,1−(1+p1)pi,1+ρ1pi−1,1+ρ2pi,0=0 其特征根为：a=ρ1
i
i
假设其通解为：pi,1=Aρ1+Bx0代入前式得：
i+1ii−1iB⋅x0−(1+ρ1)B⋅x0+ρ1B⋅x0+ρ2p00⋅x0=0
解之，得：B=−p00Qpi,1=Aρ1i−p00x0
i
代入3式得：(1+ρ1)p01=ρ2p00+p11 即：
A=p00(1+ρ1+ρ2−x0)
ii⎧pi，
1=p00(1+ρ1+ρ2−x0)ρ1−x ⎪i
pi，⎨0=p00x
⎪p00=(ρ1+ρ2)p0⎩
[]
由正则条件：
p0+(ρ1+ρ2)p0(1+ρ1+ρ2−x0)∑ρ1i=1
i=0
∞
∴∴
p0=A=
1−ρ1
1−ρ1+ρ1+ρ21+ρ1+ρ2−x0(r+1)[p∑µ
r=0
1
∞
r，0
+pr，1]=
(r+1)p(1+ρ∑µ
00
r=0
1
∞
1
+ρ2−x0)ρ1
r
=
p00(1+ρ1+ρ2−x0)
µ1−ρ12
r
()=++−−PCB=∑pr，p1ρρxρx100∑12010
r
r=0
r=0
∞∞
[]
=
p00(1+ρ1+ρ2−x0)p
−00
1−ρ11−x0
2.9排队系统中有三个队列,其到达率分别为
λa,λb,λc公用同一出线路，其中a类最优先，
即线路有空闲就发送；b类次之，即a无排队时
可以发送，c类最低，即a，b类均无排队时可以发送，不计正在传送的业务，各个队列的截至队长为na＝2，nb=1，nc＝0，试列出稳定状态下的状态方程，并计算λa=λb=λc时，各
状态的概率和三类呼叫的呼损。
解： r，s，k分别表示a，b，c三队中等待的呼叫数，状态以（r，s，k）表示。 稳态方程：
(λa+λb+λc)p0=µp000
(λa+λb+µ)p000=µ(p010+p100)+(λa+λb+λc)p0(λa+λb+µ)p100=µp200+λap000(λb+µ)p200=λap100
(λa+µ)p010=λbp000+µp110
µp210=λap110+λbp200
(λa+µ)p110=λbp100+λap010+µp210
归一条件p0+
λa
p=1 若 令λ=λ=λρ=∑i,j,kabc
p010p110
p000=3ρp0p100
3ρ2+3ρ3
=p02ρ2+2ρ+13ρ
p0
2
2ρ+2ρ+1
3
3ρ2+9ρ3+12ρ4=p0
2
2ρ+2ρ+16ρ3+15ρ4+12ρ5=p0
2ρ2+2ρ+16ρ+15ρ+12ρ
p0
2
2ρ+2ρ+1
4
5
6
p200=p210=
2ρ2+2ρ+1
p0=
12ρ6+27ρ5+36ρ4+27ρ3+14ρ2+5ρ+1
C类呼损为：pc=1−p0=L B类呼损为：pB=p010+p110+p210
A类呼损为：pA=p210+p200
2.10 有一个三端网络，端点为v1,v2,v3，边为e1(v1,v2)及e2(v2,v3)，v1到v3的业务由v2转接，设所有的端之间的业务到达率为λ，线路的服务率为µ的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间业务占用。 状态转移图如右：
当λ12=λ13=λ23=λ时 有下列关系:
⎧µpt=λp00
⎪3λp=µ(p+p+p)
000110*⎪⎪
⎨(λ+µ)p10=λp00+µp11 ⎪(λ+µ)p=λp+µp
010011
⎪⎪⎩2µp11=λ(p01+p10)
又
∑p=1 解之得:
⎧p*=p01=p10=ρp00
⎨2
⎩p11=ρp00
这里
p00=
11+3ρ+ρ
2
3ρ+ρ22ρ+ρ2
而p23=p12=1−p00−p01= 呼损p13=1−p00=22
1+3ρ+ρ1+3ρ+ρ3ρ+2ρ2
通过量T=ρ(1−p12)+ρ(1−p13)+ρ(1−p23)= 2
1+3ρ+ρ2ρ+ρ2
线路利用率η=p*+p11+(p10+p01)/2= 2
1+3ρ+ρ
2.11上题中的网若用于传送数据包,到达率仍为 每秒 平均包长为b比特,边的容量为c比特/秒,采用不拒绝的方式,并设各端的存储容量足够大,求: (1)稳定条件。
(2)网络的平均时延。 (3)总的通过量。
(4)线路的平均利用率。
解：这是一个无损但有时延的系统。 两条线路上到达率为：2 ，而服务率为：c/b的M/M/1系统。 (1)稳定条件为： 2 b/c
对v1v2和v2v3间的业务：1=
11
= µ(1−ρ)−2λ
对v1v3间的业务：2=21=
2−2λ
(3)系统稳定时，总的通过量为：3 b/c。 (4)线路的平均利用率 = =2 b/c。
一般来说，通过率与利用率均有增加，这是以稳定性和时延为代价换来的。
2.12在分组交换系统中，设信息包以泊松率到达，平均到达率为 ，但信息包的长度为固定b比特，信道容量为c比特/秒。由于端内存储量的限制，设除了在传送的包外，只允许有两个信息包等待传送，试：
(1)列出关于dr(顾客离去时的队长)的系统方程 (2)解出个dr.
(3)求平均时延。
(4)求信息包被拒绝的概率。 解：
⎧d0=d0q0+d1q0
⎪d=dq+dq+dq
011120⎪1
⎪d2=d0q2+d1q2+d2q1+d3p0
⎨
（⎪d3=d0q3+d1q3+d2q2+d31−p0）
⎪3
⎪∑di=1⎩i=0
其中p0是第4个顾客被拒绝离去之后，第3个顾客的残余寿命中无顾客到达的概率。 这里到达是随机的，可知：p0=设λ则
∞
−λτ
∞
∫
b/c
c−λtc−λ⋅edt=⎛ ⎜1−e⎞⎟
⎝⎠bλb
=ρ
b(τ)dτ=∫e−λτδτ−dτ=e−ρ
q0=∫e
∞b
()
q1=∫λτe−λτb(τ)dτ=ρe−ρ2
1−q0
∴d1=d0
q0
q2=∫
∞
(λτ)2e−λτb(τ)dτ=ρ2e−ρ
2
d2=e2ρ−(1+ρ)eρd0
[]
⎡3ρ(2ρ+ρ2)ρ⎤2ρρ⎢e−(1+2ρ)e+e⎥d0
2⎦d3=⎣
eρ−1
ρ
e−1
Q∑di=1d0=
4ρ+ρ2ρ3ρ22ρ
(1+ρ)e−(1+2ρ+2ρ)e+e
2
平均时延：
⎡m⎛mv⎞⎤3⎞ρ1⎤b⎡32ρ⎛
⎟++=−+2ρ⎟e+⎥d0 emd=+bc=⎢vd1+⎜⎜1⎟2⎥⎢⎜2⎠2⎦c⎝⎣2⎝2m1⎠⎦⎣2m1
拒绝概率：
pC=d3
2.13有四个端三条边组成的数据网，如图所示。端间的信息包分别为和每秒，信息包长度为
负指数分布，平均包长为k比特，各信道容量分别为c1，c2和c3，和一起排队，和一起排队，和一起排队，均不拒绝，求 (1)各种业务的平均时延。 (2)网络的平均时延。 (3)各信道的平均利用率。 解: 由于均不拒绝且到达和离去均随机，故3个
信道均等效于3个M/M/1系统，其中： C1：到达为λ12+λ13。服务为：c1/b C2：到达为λ12+λ42。服务为：c2/b C3：到达为λ13+λ43。服务为：c3/b C1的平均迟延为
11
= cµ1(1−ρ1)1
−λ12−λ13b11
= cµ2(1−ρ2)2
−λ12−λ42b11
=
µ3(1−ρ3)c
3
−λ13−λ43b
C1的平均迟延为
C1的平均迟延为
s12=sc1+sc2=
11
−λ12−λ13b
+
12
−λ12−λ42b
s13=sc1+sc3=
1c1
−λ12−λ13b1
+
1c3
−λ13−λ43b
s42=sc2=
2
−λ12−λ42b
s43=sc3=
11
−λ13−λ43b
网络的平均时延为：s=各信道利用率为：
λ12s12+λ13s13+λ42s42+λ43s43
λ12+λ13+λ42+λ43
ηc1=ρ1=(λ12+λ13)b/c1ηc2=ρ2=(λ12+λ42)b/c2 ηc3=ρ3=(λ13+λ43)b/c3
2.14总线上有4个用户v1,v2,v3和v4，它们之间以Alopha方式互相通信，信包到达率均为每秒，信息包的长度为b比特；总线上的传输速率为c比特/秒，试求通过率r，并大致画出r与b的曲线关系。
解：r与b的曲线关系如右图，从直观上来看，这也是显然的。
总线上一个包的服务时间τ=秒，
总的呼叫量为：a=12λ，
通过量为：=a⋅e通过率：r=−2a
=12λe−2a 3.2 设在一个纯ALOHA系统中，分组长度τ=20ms，总业务到达率λt=10 pkt/s，试求一个消息成功传输的概率。若为S-ALOHA系统，试求这时消息成功传输的概率，并求一个消息分组传输时和另一个分组碰撞的概率。
解：由题意，τ=20ms，λt=10pkt/s，则系统的总业务量为
P=λtτ=10×20×10−3=0.2
纯ALOHA系统吞吐量满足p=Pe
−2P
，一个消息成功传输的概率为
Ps=pP=e−2P=e−2×0.2=e−0.4=0.67
S-ALOHA系统的吞吐量满足p=Pe
−P
，这时消息成功传输的概率为
Ps=pP=e−P=e−0.2≈0.82
一个消息分组传输时和另一个分组碰撞的概率为：
1−Ps=1−0.82=0.18。
3.3
设在一个S-ALOHA系统中每秒共发送120次，其中包括原始发送和重发。每次
发送需占用一个12.5 ms的时隙。试问： （1） 系统的归一化总业务量等于多少？ （2） 第一次发送就成功的概率等于多少？ （3） 在一次成功发送前，刚好有两次碰撞的概率等于多少？
解：由题意，λt=120次/秒， τ=12.5 ms。 （1） P=λtτ=120×12.5×10（2） P(0)=e
−λtτ
−3
=1.5。
=e−1.5=0.223。
（3） p3=1−e
(
−P2
)e
−P
=(1−0.223)×0.223=0.135。
2
3.4 设一条长度为10 km的同轴电缆上，接有1000个站，信号在电缆上传输速度为200 m/us，信号发送速率为10 Mb/s，分组长度为5000 b。试问： （1） 若用纯ALOHA系统，每个站最大可能发送分组速率等于多少？ （2） 若用CSMA/CD系统，每个站最大可能发送分组速率等于多少？ 解：（1）纯ALOHA中，发送分组不用等待。理想情况下，各站一个接一个发送分组，互不干扰，发送分组的最大速率为
10M/(5000×1000)=2 pkt/s
（2）对于CSMA/CD系统，信号传输速率为200 m/s，对于10 km电缆，单程传播时间为 t=10×10/200=50 µs
3
CSMA/CD系统发送一个分组必须等待的时间为：2t=100 us=0.1 ms。 故每个站的最大可能发送分组速率为：10M×0.1 ms/5000=0.2 pkt/s。
4.4有一个n端的全连接图。试证： （1）无重复端的环数为
∑Cnk
k=3
n
(k−1)!
2
n
（2）经过某一固定边e的环数为
∑k!C
k=3
kn−2
（3）两个固定端之间的径数位1+
∑n−k−2!
k=1
n−2
(n−2)!
(1)环上有k个端（3≤k≤n），此k个端的选择方式有Cn种；对于某固定的k端来说，考虑可以生成的环，任指定一个端，下个端的选取方法公有k-1种，再下端的选法有k-2种，等
n
(k−1)!k(k−1)!种，总的环数为∑Cn 等，注意，这样生成的环可按两种试图顺序取得，故有
22k=3
k
(2)某一固定边e确定了两个端，经过e的环数按其过余下端进行分类，若环再过k个端（1≤k≤n-2），有选法Cn−2种；对于某固定端来说，自然可以生成k!个环，从而总的环数为
k
∑C
k=3
n
k
n−2
k!个。
(3)两个固定端之间的径按其经过端数分类，其中有一条不经过其他端的径，若经过k个端，（1≤k≤n-2），则对于第一个端有（n-2）种选择，第二个端有（n-3）种选择，第k个端
n−2
(n−2)!(n−2)!
总的径数为 1+∑ 有（n-k-1）种选择，共有
(n−k−2)!(n−k−2)!k=1
4.5 试求图4-44中图的主树数目，并列举所有的主树。
解：为图的端编号为v1,v2,v3,v4。 取v3为参考点，有：
3S=−1
−1
图4-44
−1−120
0=8 2
所得主树见下:
4.6 试证明端数n大于4的连接图都是非平面图，并求n=2，3，4的全连接图为对偶图。 证明：设有n个端的全联接图为Kn因为K5是非平面图，而当n>5时K5是Kn的子图，从而Kn（n>5）均不是平面图。一下是对偶图（注意K4为自对偶图）。
4.7
⎡
0⎢0C=⎢
⎢0⎢⎣0
1000
0100
1⎤0⎥⎥ 1⎥⎥0⎦
已知一个图的邻接矩阵如左，画出此图，并求各端之间的最小有向径长。
对所绘制图形的端点进行编号，得邻接矩阵。
解：首先作出图形：
v1
⎡
⎢C=⎢
⎢⎢⎣
v2v3v41010⎤0010⎥
⎥
0001⎥
⎥
0000⎦
经计算：
⎡0⎢02
C=⎢
⎢0⎢⎣0
因而有
00001000
0⎤⎡0
⎢01⎥3⎥ C=⎢
0⎥⎢0⎥⎢0⎦⎣0
d(v1,v3)=2
0000000
1⎤0⎥⎥ 0⎥⎥0⎦
d(v1,v2)=1
d(v2,v3)=1 d(v3,v4)=1
d(v1,v4)=1
d(v2,v4)=2
其余有向径长均为 ∞，或不存在。
4.8 图有六个端，其无向距离矩阵如下：
v1v1v2v3v4v5v6
v2⎡0⎢1⎢⎢2⎢⎢3⎢2⎢⎣1v3v4v5v612321⎤01232⎥
⎥
10123⎥
⎥
21012⎥32101⎥
⎥
23120⎦
用P算法，求出最短树。 用K算法，求出最短树。
限制条件为两端间通信的转接次数不超过2的最
短树。
解：
(1)P算法求解：
eeee
{v1}⎯⎯→{v1,v2}⎯⎯→{v1,v2,v3}⎯⎯→{v1,v2,v3,v6}⎯⎯→{v1,v2,v3,v6,v5}
e
⎯⎯→{v1,v2,v3,v6,v5,v4}
12
23
16
65
34
(2)K算法求解：
按最小边长顺序取得： e12=e23=e34=e45=e56=1此结果意味着最短树不唯一。
(3)原图有一个边长全为1的基本子图G1，要求转接次数小于等于2，若选取G1的任何4个连续顶点，vivi+1vi+2vi+3,作为基础，然后再按要求增加边，例如以v1v2v3v4为基础，增加
v5v6，得到一个树长为7转接次数小于等于2的树T1，事实上，以任何4个连续顶点均可
得到树长为7的转接次数小于等于2的树
4.9 图有六个端，端点之间的有向距离矩阵如下：
v1v2v3v4v5v6
v1v2⎡09⎢10⎢
⎢2∞⎢
⎢∞∞⎢∞6⎢
⎣7∞
v3v413
v5v6∞∞⎤
4∞7∞⎥
⎥
0∞1∞⎥
⎥
5027⎥2805⎥
⎥
2∞20⎦
(1)用D算法求V1到所有其他端的最短径长及其路径。 (2)用F算法求最短径矩阵和路由矩阵，并找到V2至V4和V1至V5的最短径长及路由。 (3)求图的中心和中点。
解：
(1)D
算法
V10
V2∞ 9 9 8 8 V3∞
V4∞ 3 3
V5∞ ∞
V6∞ ∞ ∞ 7
指定 V1V3V5V4V3V2
最短径长W1＝0 W13＝0 W15＝0 W14＝0 W16＝0 W12＝0
(2)F算法
最短路径矩阵及最短路由阵为W5，R5
v2→v1→v4有向距离为4
v1→v3→v5有向距离为2
第 15 页 共 26 页
⎡0913∞∞⎢⎤⎢104∞7∞⎥
W⎢2∞0∞1∞⎥
⎥
0⎢⎢∞∞
5027⎥
⎢⎥⎢∞62805⎥
⎣7∞2∞20⎥
⎦⎡0913∞∞⎢⎤⎢10247∞⎥
W⎢⎢211051∞⎥
⎥
1⎢∞∞5027⎥
⎢⎢∞62805⎥⎥
⎣71621020⎥
⎦⎡091316∞⎢⎤⎢10247∞⎥
W⎢211051∞⎥
⎥
2⎢⎢∞∞5027⎥
⎢⎢762805⎥⎥
⎣71621020⎥
⎦⎡09132∞⎢⎤⎢10243∞⎥
W⎢⎢211051∞⎥
⎥
3⎢7165027⎥
⎢⎢462805⎥⎥
⎣4132720⎥
⎦⎡0913210⎢⎤⎢1024311⎥
W⎢21105112⎥
⎥
4⎢⎢7165027⎥
⎢⎢462705⎥⎥
⎣4132720⎥
⎦⎡081327⎢⎤⎢102438⎥
W⎢⎢270516⎥
⎥
5⎢684027⎥
⎢⎢462705⎥⎥
⎣4
82720⎥
⎦
⎡023400⎢⎤⎢103050⎥R⎢100050⎥⎥0⎢⎢003056⎥⎢⎢023406⎥⎥⎣103450⎥⎦⎡02340
0⎢⎤⎢101150⎥R⎢⎢110150⎥⎥1⎢003056⎥⎢⎢023406⎥⎥⎣113150⎥⎦⎡023420⎢⎤⎢101150⎥R⎢⎢110150⎥⎥2⎢003056⎥⎢⎥⎢223406⎥⎣11315
0⎥⎦
⎡023430⎢⎤⎢101130⎥R⎢110150⎥⎥3⎢⎢333056⎥⎢⎢32
3
3
6⎥⎥⎣313350⎥⎦⎡023434⎢⎤⎢101134⎥R⎢110154⎥⎥4⎢⎢333056⎥⎢⎢323306⎥⎥⎣31335
0⎥⎦
⎡053435⎢⎤⎢101135⎥
R⎢150155⎥
⎥
5⎢⎢555056⎥
⎢⎢323306⎥⎥
⎣3
53350⎥
⎦
第 16 页 共 26 页
(3)MaxWij=(8,8,7,8,7,8) 中心为V3或V5
5
j
∑W
j
5ij
=(21,18,21,27,24,23) 中心为V2
补充习题：试计算完全图Kn的主树的数目。
解：设A为Kn的关联阵，那么主树的数目为：
n−1
n−1
N=dctA⋅AT=dct
−1−1
LLL1=dctM
MO
O
−1−1
0LLMn−1=dctM
M
O
−1
O
n−1−=dctO
n−1
LLL1n
n00MM
O
n−1
n
O
=nn−1⋅
1
=nn−2n
n
O
0n
证毕。
5.1求下图中Vs到Vt的最大流量fst,图中编上的数字是该边的容量。 解： 本题可以利用M算法，也可以使用最大流－最小割简单计算可知：
X={vs,v3,v4}
={v1,v2,vt}
C(X,)=3+5+1+3=12
fs2 =5，f12=1，
可知：最大流为12，可以安排为fs1 = 3,，
f2t＝4，f1t=4，fs3=1，fs4=3，f3t=1，f4t=3。
5. 2试移动上图中的一条边，保持其容量不变，是否能增大fst？如果可以，求此时的最大值，但若所有转接端v1v2v3和v4的转接容量限制在4，则情况将如何？
第 17 页 共 26 页
解： 依然按照最大流－最小割定理，若
能依一边从X找到内部至割(X,)中，自然可以增大流量，可以将e34移去，改为：e41 或者e42均可，使总流量增至12＋2＝14。
当vi(i = 1,...4)的转接容量限制到4时，等效图为右图，对于3.11中的流量分配，在本题限制下，若将fs2由5改为4即得到一个流量为11的可行流。 但若X=vS,v3,v3v4,v4,v2
'
*={v1,v1',v2,vt}
*
v1
v1'
{
''
}
， 则
v44v4'
C(X*,*)=1+3+4+3=11，换句话说就是11已是最大流。
5.3图5-12中的Vs和Vt间要求有总流量fst＝6，求最佳流量分配，图中边旁的两个数字前者为容量，后者为费用。 解： 本题可以任选一个容量为6的可行流，然后采用负价环法，但也可用贪心算法，从Vs出发的两条线路费用一样，但进入Vt的两条路径费用为7和2，故尽可能选用费用为2的线路，得下图1。
再考虑V0，进入V0的两条路径中优先满
足费用为3的路径，得：图2，很容易得到
最后一个流量为fst=6的图3，边上的数字
为流量安排。总的费用为 VsL=3×2+3×2+1×3+2×4+1×1
+2×3+4×2+2×7=52
易用负价环验证图4的流量分配为最佳流量分配。
3,4
图1
4图 2
2图 3
2图 4
第 18 页 共 26 页
第 19 页 共 26 页
6.1由n个元件构成的一个系统，各元件的平均寿命都是T。当一个元件失效据使得系统失效的情况下，已知系统的平均寿命将下降至T/n，如果采取容错措施，当m个以上元件失效才使系统失效，求证此系统的平均寿命为：Tm=T
1
∑r=0n−r
m
可见比未采取措施前提高至少m倍。当m=n-1时，这一系统实际上即是n个元件的并接系
统，试证上式即转化成并连系统的寿命公式。
证：以i状态代表有i个元件失效的状态，此时系统的状态转移框图如下：
Tn−i
那么状态i的平均寿命为：Si=
0≤i≤m
从而系统的平均寿命为：S=S0+S1+L+Sm=T
1 ∑i=0n−i
m
当m=n-1时S=T
1
∑kk=0
112131n1n
(1)=C−C+C−L+−Cn ∑nnn
23nk=0k
n
n
而利用数学归纳法易知：
6.3有n个不可修复系统，它们的平均寿命都是T。先取两个作为并接，即互为热备份运行；
当有一个损坏时，启用第三个作为热备份；再损坏一个是起用第四个，已知下去，直到n个系统均损坏。忽略起用冷备份期间另一系统损坏的可能性；试计算这样运行下的平均寿命；并与全冷备份和全热备份是的平均寿命相比较。
解：状态图如下：i表示有i个系统损坏，失效在图中标出。
由上图有：Si=
T2
0≤i≤n−2Sn−1=T
从而，平均寿命：
S=S0+S1+L+Sn−1=S冷=nTS热
Tn+1×(n−1)+T=T22111⎞⎛
S热＝⎜1+++L+⎟T
n⎠23⎝
6.4上题目中n个子系统都是可修复系统，可靠度都是R。仍用上述方式运行，一损坏系统修复后作为最后一个系统排队等候再起用，求稳态可靠度。 解： m，n-m表示n个系统中有m个失效，状态转移图及失效率与修复率如图：
用Pm表示状态m,n-m的概率（稳态），状态方程如下：
⎧2αp0=βp1
⎪M⎪
⎪(2α+mβ)pm=2αpm−1+(m+1)βpm+1⎪⎪M⎨
⎪(2α+nβ)pn−1=2αpn−2+nβpn⎪αp=nβp
n
⎪nn−1⎪pi=1∑⎪⎩i=0
解状态方程如下：有：
m
⎧(2α)p0⎪pm=m⎪m！β⎨n
()α2⎪p=p0nn
⎪2n！β⎩
0
0≤m
⎡n−11⎛2α⎞m2n−1αn⎤
+由归一性：p0=⎢∑⎟⎜⎥ ⎟⎜n
n！β⎥⎝β⎠⎢⎣m=0m！⎦
1⎛2α⎞
⎜∑m！⎜β⎟⎟⎝⎠
m
m
−1
稳态可靠度：Rs=1−pn=
1⎛2α⎞2α+⎜⎟∑m！⎜β⎟n！βn⎝⎠
n−1n
其中，
α1−R
R是单一系统的可靠度。 =
βR
6.5一个复杂系统有n级梯形结构组成如图所示。其中有n个子系统作为桥，2(n+1)个子系
统作为梯边，它们都是可靠度为R的可以修复系统。求这个复杂系统的可靠度递推公式，假定所有子系统都互相独立。
解：
依次考虑1，2，3，… n。依照各个桥的情况可以分类，根据1，2，3，… n的好坏情况可以得到以下结果：
情况 Ⅰ Ⅱ Ⅲ ┇ N N+1
概率 R R(1-R) R(1-R)2
R(1-R)n-1(1-R)n
可靠度 [1-(1-R)2]Rn-1[1-(1-R2)2]Rn-2[1-(1-R3)2]Rn-3
[1-(1-Rn)2]R01-(1-Rn+1)2
∴
Rn=R(2R−R2)Rn−1+R(1−R)(2R2−R4)Rn−2+L
+R(1−R)
n−1
(2R
n
−R
2n
)R+(1−R)(2R
n
n+1
−R
2n+2
)
其中：R0=2R−R n≥0
2
6.6有一个故障率为α的系统，为了考虑是否使之成为可修复系统而配备维修力量，分别计算两类可靠度，试证明作为不可修复系统在时间T以内的可靠度大于作为可修复系统的稳态可靠度的条件是：βT
αT=0.01
解：故障率为的不可修复系统在T（αT=0.01）内的可靠度为：
R(T)=e−αT=e−0.01
α β的可修复系统的稳定可靠度为
αα+β
αα+β
现：
R(T)>
或 e
−0.01
>
αTαT+βT
=
αT
0.01+βT
∴βT
−r
6.7有一故障率为α，修复率为的系统β，已知此系统的费用是C=Aα
+Bβs
其中A，B，r，s为已知的非负常量，求可靠度为0.99时的最小费用。 解：
Q
αα+β
=0.99∴β=99αC=
A
αr
+B⋅99s⋅sαs−1
1r+s
令：
dcA
=0有−r+B⋅99s⋅sαs−1=0dαα
−r
r+s
⎛rA⎞∴α=⎜s⎟Bs99⋅⎠⎝99s
⎛rA⎞
Cmin=A⎜s⎟
⎝Bs⋅99⎠⎛rA⎞+B⎜s⎟⎝Bs⋅99⎠
sr+s
只考虑端故障，且各端的可靠6.8用流量法求图5－9(b)中的二分网的联接度α和结合度β，度均为R，求1端和5'端间的联接概率。
解：图5－9(b)中的二分图，任意一端度数均为4，δ=4 容易知道：
α=β=δ=4
一知考虑端故障，故中有一，二，
三失效和无失效是等价图入右：
可靠度分别为：
[1−(1−R)]⋅C⋅R(1−R)[1−(1−R)]{C⋅R(1−R)
3
14
3
4
24
2
2
+C⋅R(1−R)+C⋅R
34
3
44
3
4
}
1和5'之间联接概率为：
1234
R1,5'=C4⋅R(1−R)1−(1−R)+C4⋅R2(1−R)+C4⋅R3(1−R)+C4⋅R4⋅1−(1−R)
3
2
4
[]{}[]
1. 2. 3.
6.9有一网络结构如图：
验证网络是否为保证网。
求联接度α和结合度β。
若每边的可靠度都是Re，每端的可靠度
Rn,求线路故障下网络的可靠度和局故障的网络的可靠度。
求v1和v2间联接的概率。
要使α和β都为2，如何添加一条边来
满足。 解：
4. 5.
1. 原网收缩为：
从而是保证图。 2. 3.
去掉U1,U2可使网中断，故α=1, 局故障下网的可靠度： 端的不可靠度为Fn=1−Rn
β=2。
网络的可靠度R1=1−
当Fn
边故障下： CF∑αii=nin(1−Fn)n−i=1−∑CiFniRni=1nn−i R1≈1−CαFnα=1−2Fn
边的不可靠度为Fe=1−Re：
网的可靠度R2=1−
当Fe
4. ∑BF(1−F)iieei=pmm−i=1−∑CiFeiRei=22mm−i R1≈1−BβFem=1−12Fn
R1,6=1−(1−ReRn)1−ReRn1−1−ReRn222
R1,6
5. ()][()][1−(1−R)(1−RR)] =R[1−(1−R)(1−RR)][1−(1−RR)][2222een2n222eenen在V1和V3之间连一条边，就使α=β=2
6.11有一个四端全联接的网络，各边的容量都为1，可靠度均为0.999，若网络内部只有两个端之间有业务，呼叫量为0.1爱尔兰，不可靠集定义为转接次数大于1，或呼损大于0.01，设所有端均不出故障，求此两端之间通信的综合可靠度。
解：
考虑到转接此时小于等于1，那么某两端见的等
效网络为右图：
有三条独立的线路可靠度为：R2，R1，R2。
其中：R1＝0.999 R2＝0.9992
呼叫量为0.1个爱尔兰，又因为必有呼损率小于0.01，
那么有爱尔兰公式一可知，在可靠集中应至少有两条
线路是正常的，
设x为不正常线路个数：
x=0的概率：R1R2
x=1的概率：2R1(1−R2)R2+(1−R2)R2 22
综合可靠度：2R1(1−R2)R2+(1−R2)R2+R1R2 22
m6.12有m条边n个端的随机图有Cn(n−1)种，即每条边可在任两端之间，在这许多图中，有多
2
少在某两端vi和vj间有边？已知某边的一端是vi，另一端是vj的占多少？若m=n-1，联接图占总数的百分之几。
解：
m−1vi和vj之间有边Cn(n−1)种，
2−1
若某边的一端是vi，另一端是vj的概率： m−1Cn(n−1)mn(n−1)=2−12m2m= n(n−1)n(n−1)
2
数的总数是n n−2nn−2，从而联接图占：n−1 Cn(n−1)2