Question

Network Structures

1. The length of a path in a simple graph is the number of edges on it. The distance between two nodes of a simple graph is the length of the shortest path connecting them. The diameter of a graph is the maximum distance between a pair of nodes. Let $v$₁ , . . . , $v$_$n$be all the nodes of a graph G, and let dist_G($v$_$i$,  $v$_$j$ ) be the distance between $v$_$i$and $v$_$j$in this graph G. Then the average distance between nodes of G is the number

Answer 1

The distance between the two nodes d(x,y) x and y in the tree is the number of edges in the shortest path between them , The longest path in tree T is either in one of the subtrees of the root x, or it is a path from a leaf of one subtree to x, and a path from x to a leaf in the other subtree, And the diameter is recursively computed as,

diameter(x) = max(diameter(leftsubtree(x)), diameter(rightsubtree(x)), height(leftsubtree(x)) + height(rightsubtree(x)) + 2).

Hence the pseudocode of the recursive algorithm that returns both the diameter and height of the tree rooted at a given node x is as given below :

(int,int) = Diameter(x) { // It returns the (diameter(x) , height(x))

if (x=NIL)

return(-1,-1)

(p,q) = Diameter(leftsub(x))

(r,s) = Diameter(rightsub(x))

v = 1 + max(q,r)

u = max(p,r,q+s+2)

return(u,v) }

If the time complexity is given as T(n) for the tree T having n nodes , The recurrence relation is derived as ,

T(n) <= max {T(i) , T(n − i − 1) : 0 <= i <= n − 1} + c, T(0) = c.

By using induction , T(n) <= cn , Hence T(n) ∈ O(n) .