图 5 显示了一个加权图，包含 12 条弧和 8 个顶点。

已知

• 没有两条弧具有相同的权重
• $x$ 和 $y$ 是正整数
• 弧 CD 不在图的最小生成树中

(a) 解释为什么 $y < x + 7$

还已知当从 A 开始的 Prim 算法应用于加权图时，AB 是选择的第一条弧。

(b) 证明 $y > 2x$ 并写出并简化关于 $x$ 和 $y$ 值的两个进一步约束。

(c) 在答案本的图 1 上表示这四个约束。

(d) 仅使用图 1，写出 $x$ 和 $y$ 可以取的可能值对，形式为 $(x, y)$。

图 5 中加权图的最小生成树总权重为 73。

最小生成树中七条弧中的六条是 AB、AD、BC、CE、EF 和 GH。

(e) 确定 $x$ 的值和 $y$ 的值。必须清楚说明方法和计算过程。

D 只与 A、C 相连。既然 CD 不在最小生成树中，为了连接 D，AD 必须在树中；又因为各边权互不相同，所以 CD 的权必须大于 AD 的权。

The only arcs incident to D are AD and CD. Since CD is not in the minimum spanning tree, AD must be in the tree. Therefore

Hence

从 A 开始运行 Prim 算法时，第一条边只能从与 A 相连的 AB、AC、AD、AE 中选取。AB 首先被选且所有边权互不相同，所以 AB 的权分别严格小于另外三条边的权。

Since AB is selected first,

Therefore

and the two further constraints are

画出四条边界直线 $y=x+7$、$y=2x$、$x=1$ 和 $3y=4x+8$。由于四个不等式都是严格不等式，边界不属于可行域；取同时满足 $y<x+7$、$y>2x$、$x>1$ 和 $3y>4x+8$ 的交集。

Draw the boundary lines

The feasible region is the intersection satisfying

读出可行域内部的所有整点。边界上的点不能计入，因为原来的四个不等式都是严格不等式。

The possible integer pairs are

已知的六条边还没有把 H 所在部分与其余顶点连起来。比较可用的 EH、EG、FG，EH 的权最小，所以第七条边是 EH。把七条边的权相加并令总权为 73，再从上一问的九组整数解中筛选即可。

In the feasible region,

Also, since $x$ and $y$ are integers, $x>1$ and $y<x+7$ give $x\geq2$ and $y\leq x+6$. Hence

Thus EH is lighter than both EG and FG, so the remaining arc in the minimum spanning tree is EH.

Therefore the total weight is

Since the total weight is 73,

Testing the integer pairs from part (d), only $(3,7)$ satisfies this equation, since

Hence