[Help] How does Prim's algorithm prevent cycles in its output tree?

Revision en21, by RahulHarpal, 2024-02-26 17:29:40

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 (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

slide

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.

Tags graphs, minimun spanning tree, greedy

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)