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:
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.
V is the set of all vertices of the input graph.
X is the set of vertices that are already included in the output tree.
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
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.
Auto comment: topic has been updated by RahulHarpal (previous revision, new revision, compare).
Auto comment: topic has been updated by RahulHarpal (previous revision, new revision, compare).
Instead of $$$V - X$$$ I will write $$$V\setminus X$$$ as I'm more used to this notation.
Lemma 1: If a set of edges $$$T$$$ doesn't have cycles, and an edge $$$e$$$ is not in any cycle in $$$T\cup \{e\}$$$, then $$$T\cup \{e\}$$$ doesn't have any cycles.
Proof by contradiction:
Suppose that $$$T\cup \{e\}$$$ has a cycle. This cycle cannot contain $$$e$$$ as we know that $$$e$$$ is not in any cycle in $$$T\cup \{e\}$$$. Thus, there must be a cycle in $$$T\cup \{e\}$$$ not containing $$$e$$$. We can now remove $$$e$$$ from $$$T\cup \{e\}$$$ and get $$$T$$$, which also must contain this cycle, as we didn't touch any edges on this cycle. This is a contradiction, since we know that $$$T$$$ doesn't have cycles. $$$\square$$$
We will show that $$$T$$$ never has cycles using induction.
Base Case: In the beginning, when $$$T$$$ is empty, $$$T$$$ has no cycles.
Induction step: Let $$$T$$$ be the set of edges before our current step of the algorithm. By the induction hypothesis, $$$T$$$ has no cycles. Let $$$T' = T\cup \{e\}$$$ be the set of edges after the current step of the algorithm. We want to show that $$$T'$$$ has no cycles.
Consider one step of the algorithm. By definition, Prim's algorithm will choose an edge $$$e$$$ such that one endpoint of $$$e$$$ is in $$$X$$$ and the other is in $$$V\setminus X$$$. $$$(X, V\setminus X)$$$ is a cut of the graph by definition.
Since $$$V\setminus X$$$ is the set of vertices not yet used in the tree, there are no edges in $$$T$$$ connecting $$$X$$$ and $$$V\setminus X$$$. This means that $$$e$$$ is the only edge in $$$T'$$$ connecting the two parts of the cut $$$(X, V\setminus X)$$$. Thus, by the Lonely Cut Corollary, $$$e$$$ is not in any cycle in $$$T'$$$. Therefore, by Lemma 1, $$$T'$$$ doesn't have any cycles. $$$\square$$$
This means that e is the only edge in T′ connecting the two parts of the cut (X, V∖X) .I have a doubt about this line. Wouldn't there be a case that there is more than one edge connecting $$$X$$$ and $$$V\setminus X$$$ before selecting one of them with smallest weight and adding it to $$$T'$$$ ? In this case, the lonely cut corollary would not be applicable. Am I thinking in the right direction, or am I missing something?
That never happens.
We start with the fact that there are no edges in $$$T$$$ connecting $$$X$$$ and $$$V\setminus X$$$. This follows directly from the fact that $$$X$$$ defined as the set of all vertices that are currently connected by any edge. This means that there is no edge that has its endpoint in $$$V\setminus X$$$ and thus, no edge between $$$X$$$ and $$$V\setminus X$$$.
Now, consider the tree $$$T' = T\cup \{e\}$$$. How is $$$T'$$$ different from $$$T$$$? $$$T'$$$ is otherwise identical to $$$T$$$, but $$$T'$$$ has one extra edge: $$$e$$$.
Let's for a moment assume the case you mentioned has happened: $$$T'$$$ has two (or more) edges between $$$X$$$ and $$$V\setminus X$$$. This means that we went from $$$T$$$ having $$$0$$$ edges between $$$X$$$ and $$$V\setminus X$$$ to $$$T'$$$ having $$$2$$$ edges between $$$X$$$ and $$$V\setminus X$$$, just by adding $$$1$$$ new edge and without changing anything else. That just isn't possible.
Now I get it. Thanks a lot for helping out. This means a lot :)