CSP-S 2025 第一轮 第7题：一个包含 8 个顶点的完全图（顶点的编号为 1 到 8），任意两点之间的边权等于

题目

一个包含 $8$ 个顶点的完全图（顶点的编号为 $1$ 到 $8$），任意两点之间的边权等于两顶点编号的差的绝对值。例如，顶点 $3$ 和 $7$ 之间的边权为 $|7 - 3| = 4$。该图的最小生成树总权重是多少？

选项

• A. $7$
• B. $8$
• C. $9$
• D. $10$

答案

A

题解

答案是 A. \(7\)。

最小生成树要连接全部 \(8\) 个顶点，因此恰好有 \(8-1=7\) 条边。任意两个不同顶点之间的边权至少为 \(1\)，所以总权重至少为 \(7\)。

选择相邻编号之间的边： \[ 1-2-3-4-5-6-7-8 \] 这 \(7\) 条边每条权重都是 \(1\)，能连接全部顶点且没有环，构成一棵生成树，总权重为 \[ 7\times1=\boxed{7}. \]