查看更多
当前 - 选择题 - 最小生成树
中等
单选题
2022年5月第43题
#数学与经济管理
#最小生成树
#第二版教材
#凯恩建议必须掌握

某乡有7个小山村A~G,村与村之间原有小路可加宽修建公路的线路如下图所示(路边的数字表示路长的公里数)。为实现村村通公路,修建公路总长至少(问题1)公里。若在(问题2)村新建一所中学,则可以使人们从离它最远的村到该校所走的优化路程最短。

正确答案A
凯恩解析

本题考察的是图论中最小生成树和最短路径的综合应用
主要应用Kruskal算法来求解最小生成树,并结合图的中心性分析来决定学校的最优位置。
问题 1:
要使所有村庄之间公路互通,并且总长度最小,就是求整个图的最小生成树(Minimum Spanning Tree, MST)。这类问题常用的算法有 Prim 和 Kruskal,这里采用 Kruskal 算法。
步骤如下:

  1. 将所有边按长度升序排序。
  2. 从最短边开始依次选择,只要不构成回路,就纳入生成树中,直到选出 n−1=6n-1 = 6n−1=6 条边(因为有7个村)。
    排序后的边长度为:
  • D-E(1.5)
  • E-G(1.5)
  • C-E(1.8)
  • A-D(2)
  • A-C(2)
  • F-D(3)
  • A-F(4)
  • B-G(4)
  • A-B(5)
  • B-C(5)
  • F-G(6)

选取以下6条边组成最小生成树:

  • B-G(4)
  • A-C(2)
  • D-E(1.5)
  • E-G(1.5)
  • C-E(1.8)
  • F-D(3)

总长为:4 + 2 + 1.5 + 1.5 + 1.8 + 3 = 13.8公里
因此,正确答案为:A. 13.8

问题 2:
在最小生成树上选一个村庄建立中学,目的是使所有村庄到该村的最短路径中最长的那一段最短。这属于图的中心节点(Graph Center)问题

在最小生成树上计算每个点到其他点的最短距离最大值(即该点的“最远距离”):
以每个点为起点跑一遍 BFS/DFS,得到最大路径距离。

根据题意,已知经过计算后,E 村是最优中心点,也就是说,以 E 为学校建校点,其它村庄到达它的最长路径是所有村点中最短的。
因此,正确答案为:E

联系我们
隐私协议
用户协议
微信公众号
知乎
小红书
浙ICP备2021029036号
@2022-2026
嘉兴市安芯网络科技有限公司 版权所有