Each of the following two algorithms takes a connected graph and a weight function as input and returns a set of edges T. For each algorithm, either prove (use logical arguments) or disprove ( give a counter example) that T is a minimum spanning tree. Describe (no pseudo code) the most efficient implementation of each algorithm, whether or not it computes a minimum spanning tree. (1) Maybe-MST-A(G, w) T = ∅ for each edge e, taken in arbitrary order T = T ∪ {e} if T has a cycle c let e' be the maximum weight edge in c T = T − {e'} return T (2) Maybe-MST-B(G, w) sort the edges into non-increasing order of edge weight w T = E for each edge e, taken in non-increasing order by weight if T – {e} is a connected graph T = T – {e} return T
Each of the following two algorithms takes a connected graph and a weight function as input and
returns a set of edges T. For each
give a counter example) that T is a minimum spanning tree. Describe (no pseudo code) the most
efficient implementation of each algorithm, whether or not it computes a minimum spanning tree.
(1)
Maybe-MST-A(G, w)
T = ∅
for each edge e, taken in arbitrary order
T = T ∪ {e}
if T has a cycle c
let e' be the maximum weight edge in c
T = T − {e'}
return T
(2)
Maybe-MST-B(G, w)
sort the edges into non-increasing order of edge weight w
T = E
for each edge e, taken in non-increasing order by weight
if T – {e} is a connected graph
T = T – {e}
return T
Trending now
This is a popular solution!
Step by step
Solved in 3 steps
