网络优化问题的例子 例:公路连接问题 某一地区有若干个主要城市,现准备修建高速公路 把这些城市连接起来,使得从其中任何一个城市 都可以经高速公路直接或间接到达另一个城市假 定已经知道了任意两个城市之间修建高速公路的成 本,那么应如何决定在哪些城市间修建高速公路, 使得总成本最小? 最小(生成树 4 也称为 最小(支撑)树 28 例： 公路连接问题 某一地区有若干个主要城市，现准备修建高速公路 把这些城市连接起来， 使得从其中任何一个城市 都可以经高速公路直接或间接到达另一个城市. 假 定已经知道了任意两个城市之间修建高速公路的成 本，那么应如何决定在哪些城市间修建高速公路， 使得总成本最小？ 网络优化问题的例子 1 1 3 2 4 5 6 3 8 5 2 4 7 最小(生成)树 也称为 最小(支撑)树