1
$\begingroup$

I am given a connected graph. I have to construct a spanning tree from the graph, that has minimum diameter.

However, I looked for the solution, and the solution goes like this.

If the diameter of the tree is even, then it must have a center node. Then we try to find the center node by finding all pair shortest path first, and then trying to check every node if it can be a center or not. We do this the following way.

Lets say the current vertex we are checking is called v.

If the two most farthest vertex from v is x and y, and they have the same distance from the vertex v then v is a potential center of a diameter. Then we store ans = dis[v][x] + dis[v][y]. We find the minimum of such node v for which dis[v][x] + dis[v][y] is minimum. Here, dis[v][x] means the distance from v to x.

To avoid the diameter being odd, we introduce new vertex in every edges.

For example if there is an edge like 1-2 then we introduce a new vertex ( let's say 3 ) and the edge 1-2 becomes 1-3 and 3-2.

What I need is a proof of this solution. Why are we taking the minimum of dis[v][x] + dis[v][y]? How does this guarantees the minimum diameter?

Also, the solution mentioned if the diameter isn't even, then you might want to check the most distanced vertex from v being x and y and as the diameter is odd, |dis[v][x] - dis[v][y]| = 1 this check will not provide a correct answer.

What I am searching for is a formal proof of this.

The problem is listed in UVa Online Judge, Here's the link:

http://uva.onlinejudge.org/external/108/10805.pdf

The solution I found is this:

https://yuting-zhang.github.io/uva/2016/12/21/UVa-10805.html

$\endgroup$
  • $\begingroup$ The case of even-length diameter is easy. The case of odd-length diameter is not that immediate. In fact, the given solution page is wrong when it says "This way, we ensure that the diameter is always even". $\endgroup$ – Apass.Jack Sep 30 '18 at 5:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.