Optimizing Minimum Spanning Trees Under Constraints

00:00 5 marks

Consider a connected graph representing a network with several nodes and weighted edges, where some edges are more expensive and a budget constraint limits the total cost. The goal is to construct a Minimum Spanning Tree (MST) that minimizes the overall cost while respecting the budget limit.

Part (a): Given a graph with 8 nodes and 12 edges with specified weights, explain how you would construct an MST under a budget limit of \(C\) dollars.

Part (b): After constructing the MST, suppose that one edge’s cost increases by 20%, describe the steps to adjust the MST while keeping the network connected at minimal extra cost.

Part a

8 minutes 3 marks

Question

Explain in detail how you would construct a Minimum Spanning Tree (MST) for a network graph with 8 nodes and 12 edges, given that the total cost must not exceed a budget \(C\). Describe how standard algorithms must be adapted to include this budget constraint.

Hint Hint

Hint

Discuss applying Kruskal’s or Prim’s algorithm with a supplementary check for the cumulative cost at each step.

Answer Answer
Mark Scheme Mark Scheme
Explanation Explanation
Formula Booklet

Answer Answer

Complete Answer

By modifying Kruskal’s algorithm to include a budget check at each addition, one can construct an MST that stays within \(C\). Edges are added in increasing order of weight, and if adding an edge exceeds the budget, it is skipped in favor of the next cheapest edge.

Mark Scheme Mark Scheme

Answer Explanation Answer Explanation

Formula Booklet

Part b

7 minutes 2 marks

Question

After constructing the MST in part (a), suppose one edge in the MST has its cost increased by 20%. Describe the steps required to adjust the MST while minimizing extra cost and ensuring the network remains connected.

Hint Hint

Hint

Consider verifying if the updated edge still belongs to the MST and whether a substitution is needed.

Answer Answer
Mark Scheme Mark Scheme
Explanation Explanation
Formula Booklet

Answer Answer

Complete Answer

Identify if the increased cost edge is still optimal. If not, remove it and reapply the MST algorithm on the modified graph to find a replacement edge that maintains connectivity at minimal extra cost.

Mark Scheme Mark Scheme

Answer Explanation Answer Explanation

Formula Booklet