Consider a possible DIVIDE-AND-CONQUER approach to finding a minimal spanning tr
ID: 3748958 • Letter: C
Question
Consider a possible DIVIDE-AND-CONQUER approach to finding a minimal spanning tree in a connected, weighted, graph G. Suppose that we recursively divide the vertices of G into two disjoint subsets V1 and V2. We then find a minimal spanning tree T1 for V1 and a minimal spanning
tree T2 for V2. Finally we find a minimum weight edge e connecting T1 and T2. We then let T be the graph obtained by combining T1, T2, and e.
(a) Is T always a spanning tree?
(b) If T is a spanning tree, is it always a minimal spanning tree?
Explanation / Answer
It's correct that T will always be a spanning tree but you won't always get a minimal spanning tree by just connecting T1 and T2. Please find the following example:
Let us consider the graph given below G(A,B,C,D,H,G,F,E)
A B C D
10
10
5
10
10
10 10
E 10 F 7 G 10 H
Suppose Edge (B,C) has cost 5 and (F,G) has cost 7, all other edges have cost 10.
Then you divide it in T1(A,B,E,F)
and T2 (C,D,H,G)
so the minimum spanning tree for T1 and T2 will be cost you 30 each.
If you now connect them with the minimal possible edge you get a spanning tree with cost 65:
i.e. T=T1+T2 (you have to choose from BC or FG to combine those subgraphs, so we will have to take BC as it costs 5)
so you can see T is obviously a spanning tree but it is not a minimum spanning as tree. As in our case the Minimum spanning tree will cost you 62
i.e. G(A,B,C,D,H,G,F,E) (10+5+10+10+10+7+10=62)
so 62<65 . so T will be Minimal spanning tree only if you have same cost for all the edges. if it varies then it won't be be a MST.
10
10
5
10
10
10 10
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.