2. 从业资格
  3. 山区某乡的6个村之间有山路如下图所示，其中的数字标明了各条山路（公里）。

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

考试题库2022-08-02  47
问题 山区某乡的6个村之间有山路如下图所示，其中的数字标明了各条山路（公里）。乡政府决定沿山路架设电话线。为实现村村通电话，电话线总长至少为（　　）公里。A.11B.14C.18D.33
选项 A.11
B.14
C.18
D.33
答案 B
解析 本题需要在给定的图上寻找最小支撑树。图由若干个结点以及结点之间的连线组成，每条连线上标记了权数（本题为长度）。最小支撑树实际上是其中的一个子图，它包括所有的结点以及部分连线，这些连线需要连接所有的结点，但其总权数（长度）最小。从本题应用看，就是要在上述山路图中确定部分山路，使其能连接6个村，又能使总长度最短。最小支撑树的求解方法：先选择最短的一条线（如有多条，可以任选一条），它已经连接了2个点。从这2点出发，再找出能连接其他一个点的最短线（如有多条，可以任选一条）。这样，就已经用2条线连接了3个点。依此类推，逐步做下去，连线也逐步增多，连接的点也逐步增多，直到所有的点都连上为止。这样求出的若干条连线以及所有结点就组成了最小支撑树。本题求出的一种最小支撑树如下：其连线的总长度等于14公里，连接了6个村。在同一个图中，最小支撑树的方案可能有多个，但其连线的总长度是相等的。这是运筹学求解最优问题的普遍原则：最优值如果有，则必是唯一的，但达到最优值的方案可能不止一个。
转载请注明原文地址:https://tihaiku.com/congyezige/2401748.html
本试题收录于： 高级系统分析师题库软件水平考试初中高级分类

高级系统分析师

软件水平考试初中高级

相关试题推荐
随机试题
最新回复(0)