[Help] How does Prim's algorithm prevent cycles in the MST?

Правка en15, от RahulHarpal, 2024-02-26 17:20:38

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 MST.

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

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.

Теги graphs, minimun spanning tree, greedy

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en23 Английский RahulHarpal 2024-02-26 17:47:43 0 (published)
en22 Английский RahulHarpal 2024-02-26 17:47:00 0 (saved to drafts)
en21 Английский RahulHarpal 2024-02-26 17:29:40 0 (published)
en20 Английский RahulHarpal 2024-02-26 17:28:40 105
en19 Английский RahulHarpal 2024-02-26 17:27:32 85
en18 Английский RahulHarpal 2024-02-26 17:27:03 58
en17 Английский RahulHarpal 2024-02-26 17:24:13 79
en16 Английский RahulHarpal 2024-02-26 17:21:12 23
en15 Английский RahulHarpal 2024-02-26 17:20:38 2 Tiny change: 'ication:\n1. T is ' -> 'ication:\n\n1. T is '
en14 Английский RahulHarpal 2024-02-26 17:20:19 2 Tiny change: 'added.**\n**Key po' -> 'added.**\n\n**Key po'
en13 Английский 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 Английский RahulHarpal 2024-02-26 17:18:28 77
en11 Английский RahulHarpal 2024-02-26 17:17:19 115
en10 Английский RahulHarpal 2024-02-26 17:12:39 4
en9 Английский RahulHarpal 2024-02-26 17:12:20 75
en8 Английский RahulHarpal 2024-02-26 17:11:13 2 Tiny change: 'QED!"_**\nFor clar' -> 'QED!"_**\n\nFor clar'
en7 Английский RahulHarpal 2024-02-26 17:10:58 914
en6 Английский RahulHarpal 2024-02-26 16:57:55 185
en5 Английский RahulHarpal 2024-02-26 16:52:34 16
en4 Английский RahulHarpal 2024-02-26 16:52:09 7
en3 Английский RahulHarpal 2024-02-26 16:48:36 336
en2 Английский RahulHarpal 2024-02-26 16:40:53 3 Tiny change: 'e [slides]:\n(https://d' -> 'e [slides](https://d'
en1 Английский RahulHarpal 2024-02-26 16:40:07 490 Initial revision (saved to drafts)