(a) 解释为什么不可能画出一个具有八个顶点的图，其中顶点度数为 1、2、2、3、3、4、4 和 6。

图 3 显示了网络 $T$。弧上的数字表示八个顶点 A、B、C、D、E、F、G 和 H 之间的距离（单位：km）。

(b) 确定 A – C – D – E – C – B – F 是否是 $T$ 上路径的一个例子。必须证明你的答案。

(c) 使用 Prim 算法，从 A 开始，找到 $T$ 的最小生成树。必须清楚说明选择树弧的顺序。

(d) 使用答案本中图 1 给出的顶点画出最小生成树。

弧 CF 的权重现在增加到 $x$。$T$ 的最小生成树是唯一的，并且包含与 (c) 中找到的相同的弧。

(e) 写出必须包含 $x$ 的最小区间。

利用握手定理：所有顶点度数之和必须等于边数的两倍，因此一定是偶数。把题目给出的八个度数相加即可判断是否可能。

The sum of the vertex orders is

By the handshaking lemma, the sum of all vertex orders must equal twice the number of arcs, so it must be even. Since 25 is odd, such a graph is impossible.

路径不能重复经过顶点。检查给出的顶点序列可见 C 出现两次，并且中间形成了 C—D—E—C 的回路，因此该序列不是路径。

No. The vertex C appears twice in

Therefore the sequence is not a path on $T$.

从 A 开始，每一步都在“已选顶点集合”和“未选顶点集合”之间选择权重最小的弧，且不能形成回路。必须按实际选取顺序列出弧，而不能只列权重。

Applying Prim’s algorithm from A, the arcs are selected in the order

The corresponding weights are

so the weight of the minimum spanning tree is

把 (c) 依次选出的七条弧画在题目给出的八个顶点之间。七条弧连接全部八个顶点且不形成回路，因此构成所求最小生成树。

The minimum spanning tree contains the arcs

Its diagram is:

CF 原来的权重是 21，题目说明其权重增加，所以 $x>21$。在所得 MST 中删除 CF 后，F 与其余顶点分离；把 F 重新接回树的下一条最轻弧是 FH，权重为 25。要使原 MST 仍然是唯一的，CF 必须严格轻于 FH。

Since the weight of CF is increased from 21,

If CF is removed from the minimum spanning tree, the next lightest arc that can reconnect F is FH, with weight 25. For the same minimum spanning tree to remain unique, CF must be strictly lighter than FH, so

Hence the smallest interval is