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

Правка en19, от RahulHarpal, 2024-02-26 17:27:32

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

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)