0
$\begingroup$

I ran into an interview two days ago and came across one strange definition of safe edge.

We are given an undirected weighted Graph $G = (V,E)$ with all distinct edge weights. Assume that the graph is connected.

Safe Edge Definition: if an edge $e \in E$ is not contained in any cycle, we called it a safe edge

Following is a theorem based on the above definition.

Theorem: All the safe edges must be in Minimum Spanning Tree (MST).

Please compare the definition of a "safe edge" on this interview with the classical definition of safe edge at all courses like here: MAIN SAFE EDGE THEOREM.

$\endgroup$
1
  • 2
    $\begingroup$ Please do not delete your question after you have already received an answer. Part of our mission is to build up an archive of high-quality questions and answers that will be useful not only to you but also to others in the future. Deleting it after you have already received answers is not fair to answerers. See cs.stackexchange.com/help/…. $\endgroup$
    – D.W.
    Jan 11 at 22:35
5
$\begingroup$

They are two different definitions. The interview definition calls a safe edge one that is not part of any cycle and therefore cannot be removed from $G$ without disconnecting it, thus changing the resulting MST. Notice that this definition depends solely on the chosen edge and on $G$. Notice also that it does not depend on the edge weights in any way.

The definition in the notes defines a safe edge $e$ as one that can safely be added to a subgraph $A$ of $G$ so that $A + e$ is a partial MST of $G$. In this case $A$ is probably thought to already be a partial MST of $G$, since otherwise no edge would be safe, although this is not formally required. Notice that this definition depends on the particular choice of $A$ and on the edge weights of $G$.

As an example, let $G$ be a cycle on $n$ nodes, where the $n$ edges have weights $1, \dots, n$. None of these edges is safe according to the interview definition. If $A$ is the empty graph then all edges except for the one of weight $n$ are safe w.r.t. the definition in the notes. If $A$ is the subgraph containing the edge of weight $n$ then no edge is safe w.r.t. the definition in the notes.

$\endgroup$
2
  • $\begingroup$ Yes, the interview definition is defining bridges, or cut-edges. And yes, all bridges of a graph $G$ must belong to all MSTs of $G$. $\endgroup$
    – Steven
    Jan 11 at 20:46
  • $\begingroup$ I noticed that in a previous edit you were asking for a proof. Let $e=(u,v)$ be an edge of $G$. If there is a MST $T$ of $G$ such $e \not\in T$, then let $P$ the (unique) simple path from $u$ to $v$ in $T$. $P+e$ is a cycle in $G$, showing that $e$ cannot be a cut-edge. In other words $e \not\in T \implies \mbox{$e$ is not a cut edge}$. Taking the contrapositive statement: $\mbox{$e$ is a cut edge} \implies e \in T$. $\endgroup$
    – Steven
    Jan 11 at 21:08

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.