Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Proof of correctness: Algorithm for diameter of a tree in graph theory

In order to find the diameter of a tree I can take any node from the tree, perform BFS to find a node which is farthest away from it and then perform BFS on that node. The greatest distance from the second BFS will yield the diameter.

I am not sure how to prove this, though? I have tried using induction on the number of nodes, but there are too many cases.

Any ideas would be much appreciated...

like image 682
AYR Avatar asked Nov 15 '13 20:11

AYR


People also ask

How do you prove a graph is a tree?

Theorem: An undirected graph is a tree iff there is exactly one simple path between each pair of vertices. Proof: If we have a graph T which is a tree, then it must be connected with no cycles. Since T is connected, there must be at least one simple path between each pair of vertices.

What is the diameter of graph?

The diameter of a graph is the length of the shortest path between the most distanced nodes. d measures the extent of a graph and the topological length between two nodes.


1 Answers

Let's call the endpoint found by the first BFS x. The crucial step is proving that the x found in this first step always "works" -- that is, that it is always at one end of some longest path. (Note that in general there can be more than one equally-longest path.) If we can establish this, it's straightforward to see that a BFS rooted at x will find some node as far as possible from x, which must therefore be an overall longest path.

Hint: Suppose (to the contrary) that there is a longer path between two vertices u and v, neither of which is x.

Observe that, on the unique path between u and v, there must be some highest (closest to the root) vertex h. There are two possibilities: either h is on the path from the root of the BFS to x, or it is not. Show a contradiction by showing that in both cases, the u-v path can be made at least as long by replacing some path segment in it with a path to x.

[EDIT] Actually, it may not be necessary to treat the 2 cases separately after all. But I often find it easier to break a configuration into several (or even many) cases, and treat each one separately. Here, the case where h is on the path from the BFS root to x is easier to handle, and gives a clue for the other case.

[EDIT 2] Coming back to this later, it now seems to me that the two cases that need to be considered are (i) the u-v path intersects the path from the root to x (at some vertex y, not necessarily at the u-v path's highest point h); and (ii) it doesn't. We still need h to prove each case.

like image 199
j_random_hacker Avatar answered Sep 21 '22 04:09

j_random_hacker