the question is clear..you draw the sample test case and work out ..
you will understand
1
/ / \
4 2 3
/\
5 6
....here from node 2 the maximum cost to reach any node 'i' is 2 and
minimum is 1
...so M(2) = max(1,2)=2..the same is the case for node 1 also
...if you consider node 4 , to reach 6 , cost is 3....similar is
applicable for other nodes....
....therefore centre = min(M(1..6)) = 1 and 2.
...hope u got me!!
On Wed, Jul 27, 2011 at 2:08 AM, siva viknesh <[email protected]>wrote:
>
>
>
> ---------- Forwarded message ----------
> From: jayapriya surendran <[email protected]>
> Date: Sep 29 2010, 9:41 pm
> Subject: Directi question-centre of the tree
> To: Algorithm Geeks
>
>
> In graph theory, atreeis defined as a graph on N nodes,and (N-1)
> un-directed edges such that there are no cycles in the graph.Each node
> has a single unique path to every other node.
> Let D(u,v) be the number of edges in the unique path from node 'u' to
> node 'v' (or from node 'v' to 'u' since the edges are
> un-directed).D(u,u) is 0 for all nodes 'u'.
> M(u)=MAX(D(u,i):for all nodes i)
> Thecenterof atreeis the node (or nodes) 'u',for which M(u) is
> minimum among all the nodes in the graph.
> You'll be given a graph which has N nodes (1<=N<=20).The nodes are
> labeled 1,2,3,..N.You will be provided with N-1 edges in the form of
> "a b" pairs where 1<=a,b<=N.No edge will be repeated.You can assume
> that the edges are specified such that the graph is a validtreeas
> defined above.
> Output the node labels of thecenter(or centers) of thetree.
> Sample Input:
> 6(value of N)
> 1 3 (edges)
> 1 4
> 1 2
> 2 5
> 2 6
>
> Sample Output
> 1
> 2
> Expected:O(N) complexity algo
> can anyone plz help me out with O(N) algo?
>
--
Regards,
$iva
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
