Page 1 of 1
Problem 3. [25 pts] [Centroid] The centroid of a tree is a node that, if removed, splits the tree into connected compone
Posted: Thu May 05, 2022 12:55 pm
by answerhappygod
- Problem 3 25 Pts Centroid The Centroid Of A Tree Is A Node That If Removed Splits The Tree Into Connected Compone 1 (54.46 KiB) Viewed 30 times
Problem 3. [25 pts] [Centroid] The centroid of a tree is a node that, if removed, splits the tree into connected components each of size no greater than V/2. The following algorithm can be used to find the centroid of a tree T: 1. Let v be an arbitrary vertex of T 2. Let {C₁, C₂,..., C₁} be the connected components of T - {v} 3. Let Ck be the component of maximum size among C₁, 1 ≤ i ≤l 4. If Ck ≤ V/2, return v and terminate 5. Else, let v' be the member of Ck that is a neighbour of v 6. Go back to step 2, with v = v' Prove that the algorithm above always terminates and thus, finds the centroid of the tree.