Scribd
Upload
25 views1 page

Slide 11 - Proof of Prim Algorithm

The document presents a proof that Prim's algorithm produces an optimal solution, specifically a Minimum Spanning Tree (MST). It employs mathematical induction to demonstrate that at each step, the partial solution can be extended to an optimal solution, ultimately concluding that the final solution is also optimal. The proof highlights the algorithm's greedy approach of adding the cheapest edge while ensuring that this choice does not prevent the formation of an MST.

Uploaded by

Ashraf Bawer
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
25 views1 page

Slide 11 - Proof of Prim Algorithm

The document presents a proof that Prim's algorithm produces an optimal solution, specifically a Minimum Spanning Tree (MST). It employs mathematical induction to demonstrate that at each step, the partial solution can be extended to an optimal solution, ultimately concluding that the final solution is also optimal. The proof highlights the algorithm's greedy approach of adding the cheapest edge while ensuring that this choice does not prevent the formation of an MST.

Uploaded by

Ashraf Bawer
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 1

Firefox https://chat.deepseek.com/a/chat/s/cc9117b5-19b2-40d...

1. Goal of the Proof

We want to prove that the final solution SOLn−1 produced by Prim's algorithm is an optimal solution
(i.e., an MST). To do this, we show that:

�. At every step, the partial solution SOLh can be extended to an optimal solution.

�. The final solution SOLn−1 is itself an optimal solution.

2. Inductive Proof Structure

The proof uses induction on h, where h is the number of iterations completed by the algorithm.

Base Case (h = 0):

• At the start, SOL0 is the empty set (no edges have been added yet).

• The claim holds trivially because any optimal solution SOL∗ extends the empty set.

Inductive Step (h ≥ 0):

• Inductive Hypothesis: Assume that for some h ≥ 0, there exists an optimal solution SOL∗ that
extends SOLh .

• Goal: Show that the claim also holds for h + 1 (i.e., there exists an optimal solution SOL∗ that
extends SOLh+1 ).

3. Key Steps in the Inductive Step

Case 1: If SOL∗ already extends SOLh+1 , the claim holds trivially.

Case 2: If SOL∗ does not extend SOLh+1 :

• Let {u, v} be the edge added to SOLh in the (h + 1)-th iteration.

• Since {u, v} is not in SOL∗ , adding {u, v} to SOL∗ creates a cycle.

Why Does This Cycle Exist?

• SOL∗ is a spanning tree, so it already connects all nodes without cycles.


• Adding {u, v} to SOL∗ creates a cycle because there is already a path from u to v in SOL∗ .

Finding an Edge to Replace:

• Traverse the cycle starting from u until the first node xj that is not in Ch is found.

• Let {xj−1 , xj } be the edge in the cycle where:

◦ xj−1 ∈ Ch (in the current tree).


◦ / Ch (not yet in the tree).
xj ∈

Why {xj−1 , xj } is a Candidate for Replacement:

• {xj−1 , xj } is in SOL∗ but not in SOLh+1 .


• Since {u, v} was chosen as the minimum-weight edge connecting Ch to V − Ch , and {xj−1 , xj }
also connects Ch to V − Ch , it must be that:

p({xj−1 , xj }) ≥ p({u, v}).

Constructing a New Optimal Solution:

• Replace {xj−1 , xj } with {u, v} to form a new solution:

SOL# = (SOL∗ − {{xj−1 , xj }}) ∪ {{u, v}}.


• Since p({xj−1 , xj }) ≥ p({u, v}), the total weight of SOL# is not greater than that of SOL∗ .
• Therefore, SOL# is also an optimal solution and extends SOLh+1 .

4. Completing the Proof

• By induction, the final solution SOLn−1 produced by the algorithm is contained in an optimal solution
SOL∗ .
• Since both SOLn−1 and SOL∗ have exactly n − 1 edges (where n is the number of nodes), they
must be the same.

• Therefore, SOLn−1 is an MST, and Prim's algorithm is correct.

5. Intuitive Explanation

• Prim's algorithm grows the MST by always adding the cheapest edge that connects the current tree to
a new node.

• The proof ensures that this greedy choice does not exclude the possibility of finding an optimal
solution.

• By replacing edges in the optimal solution with the algorithm’s choices, we show that the algorithm’s
solution is also optimal.

1 of 1 3/17/25, 16:33

You might also like