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$
0

1 Answer 1

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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .