运筹学 operations research 第三章图与网络分析 图的支撑树的应用举例 5 [例刀]某地新建5处居民点,拟修·75 道路连接5处,经勘测其道路可铺 55 成如图所示。为使5处居民点都有 3.5 道路相连,问至少要铺几条路? 解 该问题实为求图 的支撑树问题, 共需铺4条路。 vhttp://www.tju.edu.cn 第三章 图与网络分析 [ 例7] 某地新建 5处居民点，拟修 道路连接 5处，经勘测其道路可铺 成如图所示。为使 5处居民点都有 道路相连，问至少要铺几条路？ 解： 该问题实为求图 的支撑树问题， 共需铺 4条路。 v1 v2 v3 v4 v5 图的支撑树的应用举例 v1 v2 v3 v4 v5 5 5.5 3.5 7.5 4 2 3