资源描述：
《通信网理论基础课后习题答案new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、3.4k1.环上有k个端（3≤k≤n），此k个端的选择方式有C种；对于某固定的k端来说，考n虑可以生成的环，任指定一个端，下个端的选取方法公有k-1种，再下端的选法有k-2(k−1)!种，等等，注意，这样生成的环可按两种试图顺序取得，故有种，总的环数为2nk(k−1)!∑Cnk=322.某一固定边e确定了两个端，经过e的环数按其过余下端进行分类，若环再过k个端（1k≤k≤n-2），有选法C种；对于某固定端来说，自然可以生成k!个环，从而总的环数n−2nk为∑Cn−2k!个。k=33.两个固定端之间的径按其经过端数分类，其中有一条不经过其他端的径，若经过k个端，（
2、1≤k≤n-2），则对于第一个端有（n-2）种选择，第二个端有（n-3）种选择，第k个n−2(n−2)!(n−2)!端有（n-k-1）种选择，共有总的径数为1+∑(n−k−2)!k=1(n−k−2)!3.5试求图3-52中图的主树数目，并列举所有的主树。解：为图的端编号为v1,v2,v3,v4。取v3为参考点，有：3−1−1S=−120=8−102所得主树见下:图3-52第1页共23页3.6试证明端数n大于4的连接图都是非平面图，并求n=2，3，4的全连接图为对偶图。证明：设有n个端的全联接图为Kn因为K5是非平面图，而当n>5时K5是Kn的子图，从而K（nn>
3、5）均不是平面图。一下是对偶图（注意K4为自对偶图）。3.7⎡0101⎤已知一个图的邻接矩阵如左，画出此图，并求各⎢⎥0010端之间的最小有向径长。C=⎢⎥⎢0001⎥⎢⎥⎣0000⎦解：首先作出图形：对所绘制图形的端点进行编号，得邻接矩阵。vvvv1234⎡1010⎤⎢⎥C=0010⎢⎥⎢0001⎥⎢⎥⎣0000⎦第2页共23页经计算：⎡0010⎤⎡0001⎤⎢⎥⎢⎥00010000C2=⎢⎥C3=⎢⎥⎢0000⎥⎢0000⎥⎢⎥⎢⎥⎣0000⎦⎣0000⎦因而有d(v,v)=1d(v,v)=2d(v,v)=1121314d(v,v)=1d(v,v)=2232
4、4d(v,v)=134其余有向径长均为∞，或不存在。3.8图有六个端，其无向距离矩阵如下：vvvvvv1234561.用P算法，求出最短树。v1⎡012321⎤2.用K算法，求出最短树。⎢⎥v1012322⎢⎥3.限制条件为两端间通信的转接次数不超过2的最v3⎢210123⎥短树。⎢⎥v3210124⎢⎥v⎢232101⎥5⎢⎥v6⎣123120⎦解：1.P算法求解：{}v⎯⎯→e12{v,v}⎯⎯→e23{v,v,v}⎯⎯→e16{v,v,v,v}⎯⎯→e65{v,v,v,v,v}112123123612365⎯⎯→e34{}v,v,v,v,v,v123654
5、2.K算法求解：按最小边长顺序取得：e=e=e=e=e=1此结果意味着最短树不唯一。1223344556第3页共23页3.原图有一个边长全为1的基本子图G1，要求转接次数小于等于2，若选取G1的任何4个连续顶点，vvvv,作为基础，然后再按要求增加边，例如以vvvv为基础，ii+1i+2i+31234增加vv，得到一个树长为7转接次数小于等于2的树T1，事实上，以任何4个连续56顶点均可得到树长为7的转接次数小于等于2的树3.9图有六个端，端点之间的有向距离矩阵如下：vvvvvv1.用D算法求V1到所有其他端的最短径长及其路径。123456v1⎡0913∞∞⎤2
6、.用F算法求最短径矩阵和路由矩阵，并找到V2至v⎢104∞7∞⎥V4和V1至V5的最短径长及路由。2⎢⎥v⎢2∞0∞1∞⎥3.求图的中心和中点。3⎢⎥v∞∞50274⎢⎥v⎢∞62805⎥5⎢⎥v6⎣7∞2∞20⎦解：1.D算法V1V2V3V4V5V6指定最短径长0∞∞∞∞∞V1W1＝0913∞∞V3W13＝0932∞V5W15＝0837V4W14＝087V3W16＝08V2W12＝02.F算法最短路径矩阵及最短路由阵为W5，R5v→v→v有向距离为4214v→v→v有向距离为2135第4页共23页⎡0913∞∞⎤⎡023400⎤⎢⎥⎢⎥104∞7∞103050
7、⎢⎥⎢⎥⎢2∞0∞1∞⎥⎢100050⎥W0⎢⎥R0⎢⎥∞∞5027003056⎢⎥⎢⎥⎢∞62805⎥⎢023406⎥⎢⎥⎢⎥⎣7∞2∞20⎦⎣103450⎦⎡0913∞∞⎤⎡023400⎤⎢⎥⎢⎥10247∞101150⎢⎥⎢⎥⎢211051∞⎥⎢110150⎥W1⎢⎥R1⎢⎥∞∞5027003056⎢⎥⎢⎥⎢∞62805⎥⎢023406⎥⎢⎥⎢⎥⎣71621020⎦⎣113150⎦⎡091316∞⎤⎡023420⎤⎢⎥⎢⎥10247∞101150⎢⎥⎢⎥⎢211051∞⎥⎢110150⎥W2⎢⎥R2⎢⎥∞∞5027003056⎢⎥⎢⎥⎢762805⎥⎢22
8、3406⎥⎢⎥⎢⎥⎣71
