@Everyone: Wladimir has posted the correct solution to the problem and it is
an O(N) bottom up solution.
*The original solution:*
On Wednesday, 6 October 2010 21:10:40 UTC+5:30, wladimirufc wrote:
>
> Find the leaf of tree then put all leaf in a queue.
>
> While queue not empty:
> remove u from queue
> remove u of tree
> if some v adjacent a u become leaf
> insert v in queue
>
> the last vertice is the center of the tree
>
Let me expand on the solution for a bit.
*Definition:*
1. For the purposes of this solution, a *leaf node* is defined as a node
having only one edge connected to it.
*Visualization:*
Think about the tree being flattened onto a table and laid out in a circular
fashion.
eg.
1
/ / \ \
4 2 3 7
/\
5 6
\
8
can be laid out as:
4 3
\ /
1 -- 7
|
2
/ \
5 6
\
8
Now, wrap a rubber band around the layout and start tightening it.
At every stage, you'll be getting rid of nodes with only a single edge (so
called leaf nodes)
Stop when you end up with either a single node or a pair of nodes connected
by an edge.
*For example, *
remove leaf nodes as:
Step 1: 8,5,4,3,7
Step 2: 6,1 (Note: 2 is not removed as it has 2 connecting edges)
The center of the tree is thus 2.
*Proof of correctness:*
Let T be a tree for which D(u, v) = D(v, u) = C is the maximum possible.
It is obvious that both u and v must be leaf nodes since u..v is a diameter
of the graph.
Also, any non-leaf node w on the path u...v has M(w) < M(u) or M(v) since
D(u, v) = D(u, w) + D(w, v)
Consider all such diameters of the tree graph T.
Let the pairs (u1, v1), (u2, v2)... (uk, vk) represent the nodes of a
diameter of the graph.
Consider the subgraph G' = G - {u1, u2, ..., uk, v1, v2, .. vk}
The diameter of G' is C-2. The center(s) of the graph is/are unchanged.*
Applying this reduction multiple times, any tree's undirected graph
representation
can be reduced to a graph of diameter 0 or 1.
*Base cases: *
Graph of diameter 0: The node itself is the center.
Graph of diameter 1: The pair of connected nodes are the center of the
graph.
*Note:* The connectedness of the graph is maintained at every stage of the
reduction process as no bridge nodes are ever removed.
** Proof of reduction of diameter by 2:*
Let us assume that the diameter of G' is C-1 with the nodes making up the
diameter being (p, q).
Therefore atleast one of p and q is a leaf node in G.
But since we removed all the leaf nodes in the reduction process, both p and
q must be internal nodes.
Hence the diameter of G' cannot be C-1.
By removing the 2 end nodes on a diameter of G, we are assured that there
exists a path of length C-2 in G'.
Since the diameter is an integral value and G' cannot have a diameter >=
C-1, therefore the diameter
of G' is C-2.
** Proof of non-changing nature of the center:* *(slightly hand-wavy, I
would appreciate slightly more formality)*
Since the reduced graph G' has all the nodes of the original diameter
(except the leaf nodes) present and the
diameter of the graph G is also present as one of the diameters of graph G',
the center of the graph is
still present in G'.
Taking all these parts together proves the result and also provides the
algorithm for obtaining the result
in O(N).
Hope you enjoyed it!
--
DK
http://gplus.to/divyekapoor
http://twitter.com/divyekapoor
http://www.divye.in
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/dBlYluR4wvIJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
