题目
The table below represents a complete network that shows the least costs of travelling between eight cities, A, B, C, D, E, F, G and H.
Srinjoy must visit each city at least once. He will start and finish at A and wishes to minimise his total cost.
(a) Use Prim’s algorithm, starting at A, to find a minimum spanning tree for this network. You must list the arcs that form the tree in the order in which you select them.
(b) State the weight of the minimum spanning tree.
(c) Use your answer to (b) to help you calculate an initial upper bound for the total cost of Srinjoy’s route.
(d) Show that there are two nearest neighbour routes that start from A. You must make the routes and their corresponding costs clear.
(e) State the best upper bound that can be obtained by using your answers to (c) and (d).
(f) Starting by deleting A and all of its arcs, find a lower bound for the total cost of Srinjoy’s route. You must make your method and working clear.
(g) Use your results to write down the smallest interval that must contain the optimal cost of Srinjoy’s route.
题目中文翻译
下表表示一个完整网络，显示了八个城市 A、B、C、D、E、F、G 和 H 之间的最小旅行成本。
Srinjoy 必须每个城市至少访问一次。他将从 A 出发并回到 A，并希望最小化总成本。
(a) 使用 Prim 算法，从 A 开始，找到此网络的最小生成树。必须按选择顺序列出构成树的弧。
(b) 写出最小生成树的权重。
(c) 使用 (b) 的答案帮助计算 Srinjoy 路线总成本的初始上界。
(d) 证明从 A 出发有两条最近邻路线。必须清楚说明路线及其对应的成本。
(e) 写出使用 (c) 和 (d) 的答案可以获得的最佳上界。
(f) 通过删除 A 及其所有弧，找到 Srinjoy 路线总成本的下界。必须清楚说明方法和计算过程。
(g) 使用你的结果写出必须包含 Srinjoy 路线最优成本的最小区间。