Minimally Invasive Treatment and Minimum Spanning Tree

Overview of Minimal Spanning Tree (MST)

• Definition of Minimally Invasive Treatment:
  • Starts from one vertex and progressively grows the rest of the tree.
  • Key objective: Achieve a total weight of the tree that is minimal.

Prim's Algorithm for MST Construction

• Initialization:

  • Begin with a rich set (initially the starting vertex, denoted as zero here).
  • The unreached set contains all other vertices (for n vertices, this will include nodes 1 to n-1).

• Process Overview:

  • Continue looping until the unreached set is empty.
  • Identify edges between the rich set and unreached set.

Steps in the Algorithm

1. Identify Minimum Edge:

   • Find edge E with the smallest weight connecting rich set (X) to unreached set (Y).
   • Ensure Y is not in the rich set to avoid cycles.

2. Update Sets:

   • Add the found edge E to the MST.
   • Move Y from the unreached set to the rich set.

Example of Building MST

• Initial Setup:
  • Graph vertices: 0, 1, 2, 3, 4, 5, 6, 7.
  • Starting from vertex 0, the edges and weights are defined.

Steps Illustrated

• Step 1:

  • Rich set: {0}
  • Unreached set: {1, 2, 3, 4, 5, 6, 7}
  • Minimum edge identified: (0, 4) with weight 5.
  • Update: Rich set becomes {0, 4}, Unreached set becomes {1, 2, 3, 5, 6, 7}.

• Step 2:

  • Minimum edge identified: (4, 7) with weight 5.
  • Update: Rich set becomes {0, 4, 7}, Unreached set becomes {1, 2, 3, 5, 6}.

• Step 3:

  • Minimum edge identified: (7, 6) with weight 5.
  • Update: Rich set becomes {0, 4, 7, 6}, Unreached set becomes {1, 2, 3, 5}.

• Subsequent Steps:

  • Continue identifying edges from the rich set to unreached set:
  • (6, 1) with weight 1, update Rich set to {0, 4, 7, 6, 1}.
  • (6, 5) with weight 3, update Rich set to {0, 4, 7, 6, 1, 5}.
  • (5, 2) with weight 5, and finally, add (2, 3) completing the MST.

Conclusion

• Result:
  • The process ultimately creates a minimum spanning tree which allows reaching all nodes from the starting vertex (0) with minimal total cost.
• Key Insight:
  • The minimum spanning tree efficiently connects all nodes with the least weight, minimizing expenditure in traversal costs.