For an undirected graph with tree characteristics, we can choose any node as the root. The result graph is then a rooted tree. Among all possible rooted trees, those with minimum height are called minimum height trees (MHTs). How many MHTs can a graph have at most?
1 Answers
I believe the answer is 1 or 2. So at most 2 different MHTs. This problem is equivalent with first finding the diameter of the given graph. The diameter of a tree is the maximum length of a path between two tree nodes.
There is an very elegant two-pass algorithm to find a tree's diameter.
- choose an arbitrary node A and find the furtherest node B from A. (use Depth-First Search or Breath-First Search).
- Start from Node B, do a second DFS or BFS to find the furtherest Node C from B. The distance between B and C is the diameter of this tree.
Having the diameter information, we can actually get the root nodes of these MHTs. If the diameter is even, then there will be only 1 MHT and its root is the middle node of path B to C; If the diameter is odd, then there will be 2 MHTs and the roots are the middle 2 nodes of path B to C. These 2 root nodes are guaranteed to be adjacent with each other.
The following link shows the proof about the number of tree centers. The key in this problem is that we want to use the center of a tree as the root, as this provides an overall minimum path length to all other nodes. You can prove this by contradiction, using any other nodes will yield a longer tree height.
Related