结构推理 已知世界六大城市:,N,,L,T,M,试在表所示交通网络的数据中确定最小树。 1351776850 1360706759 516057362 7770572055 6867362034 505925534
【正确答案】解:将表用图形的形式表示出来,如图所示,然后在图中寻求其最小支撑树。 (1)避圈法。首先,从图中选取权数最小的边;再在剩余的子圈中,取权最小的边;又在剩余的子圈中,取权最小的边[M,N],并使得它们相互不构成圈。依次进行,直到再也不能选取出边为止。此过程表达如下: 经过五次选边,得到边集合构成了唯一的最小支撑树,如图所示,此最小支撑树的总权为 (2)破圈法.破圈过程与上述避圈法的过程相反,但所得结果与(1)相同.
【答案解析】