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