1991年美赛A题：直角通信网络的斯坦纳树

1991年美赛A题：直角通信网络的斯坦纳树是1991年MCM的A题，英文原题名为The Steiner Tree Problem。

返回1991年美赛赛题。

线路与辅助站点

连接通信站的线路成本与长度成正比。在原有站点之外增加辅助站点，可以让若干线路共用部分路径，从而降低总成本。这类允许增加辅助连接点的树形网络称为斯坦纳树。

题目先用平面直线网络作背景说明：增加辅助点可相对于通常的最小生成树节省最多约13.4%，即$1-\sqrt{3}/2$；有$n$个既定站点时，构成最便宜斯坦纳树不需多于$n-2$个辅助点。原图的三点示例中，两条长为$\sqrt{3}$的边可换为三条长度为1的边。

原题图1：平面直线网络中增加辅助点的两个示例。

实际要研究的本地网络则只允许水平和竖直线路，以棋盘式的直角路径计算长度。各段线路成本直接等于其长度，所有新增辅助站点都必须位于整数格点。

原题图2：直线距离与直角路径的比较，保留原图长度和成本标注。

九个既定站点

站点	横坐标	纵坐标
a	0	15
b	5	20
c	16	24
d	20	20
e	33	25
f	23	11
g	35	7
h	25	0
i	10	3

任务

1. 为上述九个站点建立连接全部站点、总线路成本最小的树形网络，允许按题设增加整数格点辅助站。
2. 再计入站点成本：一个站点若连接了$d$条边，即度数为$d$，其成本为$w{d}^{3/2}$。取$w=1.2$，重新寻找总成本最小的树。
3. 尝试推广这一问题，说明方法或结论能够如何扩展。

新增辅助站同样属于第二问计费的站点，需把站点成本和线路成本一起考虑。

原题与来源

COMAP官方题面（PDF）；题号和年份按COMAP历年赛题矩阵。核对日期：2026年9月22日。