Algorithm to find the diameter of a tree is :-

1) Choose a random node s and find the farthest node u from s.

2) Find the farthest node v from u.

3) d(u,v) is the diameter.

Can someone please explain why this algorithm works ?

Thanks

# | User | Rating |
---|---|---|

1 | tourist | 4009 |

2 | jiangly | 3773 |

3 | Radewoosh | 3646 |

4 | ecnerwala | 3624 |

5 | jqdai0815 | 3620 |

5 | Benq | 3620 |

7 | orzdevinwang | 3612 |

8 | Geothermal | 3569 |

8 | cnnfls_csy | 3569 |

10 | gyh20 | 3447 |

# | User | Contrib. |
---|---|---|

1 | cry | 161 |

2 | maomao90 | 160 |

2 | awoo | 160 |

4 | atcoder_official | 157 |

5 | -is-this-fft- | 155 |

5 | nor | 155 |

5 | adamant | 155 |

8 | maroonrk | 152 |

8 | Um_nik | 152 |

10 | djm03178 | 146 |

Algorithm to find the diameter of a tree is :-

1) Choose a random node s and find the farthest node u from s.

2) Find the farthest node v from u.

3) d(u,v) is the diameter.

Can someone please explain why this algorithm works ?

Thanks

↑

↓

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/12/2024 17:29:30 (l3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

A formal proof is given in "On computing a longest path in a tree" by R. W. Bulterman et al.

Cannot download the paper..

You need to pay for it or you can get it from libgen. I made it available here on Google Drive.

Thanks rr459595.

https://sci-hub.tw/ and http://libgen.io/ are some of the good websites to download academic materials. You can always try these.

This isn't a formal proof, but here's some insights that might help build your intuition for why it is true.

When you choose your random node

s, imagine rooting the tree ats. The first thing to note is that the two endpoints of the diameter will always be leaves (ors, ifsonly has one child. Even in this case, the other endpoint will always be leaf).Then, we can show that the farthest leaf

ufromsis one of the endpoints of the diameter. You can do this through contradiction, and I believe the main idea is something along the lines of "pretend the two endpoints are both notu. Then you can find a longer path by changing one of the endpoints tou."Great, now this farthest node

ufromsis one of the endpoints of the diameter! From here it's easy, the farthest nodevfromumustbe the other endpoint of the diameter.Can you tell how to prove by contradiction ?

Why do you need a proof? I just believe in it

You must be a theist.

Yes, I am. c:

Although it's not really necessary in this case, I think this might become clearer if you think instead about the centroid(s). Here's how it works:

Certainly the tree has a diameter, i.e. a longest path. Suppose the path from

xtoyis longest. Now consider the midpointCof this path. (This is the centroid of the tree, more or less.) IfD=d(x,y) is even,Cis a vertex; otherwise it is the midpoint of an edge. (If you like, imagine making the tree bigger by adding a vertex at the midpoint of every edge; this doesn't change your problem, and nowCis certainly a vertex.) Either way,d(x,C) =d(y,C) =D/ 2.Claim 1: For any vertex

z,d(z,C) ≤D/ 2. Proof: Consider the paths fromxtoz, and then fromztoy. Concatenating them, we get a (possibly degenerate) path fromxtoy. Since paths are essentially unique in a tree, this concatenation must pass throughC, i.e. one of the paths passes throughC. Thus suppose the path fromxtozpasses throughC. NowD≥d(z,x) =d(z,C) +d(C,x) =d(z,C) +D/ 2, which rearranges tod(z,C) ≤D/ 2.Claim 2: For any vertex

s, and a vertexufarthest froms,d(u,C) =D/ 2. Proof: Haved(s,u) ≥max(d(s,x),d(s,y)) ≥d(s,C) +D/ 2, where the second inequality comes from the previous proof. By triangle inequality,d(s,C) +d(u,C) ≥d(s,u), sod(u,C) ≥D/ 2. By Claim 1, we are done.Finally, by our observation above,

max(d(u,x),d(u,y)) ≥d(u,C) +D/ 2 =D, and we're done.Hopefully this tells you some more about what's going on: given any vertex

s, the vertices farthest fromsare precisely those which (a) have maximal distance to the centroid, and (b) don't lie on the same side of the centroid ass. In particular, the maximal distance fromsisd(s,C) +D/ 2.beutifully explained thank you so much.

I give a proof in this video (use the timestamps in the description to jump to the proof): https://www.youtube.com/watch?v=2PFl93WM_ao

It has pictures to go with the equations so is hopefully a bit easier to understand.

This proof is very memorable to me as I spent quite some time visualizing and proving it successfully myself.

My idea is very similar to Kognition's but I feel that the proof becomes intuitive if you visualize the diameter to be present beforehand and you are starting from a random node.

Bear my bad drawing skills

The claim of the theorem is that, if you start dfs from a random node

uwhich is not one of the endpoints of the diameter, the farthest nodevfromuis one of the endpoints of the diameter.Naming

u— staring nodev— farthest node fromud,d' — 2 endpoints of the diameterw— The first node in the diameter which is reached fromuWhat if

v≠d,d' then eitheruwe reachwbut from there we reach a nodev' ≠v. This implies that we get a larger diameter, hence a contradiction.w, thenThis shows that we can have a larger diameter, hence a contradiction. Hence we will always reach

wDo let me know if some parts of the proof is shaky. I solved this UVa problem using this idea.

Thanks a lot. I got it now :)

Maybe..this helps