NOIP 普及组初赛 · NOIP 2015 普及组初赛试题 第 12 题

$6$ 个顶点的连通图的最小生成树，其边数为( )。

这题考的是最小生成树的基本性质：n个顶点的树必有n−1条边。拿到题先别想算法，直接想树的结构——连通无环，所以边数一定是顶点数减一，代入6算就是5。

很多人会死记硬背最小生成树算法（比如Prim或Kruskal），结果把边数想成和顶点数一样，或者误以为要算具体边权总和。其实这道题连图都没给，纯粹考概念：树的结构决定了边数永远是n−1，不管最小还是最大生成树都成立。

考点与概念

这道题考查的是最小生成树（MST）的基本性质：n个顶点的树必有n−1条边。最小生成树是原图的一棵树（连通无环），所以6个顶点的最小生成树有6−1=5条边。

命题视角

命题人喜欢挖这种纯概念坑：不让你算具体边权，只问边数。很多人会死记硬背最小生成树算法（比如Prim或Kruskal），结果把边数想成和顶点数一样，或者误以为要算具体边权总和。其实这道题连图都没给，纯粹考概念：树的结构决定了边数永远是n−1，不管最小还是最大生成树都成立。