1
$\begingroup$

From CLRS (3rd edition), I came have this question on page 626:

Given these definitions from the text,

DEFINITIONS: Given an undirected graph G = (V,E),

1. A CUT (S ,V-S) of G is a partition of V,

2. A LIGHT EDGE over a cut is any edge crossing the cut with a weight smaller than or equal to any other edge crossing that cut,

3. A cut RESPECTS a set A of edges if no edge in A crosses the cut.

In every example in the text, the set A is coincident with one of the partitions of the cut but I cannot see why this must be. Given an arbitrary new vertex v', it could be added to the partition that contains A and no edge from v' to A would cross the cut. The definition of respects says that a cut cannot divide A, not that A must define the partition.

There is clearly something here I missed since that does not seem consistent with the theorems. Can anyone point out my error?

+++++++++++++++

Amendment. Thanks for the help. I also now realize that Theorem 23.1 only says that a light-edge is a safe edge but not that such a cut is guaranteed to find every safe edge since some edges may have both vertices in the same partition as A. I see in GENERIC-MST(G) that line 3 only says to find an edge. It is not until Kruskal or Prim algorithms that the method by which we find this edge is explained and neither depend upon the partition being coincident with the set of vertices defined by the set of edges A.

I find it interesting that in Kleinberg Tardos that they take a different approach and define a cut property (4.17, pg 145) that avoids this (what I find awkward) development of the ideas.

$\endgroup$
  • 1
    $\begingroup$ It seems that you understand the definition and that it just happens that all the examples happen to have $A$ defining the partition (i.e., $A = E\cap S^2$). By the definition you quote, the cut $(S, V\setminus S)$ respects any set $A\subseteq E \setminus (S\times (V\setminus S))$. $\endgroup$ – David Richerby Sep 25 '13 at 22:07
1
$\begingroup$

One mistake you're making with the statement:

In every example in the text, the set A is coincident with one of the partitions of the cut but I cannot see why this must be.

$A$ is a set of edges, while a cut is a partition of vertices: $(S, V - S)$.

Suppose, as you say, that $A$ is a subset of the set $\{(u,v): u,v \in S\}$, then $A$ respects the cut $(S,V-S)$ because none of the edges with both ends in $S$ will cross the cut.

If you add a new vertex $v'$ into $S$, and some other edges from $v'$ to other vertices $x$ in $S$, then $A$ can include ALL of these edges and still respect the cut $(S,V-S)$ because both $v'$ and the other edges from $v'$ are in $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.