列表

详情


山区某乡的 6 个村之间有山路如下图所示,其中的数字标明了各条山路(公里)。

乡政府决定沿山路架设电话线。为实现村村通电话,电话线总长至少为(  )公里。

A. 11

B. 14

C. 18

D. 33

参考答案: B

详细解析:

本题需要在给定的图上寻找最小支撑树。
图由若干个结点以及结点之间的连线组成,每条连线上标记了权数(本题为长度)。
最小支撑树实际上是其中的一个子图,它包括所有的结点以及部分连线,这些连线需要连接所有的结点,但其总权数(长度)最小。
从本题应用看,就是要在上述山路图中确定部分山路,使其能连接6个村,又能使总长度最短。
最小支撑树的求解方法:先选择最短的一条线(如有多条,可以任选一条),它已经连接了2个点。从这2点出发,再找出能连接其他一个点的最短线(如有多条,可以任选一条)。这样,就已经用2条线连接了3个点。依此类推,逐步做下去,连线也逐步增多,连接的点也逐步增多,直到所有的点都连上为止。这样求出的若干条连线以及所有结点就组成了最小支撑树。
本题求出的一种最小支撑树如下:

其连线的总长度等于14公里,连接了6个村。
在同一个图中,最小支撑树的方案可能有多个,但其连线的总长度是相等的。
这是运筹学求解最优问题的普遍原则:最优值如果有,则必是唯一的,但达到最优值的方案可能不止一个。

上一题