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

3.41.环上有k个端（3≤k≤n），此k个端的选择方式有种；对于某固定的k端来说，考虑可以生成的环，任指定一个端，下个端的选取方法公有k-1种，再下端的选法有k-2种，等等，注意，这样生成的环可按两种试图顺序取得，故有knC2)!1(−k种，总的环数为∑=−nkknkC32)!1(2.某一固定边e确定了两个端，经过e的环数按其过余下端进行分类，若环再过k个端（1≤k≤n-2），有选法种；对于某固定端来说，自然可以生成k!个环，从而总的环数为个。knC2−∑=−nkknkC32!3.两个固定端之间的径按其经过端数分类，其中有一条不经过其他端的径，若经过k个端，（1≤k≤n-2），则对于第一个端有（n-2）种选择，第二个端有（n-3）种选择，第k个端有（n-k-1）种选择，共有)!2()!2(−−−knn总的径数为∑−=−−−+21)!2()!2(1nkknn3.5试求图3-52中图的主树数目，并列举所有的主树。图3-52解：为图的端编号为v1,v2,v3,v4。取v3为参考点，有：8201021113=−−−−=S所得主树见下:第1页共23页3.6试证明端数n大于4的连接图都是非平面图，并求n=2，3，4的全连接图为对偶图。证明：设有n个端的全联接图为Kn因为K5是非平面图，而当n5时K5是Kn的子图，从而Kn（n5）均不是平面图。一下是对偶图（注意K4为自对偶图）。3.7⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=0000100001001010C已知一个图的邻接矩阵如左，画出此图，并求各端之间的最小有向径长。解：首先作出图形：对所绘制图形的端点进行编号，得邻接矩阵。⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=00001000010001014321vvvvC第2页共23页经计算：⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=00000000100001002C⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=00000000000010003C因而有1),(21=vvd2),(31=vvd1),(41=vvd1),(32=vvd2),(42=vvd1),(43=vvd其余有向径长均为∞，或不存在。3.8图有六个端，其无向距离矩阵如下：⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎣⎡021321101232210123321012232101123210654321654321vvvvvvvvvvvv1.用P算法，求出最短树。2.用K算法，求出最短树。3.限制条件为两端间通信的转接次数不超过2的最短树。解：1.P算法求解：{}{}{}{}{}{}456321563216321321211,,,,,,,,,,,,,,,3465162312vvvvvvvvvvvvvvvvvvvvveeeee⎯→⎯⎯→⎯⎯→⎯⎯→⎯⎯→⎯2.K算法求解：按最小边长顺序取得：15645342312=====eeeee此结果意味着最短树不唯一。第3页共23页3.原图有一个边长全为1的基本子图G1，要求转接次数小于等于2，若选取G1的任何4个连续顶点，,作为基础，然后再按要求增加边，例如以为基础，增加，得到一个树长为7转接次数小于等于2的树T1，事实上，以任何4个连续顶点均可得到树长为7的转接次数小于等于2的树iv1+iv2+iv3+iv1v2v3v4v5v6v3.9图有六个端，端点之间的有向距离矩阵如下：⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎣⎡∞∞∞∞∞∞∞∞∞∞∞∞022750826720510274013190654321654321vvvvvvvvvvvv1.用D算法求V1到所有其他端的最短径长及其路径。2.用F算法求最短径矩阵和路由矩阵，并找到V2至V4和V1至V5的最短径长及路由。3.求图的中心和中点。解：1.D算法V1V2V3V4V5V6指定最短径长0∞∞∞∞∞V1W1＝0913∞∞V3W13＝0932∞V5W15＝0837V4W14＝087V3W16＝08V2W12＝02.F算法最短路径矩阵及最短路由阵为W5，R5有向距离为4412vvv→→有向距离为2531vvv→→第4页共23页⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎣⎡⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎣⎡⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎣⎡⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎣⎡⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎣⎡⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎣⎡∞∞∞⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎣⎡⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎣⎡∞∞∞∞∞⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎣⎡⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎣⎡∞∞∞∞∞∞∞⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎣⎡⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎣⎡∞∞∞∞∞∞∞∞∞∞∞∞0533536033236505555510515311015343500272845072647204866150728342017231800533136033236503334510114311014343200272134507264720516712150112113420110231900533136033236503330510110311010343200272134508264720516715011234201231900513116043226503000510110511010243200210216750826772051501127420116319005131160432065030005101105110100432002102167508267205150112742013190054301604320650300050001050301004320022750826720510274013190554433221100RWRWRWRWRWRW第5页共23页3.中心为V)8,7,8,7,8,8(5=ijjWMax3或V5∑=jijW)23,24,27,21,18,21(5中心为V23.11求下图中Vs到Vt的最大流量fst,图中编上的数字是该边的容量。解：本题可以利用M算法，也可以使用最大流－最小割简单计算可知：{}43,,vvvXs={}tvvvX,,21=()123153,=+++=XXC可知：最大流为12，可以安排为fs1=3,，fs2=5，f12=1，f2t＝4，f1t=4，fs3=1，fs4=3，f3t=1，f4t=3。3.12试移动3.54图中的一条边，保持其容量不变，是否能增大fst？如果可以，求此时的最大值，但若所有转接端v1v2v3和v4的转接容量限制在4，则情况将如何？解：依然按照最大流－最小割定理，若能依一边从X找到X内部至割),(XX中，自然可以增大流量，可以将e34移去，改为：e41或者e42均可，使总流量增至12＋2＝14。356462314444222v1v1'v2v3v4v2'v3'v4'VsVt当vi(i=1,...4)的转接容量限制到4时，等效图为右图，对于3.11中的流量分配，在本题限制下，若将fs2由5改为4即得到一个流量为11的可行流。但若{}2'44'33*,,,,vvvvvvXS=，{}tvvvvX,,,'2'11*=则113431),(**=+++=XXC，换句话说就是11已是最大流。第6页共23页3.13图3.55中的Vs和Vt间要求有总流量fst＝6，求最佳流量分配，图中边旁的两个数字前者为容量，后者为费用。解：本题可以任选一个容量为6的可行流，然后采用负价环法，但也可用贪心算法，从Vs出发的两条线路费用一样，但进入Vt的两条路径费用为7和2，故尽可能选用费用为2的线路，得下图1。再考虑V0，进入V0的两条路径中优先满足费用为3的路径，得：图2，很容易得到最后一个流量为fst=6的图3，边上的数字为流量安排。总的费用为3,23,22,31,16,33,45,74,2VsVt图1527224321142312323=×+×+×+×+×+×+×+×=L易用负价环验证图4的流量分配为最佳流量分配。3424Vt222433211224VsVtVsVt图2图3图4Vs3.16试计算完全图Kn的主树的数目。解：设A为Kn的关联阵，那么主树的数目为：211000011110011111110011111111−−=⋅=−−==−−−=−−−−−−−=⋅=nnTnnnnnnndctnndctnndctnnndctAAdctN证毕。第7页共23页4.1求M/M/m（n）中，等待时间w的概率密度函数。解：M/M/m（n）的概率分布为：11010011!)(!)(−−=−−⎥⎦⎤⎢⎣⎡−−+=∑mrmnmkmmpkmpρρρρ⎪⎪⎩⎪⎪⎨⎧≤≤−≤≤=nknkmpkmmkpkmpkmkk0!10!)(00ρρ假定nm，n≥0，现在来计算概率P{wx}，既等待时间大于x的概率。∑=•=njjjxwPpxwP0}{}{其中，Pj{wx}的概率为：njmxwPnjmixmexwPmjxwPjmjiixmjj≤≤=−≤≤⋅=−≤≤=∑−=−1}{1!)(}{100}{0µµ可得：xmmnnimmniixmmnmjnmjiixmjmnnmjmjiixmjemmPxwP则若nPixmePmmixmePmmPixmePxwP)(010010010!)(1}{1!)(!!)(!!)(}{λµµµµρρρρρµρµρµ−−+−−=−−=−=−−=−=−⋅−=∞→+−−⋅=⎥⎦⎤⎢⎣⎡+⋅⋅=+⋅⋅=∑∑∑∑∑特别的，新到顾客需等待的概率为：!)(1}0{0mmPWPmρρ⋅−=])!1()()!1()(!)()([)1(!)(而12010−−−−−−−−=−−−−=−−−∑mnmmmnxmixmemPmxfmnnmnimnmimxmmwµλµρλµρλλµρρµ第8页共23页nmkkxmmmwPwPPwP注：emmPmxf在n=∞===−−=∞→∑−=−−}{}0{)()1(!)(10)(0λµλµρρ4.4求M/D/1排队问题中等待时间W的一、二、三阶矩m1、m2、m3，D表示服务时间为定值b，到达率为λ。解：)()1()(SBsssGλλρ+−−=其中sbstedtebtsB−∞−=−=∫0)()(δ从而sbesssG−+−−=λλρ)1()(又∑∞==0)(iiisgsG)1(!)(00ρλλ−=⎟⎟⎠⎞⎜⎜⎝⎛−⋅+−⎟⎠⎞⎜⎝⎛∴∑∑∞=∞=sjsbssgjjiiibgλρ−−=110221)1(2)1(bbgλρλ−−−=34232)1(12)2)(1(bbbgλλλρ−+−=34332322211443)1(4)21(6)0()1(6)2(2)0()1(2)0()()1(24)1)(21(ρλρρλρρλρλλλρλ−+=×=′′′−=−+=×=′′=−=−=′−==−−+−=bgGmbgGmbgGmbbbbg4.5求M/B/1，B/M/1和B/B/1排队问题的平均等待时间W，其中B是二阶指数分布：100,)1()(212121−+=−−αλλλααλλλtteetf解：M/B/1()[]2212212221222122112221221122110)1(1)1(1)1(22)0(1)0()1()()(λλλαλαλλλλαλλαλρλλαλαλλρλαλαλαλαλλαλαλ−−−+−=−=⎟⎟⎠⎞⎜⎜⎝⎛−+==−+=′′=−+=′−=+−++==∫∞−mwwBwBwssdtetfSBst第9页共23页B/M/1)))(21(2)(11())(21(2)(11)1(2))(21(2)(1110)1()(21221212122121212212122112211ρραρρρρµρραρρρρσµσρραρρρρσαλµσµλαλµσµαλσρµλρµλµσµσ−−+−++−−−−+−+−++=−=−−+−+−++=+−−++−===−=w的根取令BB/B/1设到达的概率密度函数为tteetf2121)1()(λλλααλ−−−+=设离去的概率密度函数为tteetf4343)1()(λλλααλ−−−+=假设423121λλλλααα====()[][]2122