Categories
Mastering Development

What theory should I be applying to these questions about minimum spanning trees?

Got a couple questions to answer from an assignment and I’m a little stuck on how to go about it, I can’t find any similar questions to reference too. I’m not sure what theories I should be applying. I don’t know how to mathematically prove them right/wrong.

Q: Consider a minimum spanning tree of a connected, weighted graph. If we remove an edge (u, v) of the MST, then we get two separate trees. Are these two trees the MSTs on their respective sets of nodes? Is the edge (u, v) a least-weight edge crossing between those two sets of nodes?

My assumed Answer: is yes, the two smaller sub tree’s would still be the MSTs and for the second part from what I have read on cut property, I would also say that yes, this edge would always be the lowest crossing edge that connects the two trees.

Q: Consider the following algorithm for finding an MST on a graph: split the nodes of the graph arbitrarily into two nearly equal-sided sets, and find an MST on each of those sets. Then connect the two MSTs with the least-cost edge between them. Would this algorithm always return an MST of the original graph?

My assumed answer (drew some graphs and attempted) is no, the MST from creating one MST from the graph wont always be the same as creating two smaller MSTs and combining them. I don’t know how to prove this.

Am I on the right track with these questions? Would love it if someone could provide any reading material on what theories I need to apply or help me understand how to answer the question correctly.

Leave a Reply

Your email address will not be published. Required fields are marked *