Please help with excerise 11.6 F eI ?Student\'s Form 1098 ?AccessUH-Universit ?
ID: 3701948 • Letter: P
Question
Please help with excerise 11.6
F eI ?Student's Form 1098 ?AccessUH-Universit ? Information-20185 € hw5.pdf f5502ccd-a-62ct Xbquadratic formula- LTX ? ? ? ? https://f5502ccd-a-62cb3a1a-s sites googlegroups.com site/gopa pandurangan/algbook.pdf?attachauh-ANOY7cp1covgXGezi8KzFK2z nS291RA Se7Xch ? Exercise 11.6. The diameter of a graph G = (V. E) is the maximum dis- tance among all pairs of vertices. That is ifd(u, v) is the distance between vertices u and u in ? , ??am(C)-maxu,uEV 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 treeT Exercise 11.7. Using two applications of DFS in a directed graph, give an algorithm to check if a given directed graph is strongly connected or not. Argue the correctness of your algorithm Type here to search 5:49 PM 4/6/2018 27Explanation / Answer
11.6)
i) We can easily argue that the diameter is always between two leaves, suppose lets say the any one end of the diameter is an internal node, then we can always extend this diameter by atleast one more node which gives the path longer than the diameter, so proof by contradiction the argument holds.
11.7)
Given a directed graph lets consider an arbitrary vertex v
1) Mark all vertices un reachable.
2) Do a dfs traversal from v and see if all the vertices can be reached, if not return false.
3) reverse all edges in the graph and mark all vertices unreachable.
4) do another dfs traversal from v again and see if all vertices can be reached, if reachable return true else false.
The argment here is in the first dfs traversal we find whether all vertices are reachable from v.
in the seconf traversal we find whether v can be reached from all vertices
if both are true then we have a path betweeen every pair of vertices, else it is not strongly connected.