[Help] How does Prim's algorithm prevent cycles in its output tree?
Difference between en22 and en23, changed 0 character(s)
Hello,↵
I have enrolled in my college's "Design and Analysis of Algorithms" course. Recently we were studying Greedy algorithms and proving their correctness. I have a doubt about the correctness proof of Prim's Algorithm. How do we prove that it does not form a cycle during its execution?  In the following snippet from our lecture [slides](https://drive.google.com/file/d/19Hzd8-Bwe--uxnMaLzNkpL9TfuNpkXqs/view?usp=sharing) (from Page No. 58, the MST part starts), it says:↵

**"No cycles ever get created in T. Why? Consider any iteration with current sets X and T. Suppose e gets added.**↵

**Key point: e is the first edge crossing (X, V-X) that gets added to T -> its addition can't create a cycle in T (by Lonely Cut**↵
**Corollary). QED!"**↵

For clarification:↵

1. T is the set of edges that Prim's algorithm has included to be a part of MST at any point in time during its execution.↵
 ↵
2. V is the set of all vertices of the input graph.↵

3. X is the set of vertices that are already included in the output tree.  ↵

4. V-X is the set of vertices which are not yet been included int the output tree.↵

Definition of a Cut of a graph: https://postimg.cc/SJsMFKJ7↵

Definition of Empty Cut Lemma: https://postimg.cc/JsQdQ8bV↵

Definition of Double crossing Lemma and Lonely Cut Corollary: https://postimg.cc/5QFR5Fmn↵

Algorithm/Pseudocode stated in lecture slides: https://postimg.cc/nsBrWdhJ↵

<a href="https://ibb.co/hVTkrRx"><img src="https://i.ibb.co/9WdJB9m/slide.png" alt="slide" border="0"></a>↵

How are we using the Lonely cut corollary in the part highlighted with yellow in the above image to prove that cycles won't form in the output spanning tree?  ↵

I have searched many resources on the internet for my doubts (including CodeForces blogs), but I am not able to find a reasonable explanation for the above question. Please help.↵

Thank you.↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en23 English RahulHarpal 2024-02-26 17:47:43 0 (published)
en22 English RahulHarpal 2024-02-26 17:47:00 0 (saved to drafts)
en21 English RahulHarpal 2024-02-26 17:29:40 0 (published)
en20 English RahulHarpal 2024-02-26 17:28:40 105
en19 English RahulHarpal 2024-02-26 17:27:32 85
en18 English RahulHarpal 2024-02-26 17:27:03 58
en17 English RahulHarpal 2024-02-26 17:24:13 79
en16 English RahulHarpal 2024-02-26 17:21:12 23
en15 English RahulHarpal 2024-02-26 17:20:38 2 Tiny change: 'ication:\n1. T is ' -> 'ication:\n\n1. T is '
en14 English RahulHarpal 2024-02-26 17:20:19 2 Tiny change: 'added.**\n**Key po' -> 'added.**\n\n**Key po'
en13 English RahulHarpal 2024-02-26 17:19:46 40 Tiny change: 'p=sharing), it says' -> 'p=sharing) (from Page No. 58, the MST part starts), it says'
en12 English RahulHarpal 2024-02-26 17:18:28 77
en11 English RahulHarpal 2024-02-26 17:17:19 115
en10 English RahulHarpal 2024-02-26 17:12:39 4
en9 English RahulHarpal 2024-02-26 17:12:20 75
en8 English RahulHarpal 2024-02-26 17:11:13 2 Tiny change: 'QED!"_**\nFor clar' -> 'QED!"_**\n\nFor clar'
en7 English RahulHarpal 2024-02-26 17:10:58 914
en6 English RahulHarpal 2024-02-26 16:57:55 185
en5 English RahulHarpal 2024-02-26 16:52:34 16
en4 English RahulHarpal 2024-02-26 16:52:09 7
en3 English RahulHarpal 2024-02-26 16:48:36 336
en2 English RahulHarpal 2024-02-26 16:40:53 3 Tiny change: 'e [slides]:\n(https://d' -> 'e [slides](https://d'
en1 English RahulHarpal 2024-02-26 16:40:07 490 Initial revision (saved to drafts)