Please help with exercise 11.6 Exercise 11.6. The diameter of a graph G = (V,E,

Question

Please help with exercise 11.6

Exercise 11.6. The diameter of a graph G = (V,E, is the maximum ?is_ tance among all pairs of vertices. That is ifd(u, v) is the distance between vertices u and u in G, diam(C) = maxu,tEV d(u,v). The goal is to design an efficient algorithm to compute the diameter of a tree (i.e., the graph is a tree) and analyze the running time of the algorithm (i) Show that the distance determining the diameter will always be be- tween two leaves (ii) Describe and analyze an O(n) time algorithm to compute the diam eter of tree T

Explanation / Answer

Solution:

i)

Suppose we have a graph G(V, E) and there are |V| vertices and |E| edges in the graph G.

We are talking about the diameter of a tree, this means that G is a tree, which means it doesn't contain any cycles.

Suppose d1, d2, d3, ....di is representing distance from one vertex to another.

then if di is the distance from a leave node to a non leave node, then we can say

di + 1 will be the distance between two leave nodes.

and, we know that

di+1> di

This proves that the largest distance in the tree will be between two leaf nodes.

ii)

The algorithm to find diameter is given below:

Algorithm:

I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---