CSP-S 2023 第一轮 第12题：在图论中，树的重心是树上的一个结点，以该结点为根时，使得其所有的子树中结点数最

题目

在图论中，树的重心是树上的一个结点，以该结点为根时，使得其所有的子树中结点数最多的子树的结点数最少。一棵树可能有多个重心。请问下面哪种树一定只有一个重心？

选项

• A. $4$ 个结点的树
• B. $6$ 个结点的树
• C. $7$ 个结点的树
• D. $8$ 个结点的树

答案

C

题解

答案是 C．\(7\) 个结点的树。

树的重心有一个重要性质：

• 一棵树只可能有 1 个或 2 个重心。
• 如果有 2 个重心，它们一定相邻，并且删掉它们之间的边后，得到的两棵树的结点数相等。

因此，有两个重心的树，结点总数一定是偶数。反过来说，结点总数为奇数的树，一定只有一个重心。

选项中只有 \(7\) 是奇数，所以选 C。

注意：偶数个结点的树也可能只有一个重心，但不能保证。例如，把 \(4、6、8\) 个结点依次连成一条链，中间两个结点都是重心。