RahulHarpal's blog

By RahulHarpal, history, 8 months ago, In English

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.

  • Vote: I like it
  • -3
  • Vote: I do not like it

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by RahulHarpal (previous revision, new revision, compare).

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by RahulHarpal (previous revision, new revision, compare).

»
8 months ago, # |
  Vote: I like it +12 Vote: I do not like it

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:

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

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      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.

      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        Now I get it. Thanks a lot for helping out. This means a lot :)