1
$\begingroup$

The cut property stated in terms of Theorem 23.1 in Section 23.1 of CLRS (2nd edition) is as follows.

Theorem 23.1 Let $G = (V, E)$ be a connected, undirected graph with a real-valued weight function $w$ defined on $E$. Let $A$ be a subset of $E$ that is included in some minimum spanning tree for $G$, let $(S, V-S)$ be any cut of $G$ that respect $A$ (emphasis added), and let $(u,v)$ be a light edge crossing $(S,V-S)$. Then, edge $(u,v)$ is safe for $A$.

Why does this theorem require that the cut $(S,V-S)$ respect $A$? How is this requirement used in the correctness proof? I do not see what would fail if the requirement was removed.


Some Definitions:

  • Cut: A cut $(S, V-S)$ of an undirected graph $G=(V,E)$ is a partition of $V$.
  • Cross: An edge $(u,v) \in E$ crosses the cut $(S,V-S)$ if one of its endpoints is in $S$ and the other is in $V-S$.
  • Respect: A cut respects a set $A$ of edges if no edge in $A$ crosses the cut.
  • Light edge: An edge is a light edge crossing a cut if its weight is the minimum of any edge crossing the cut.
$\endgroup$
1
$\begingroup$

I don't have the book handy. I assume that

  1. "safe" means that $(u,v)$ can be added to $A$ and we get another subset of a minimal spanning tree of $G$, and
  2. the goal is a correctness proof of Prim's algorithm¹.

Now, say the cut did not "respect" $A$. That means that there already is an edge in $A$ that crosses it. By choosing a second edge from that cut -- which may happen even with pairwise distinct weights! -- we may introduce a cycle and lose the tree property.

enter image description here

By requiring that the cut "respects" $A$ we know that $A \subseteq S$ and we can not introduce a cycle².

The assumptions of this theorem may be stronger than strictly necessary -- as long as we do not create a cycle, we do not per se need to care about other edges in the cut -- but we can build an algorithm around them, so the theorem is a convenient way to ensure its correctness.


  1. Note how the theorem directly implies that fact since Prim's algorithm maintains such a cut and chooses light edges from it to grow the tree.
  2. In the algorithm, we'll always have $A=S$.
$\endgroup$
  • $\begingroup$ Thanks. I agree with your opinion that cycle may be produced if the "respect" requirement is not satisfied. However, how could a cycle be produced when weights are pairwise distinct? If so, the heaviest edge in the cycle (which is not the edge$(u,v)$ because it is not the lightest edge across the cut) cannot be in any MST, and thus cannot be in $A$, contradicting the assumption that $A$ is a subset of $E$ that is included in some MST. $\endgroup$ – hengxin May 24 '16 at 12:28
  • $\begingroup$ The other edge of $u$ may have been chosen after that other one that already crosses the cut -- let's call it $e$ -- so we never compared $e$ with $(u,v)$. So the scenario can also happen with pairwise distinct weights. $\endgroup$ – Raphael May 24 '16 at 12:40
  • $\begingroup$ Do you mean that the lightest edge $e$ is chosen from the set of edges across the cut except those that are in $A$ but do not respect the cut? For example, suppose that $e' = (x,y) \in A$ with $w(e') = 2$ does not respect the cut $C$ and that $e'' = (x, z) \notin A$ with $w(e'') = 5$ is the only edge across the cut $C$ besides $e'$. Then the lightest edge across the cut at this stage is $e''$ instead of $e'$. In this case, $A \cup \{ e'' \}$ may contain a cycle (while $A \cup \{ e' \} = A$). $\endgroup$ – hengxin May 24 '16 at 13:01
0
$\begingroup$

Besides the effect of "avoiding cycles" pointed out by @Raphael, the "respect" requirement in the cut property guarantees that $A \cup \{ (u,v) \}$ is included in the minimum spanning tree $T' = T - \{ (x,y) \} \cup \{ (u,v) \}$ constructed in the correctness proof.

CLRS-cut-property-correctness-proof

Since $A \subseteq T$, to ensure that $A \cup \{ (u,v) \} \subseteq T' = T - \{ (x,y) \} \cup \{ (u,v) \}$, it requires $\{ (x,y) \} \notin A$; see the figure above (Fig 23.3 in CLRS).

$(x,y) \notin A$ holds because $(x,y)$ is chosen as the edge that is on the unique path from $u$ to $v$ in $T$ and crosses the cut $(S, V-S)$ and that $A$ respects the cut $(S,V-S)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.