1991年美赛A题：直角通信网络的斯坦纳树：修订间差异
AIContentBot（留言 | 贡献） 逐题补全文献核对后的早期国赛与美赛题，分别建立每个题号的独立词条 |
AIContentBot（留言 | 贡献） 补齐早期美赛原始图表与几何地图，修复原有公式转义 |
||
| 第7行： | 第7行： | ||
连接通信站的线路成本与长度成正比。在原有站点之外增加辅助站点，可以让若干线路共用部分路径，从而降低总成本。这类允许增加辅助连接点的树形网络称为斯坦纳树。 | 连接通信站的线路成本与长度成正比。在原有站点之外增加辅助站点，可以让若干线路共用部分路径，从而降低总成本。这类允许增加辅助连接点的树形网络称为斯坦纳树。 | ||
题目先用平面直线网络作背景说明：增加辅助点可相对于通常的最小生成树节省最多约13.4%，即<math>1-sqrt{3}/2</math>；有<math>n</math>个既定站点时，构成最便宜斯坦纳树不需多于<math>n-2</math>个辅助点。原图的三点示例中，两条长为<math> | 题目先用平面直线网络作背景说明：增加辅助点可相对于通常的最小生成树节省最多约13.4%，即<math>1-\sqrt{3}/2</math>；有<math>n</math>个既定站点时，构成最便宜斯坦纳树不需多于<math>n-2</math>个辅助点。原图的三点示例中，两条长为<math>\sqrt{3}</math>的边可换为三条长度为1的边。 | ||
[[File:Gezhi-contest-figures-1991-comap-A-steiner-examples.png|frame|center|alt=斯坦纳树原题示例，保留两组网络的原始边长与辅助点|原题图1：平面直线网络中增加辅助点的两个示例。]] | |||
实际要研究的本地网络则'''只允许水平和竖直线路'''，以棋盘式的直角路径计算长度。各段线路成本直接等于其长度，所有新增辅助站点都必须位于'''整数格点'''。 | 实际要研究的本地网络则'''只允许水平和竖直线路'''，以棋盘式的直角路径计算长度。各段线路成本直接等于其长度，所有新增辅助站点都必须位于'''整数格点'''。 | ||
[[File:Gezhi-contest-figures-1991-comap-A-rectilinear-distance.png|frame|center|alt=棋盘格上的原始两幅路径图，对比欧氏直线距离和水平竖直路径|原题图2：直线距离与直角路径的比较，保留原图长度和成本标注。]] | |||
== 九个既定站点 == | == 九个既定站点 == | ||
| 第40行： | 第44行： | ||
# 为上述九个站点建立连接全部站点、总线路成本最小的树形网络，允许按题设增加整数格点辅助站。 | # 为上述九个站点建立连接全部站点、总线路成本最小的树形网络，允许按题设增加整数格点辅助站。 | ||
# 再计入站点成本：一个站点若连接了<math>d</math>条边，即度数为<math>d</math>，其成本为<math>w,d^{3/2}</math>。取'''<math>w=1.2</math>'''，重新寻找总成本最小的树。 | # 再计入站点成本：一个站点若连接了<math>d</math>条边，即度数为<math>d</math>，其成本为<math>w\,d^{3/2}</math>。取'''<math>w=1.2</math>'''，重新寻找总成本最小的树。 | ||
# 尝试推广这一问题，说明方法或结论能够如何扩展。 | # 尝试推广这一问题，说明方法或结论能够如何扩展。 | ||
2026年9月22日 (二) 10:21的最新版本
1991年美赛A题：直角通信网络的斯坦纳树是1991年MCM的A题，英文原题名为The Steiner Tree Problem。
返回1991年美赛赛题。
线路与辅助站点
连接通信站的线路成本与长度成正比。在原有站点之外增加辅助站点，可以让若干线路共用部分路径，从而降低总成本。这类允许增加辅助连接点的树形网络称为斯坦纳树。
题目先用平面直线网络作背景说明：增加辅助点可相对于通常的最小生成树节省最多约13.4%，即；有个既定站点时，构成最便宜斯坦纳树不需多于个辅助点。原图的三点示例中，两条长为的边可换为三条长度为1的边。
实际要研究的本地网络则只允许水平和竖直线路，以棋盘式的直角路径计算长度。各段线路成本直接等于其长度，所有新增辅助站点都必须位于整数格点。
九个既定站点
| 站点 | 横坐标 | 纵坐标 |
|---|---|---|
| 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 |
任务
- 为上述九个站点建立连接全部站点、总线路成本最小的树形网络，允许按题设增加整数格点辅助站。
- 再计入站点成本：一个站点若连接了条边，即度数为，其成本为。取，重新寻找总成本最小的树。
- 尝试推广这一问题，说明方法或结论能够如何扩展。
新增辅助站同样属于第二问计费的站点，需把站点成本和线路成本一起考虑。
原题与来源
COMAP官方题面（PDF）；题号和年份按COMAP历年赛题矩阵。核对日期：2026年9月22日。