Could you help with Question 3: algorithm/pseudocode and time complexity if poss

Question

Could you help with Question 3: algorithm/pseudocode and time complexity if possible?

Question 1: Let G be an undirected graph. Write an algorithm that returns the set of all vertices whose degrees are strictly smaller than the degrees of all their neighbors. Question 2: Let T(V, E1) and T(V, E2) be two different spanning tree. Show that there is an edge ei E T, and an edge e2 in T2, so that T? + {e2)-{e1} and Ta + {el)-(e2} are still spanning trees. Question 3: The diameter in a tree is the length of the longest path between any two vertices in the tree. Namely, if dist(u, v) maxz,u[dist(z, w)) then dist(u, v) is the length of the unique paths between u and v in the tree.. Give an algorithm that computes the diameter of a tree. Remark: Do not use things that were not taught in this course but rather in previous courses Question 4: 1. Consider a tree T(VE) with n > 2 vertices. Show that ?veT deg(v) 2n-1 2. Say that we are given n numbers d1, d2, . . . , dn so that ?, 2n-1. Show that at least two of the numbers have value 1 3. Prove that at least one value of the dy above is at least 2 that

Explanation / Answer

SOLUTION:-(3):- The diameter in a tree is the length of the longest path between any 2 vertices in the tree.

In order to find the diameter in a tree, We will find MAX(Left_SubTree_Diameter, Right_SubTree_Diameter,LongestPath_TwoVertices via Root). We will use recursion to find the diameter of Left & Right Subtrees and for calculate the longest path we will use 1+ Left_SubTree_Height + Right_SubTree_Height.

Algorithm:-

STEP-1:- First of all, we will calculate the Left_SubTree Height

STEP-2:- Then we will calculate the Right_SubTree Height.

STEP-3:- We will calculate the diameter of Left_SubTree

STEP-4:- We will calculate the diameter of Right_SubTree

STEP-5:- We will return the Maximum value of {  Left_SubTree_Diameter , Right_SubTree_Diameter , LongestPath_TwoVertices via Root }

Time Complexity:- Finding the height of a Left and Right subtrees individually via Tree iteration from upward to downward along with finding the diameter by using recursion so Time Complexity is O(N2).

=======================================================================================

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---