2
$\begingroup$

I want to find center in a graph that doesn't have cycles. I heard, that this is how I find a diameter:

  1. Take random vertex A
  2. Find such vertex B, that distance to it is maximal
  3. Find such vertex C, that distance from B to C is maximal
  4. BC is diameter

And then I just divide it equally.

But how to prove this diameter finding algorithm? Why is it valid?

$\endgroup$
1
$\begingroup$

The solution for problem 4 in HW3_Solution.pdf gives a detailed proof. There is also the same question Prove traversing a k-ary tree twice yields the diameter asked on Stack Overflow.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.