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 Oct 4, 8:40 am, abhiram_n <[email protected]> wrote:
> I don't understand what you mean when you say "minimum among all the
> nodes in the graph".
>
> In any case, your definition ofcentreoftreelooks similar to the
> closeness centrality measure
> -http://www.faculty.ucr.edu/~hanneman/nettext/C10_Centrality.html#Clos...
>
> I doubt you can do it in O(N)...
>
> On Sep 29, 12:41 pm, jayapriya surendran <[email protected]> wrote:
>
> > 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)
> > The center of 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 the center(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?
--
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.
