0
$\begingroup$

Following are some definitions from CLRS:

DEFINITIONS :
1. Cut (S ,V-S) : of an undirected graph G = (V,E) is a partition of V(as defined in CLRS Book) .You can think it as a line that divides graph into two disjoint sets of vertices on its either side.
2. Light edge:Any edge crossing a cut is light edge if its weight is the minimum of all the edge crossing the cut.Light edge is defined with respect to a particular Cut.
3. A cut Respects a set A of edges if no edge in A crosses the cut.
4. Safe edge is the edge which we can add to MST without any violation of MST's property.These are those edges which are the part of final MST.

$\endgroup$
  • 1
    $\begingroup$ Please elaborate on what your question is. The one in the title? What are your thoughts? The definitions seem quite clear to me. (Even though the one for "safe" depends on a cut without explicitly saying so, and is somewhat wrong in that not all safe edges are going to be part of the final MST.) Try to think about scenarios where you have multiple light and safe edges, respectively. Are the sets equal? Is one included in the other? Is their intersection empty? Are they incomparable? $\endgroup$ – Raphael Apr 17 '17 at 14:42
  • $\begingroup$ @Raphael I am banging my head with this "Professor Sabatier" problem from CLRS. I hope you can related now. I saw your comment on that question. $\endgroup$ – Rajat Saxena Apr 17 '17 at 20:09
3
$\begingroup$

Yes, all safe edges (edges which are part of some MST) must be the lightest edge for some partition $(S, V-S)$ of the graph. For if $e=uv$ is a safe edge, it is part of some MST $T$, and $T-e$ partitions the vertex set of the graph into two parts $(S, V-S)$, where $u \in S$ and $v \in V-S$. If $e$ was not a lightest edge between $S$ and $V-S$, then $e$ can be removed from $T$ and replaced with a lighter edge $f$, giving a tree $T-e+f$ with a smaller weight than $T$, contradicting the fact that $T$ is an MST.

As a concrete example, suppose $G$ is the path graph on vertex set $\{a,b,c\}$ and edge set $\{ab, bc\}$, with the edges $ab$ and $bc$ having weights $1$ and $2$, respectively. Then, edge $bc$ is not the lightest edge available, but it is a safe edge to add first and it is the lightest edge between $S$ and $V-S$ if we take $S = \{a,b\}$.

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