资源描述
3.41. 环上有k个端（3kn），此k个端的选择方式有种；对于某固定的k端来说，考虑可以生成的环，任指定一个端，下个端的选取方法共有k-1种，再下端的选法有k-2种，等等，注意，这样生成的环可按两种试图顺序取得，故有种，总的环数为2. 某一固定边e确定了两个端，经过e的环数按其过余下端进行分类，若环再过k个端（1kn-2），有选法种；对于某固定端来说，自然可以生成k!个环，从而总的环数为个。3. 两个固定端之间的径按其经过端数分类，其中有一条不经过其他端的径，若经过k个端，（1kn-2），则对于第一个端有（n-2）种选择，第二个端有（n-3）种选择，第k个端有（n-k-1）种选择，共有 ，总的径数为 3.5 试求图3-52中图的主树数目，并列举所有的主树。图3-52解：为图的端点编号为v1,v2,v3,v4。取v3为参考点，有：所得主树如下:3.11求下图中Vs到Vt的最大流量fst,图中编上的数字是该边的容量。解：本题可以利用M算法，也可以使用最大流最小割简单计算可知：可知：最大流为12，可以安排为fs1 = 3,，fs2 =5，f21=1，f2t4，f1t=4，fs3=1，fs4=3，f3t=1，f4t=3。3.13图3.55中的Vs和Vt间要求有总流量fst6，求最佳流量分配，图中边旁的两个数字前者为容量，后者为费用。解：本题可以任选一个容量为6的可行流，然后采用负价环法，但也可用贪心算法，从Vs出发的两条线路费用一样，但进入Vt的两条路径费用为7和2，故尽可能选用费用为2的线路，得下图1。图1再考虑V0，进入V0的两条路径中优先满足费用为3的路径，得：图2，很容易得到最后一个流量为fst=6的图3，边上的数字为流量安排。总的费用为易用负价环验证图4的流量分配为最佳流量分配。4.3 试证M | M | m(n) 中的列德尔公式也成立证明：又有列德尔公式成立，证毕。4.10有一个三端网络，端点为，边为及，v1到v3的业务由v2转接，设所有的端之间的业务到达率为l，线路的服务率为m的M/M/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间业务占用。状态转移图如右：当时有下列关系:又 解之得:呼损而通过量线路利用率5.4一个复杂系统有n级梯形结构组成如图所示。其中有n个子系统作为桥，2(n+1)个子系统作为梯边，它们都是可靠度为R的可以修复系统。求这个复杂系统的可靠度递推公式，假定所有子系统都互相独立。解：依次考虑1，2，3， n。依照各个桥的情况可以分类，根据1，2，3， n的好坏情况可以得到以下结果：情况概率可靠度R1-(1-R)2Rn-1R(1-R)1-(1-R2)2Rn-2R(1-R)21-(1-R3)2Rn-3NR(1-R)n-11-(1-Rn)2R0N+1(1-R)n1-(1-Rn+1)2其中： 5.8有一网络结构如图：1. 验证网络是否为保证网。2. 求联接度和结合度。3. 若每边的可靠度都是Re，每端的可靠度Rn,求线路故障下网络的可靠度和局故障的网络的可靠度。4. 求v1和v2间联接的概率。5. 要使和都为2，如何添加一条边来满足。解：1. 原网收缩为：从而是保证图。2. 去掉U1,U2可使网中断，故=1, =2。3. 局故障下网的可靠度：端的不可靠度为网络的可靠度当边故障下：边的不可靠度为：网的可靠度当4.5. 在V1和V3之间连一条边，就使=2
展开阅读全文