MST: Are all safe edges, light edges? - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-09-18T03:21:54Z https://cs.stackexchange.com/feeds/question/74090 https://creativecommons.org/licenses/by-sa/4.0/rdf https://cs.stackexchange.com/q/74090 0 MST: Are all safe edges, light edges? Rajat Saxena https://cs.stackexchange.com/users/40138 2017-04-17T14:19:11Z 2017-04-17T15:36:27Z <p>Following are some definitions from CLRS:</p> <blockquote> <p><strong>DEFINITIONS</strong> :<br> 1. <strong>Cut (S ,V-S)</strong> : 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.<br> 2. <strong>Light edge</strong>: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.<br> 3. A cut <strong>Respects</strong> a set A of edges if no edge in A crosses the cut.<br> 4. <strong>Safe edge</strong> 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. </p> </blockquote> https://cs.stackexchange.com/questions/74090/-/74092#74092 3 Answer by Ashwin Ganesan for MST: Are all safe edges, light edges? Ashwin Ganesan https://cs.stackexchange.com/users/19607 2017-04-17T15:36:27Z 2017-04-17T15:36:27Z <p>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. </p> <p>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\}$. </p>