一个图最多可以有多少个最小高度树（MHT）？

Question

对于具有树特征的无向图，我们可以选择任意节点作为根。结果图是一个有根的树。在所有可能的有根树中，高度最小的树称为最小高度树（MHTs）。一个图最多可以有多少个 MHT？

Answer 1

我相信答案是 1 或 2。所以最多 2 个不同的 MHT。这个问题等同于首先找到给定图的直径。树的直径是两个树节点之间路径的最大长度。

有一个非常优雅的两遍算法来找到一棵树的直径。

1. 选择任意节点 A 并找到距离 A 最远的节点 B。（使用深度优先搜索或呼吸优先搜索）。
2. 从节点 B 开始，进行第二次 DFS 或 BFS 以找到距离 B 最远的节点 C。B 和 C 之间的距离就是这棵树的直径。

有了直径信息，我们实际上可以得到这些 MHT 的根节点。如果直径是偶数，则只有1个MHT，它的根是路径B到C的中间节点；如果直径为奇数，则将有 2 个 MHT，根是路径 B 到 C 的中间 2 个节点。这 2 个根节点保证彼此相邻。

以下链接显示了有关树中心数量的证明。这个问题的关键是我们想使用树的中心作为根，因为这提供了到所有其他节点的整体最小路径长度。您可以通过矛盾来证明这一点，使用任何其他节点都会产生更长的树高。

https://en.wikipedia.org/wiki/Centered_tree#:~:text=A%20graph%20can%20have%20an,two%20centers%20(bicentric%20trees)。