2
$\begingroup$

I know this question is posted many times, but i am still posting this because i have my own doubt which pulls me out to move forward to kruskal and prim's algorithm.So Please do help me out $-:$

Question

Let $G=\left(V,E\right)$ be a 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 $\left(S,V-S\right)$ be any cut of $G$ that respects $A$.Let $\left(u,v\right)$ be a light edge crossing $\left(S,V-S\right)$.Then, edge $\left(u,v\right)$ is safe for $A$.

Terminologies Used

we say that an edge $\left(u,v \right)$ crosses the cut if one of the endpoint is in $S$ and other in $V-S.$


Safe edge is edge at each step that we can add in A without violating any invariant.


we say that a Cut RESPECTS a set A of edges if no edge in A crosses the cut.


we say that an edge is a light edge satisfying a given property if its weight is the minimum of any edge satisfying the property

MY Approach/Doubt

With the help of book, i am able to understand the proof as-:

We Assume that $T$ is a MST(Minimum Spanning tree) which do not have light edge $\left(u,v \right)$, if we can manage to construct another MST $T^{'}$which contains $\left(u,v \right)$ and have weight less than that of $T$, then we are done! i.e we have to prove that $w \left(T^{'}\right) \leq w \left(T\right)$


Consider the figure below here

As MST $T$ will not contain $\left(u,v \right)$(given) ,there must be an edge that crosses the cut, otherwise it will be divided into 2 components.

Let that edge be $\left(x,y \right)$


Now let us construct the MST$T^{'}$ from $T$ by removing $\left(x,y \right)$ and adding $\left(u,v \right)$ given as-:

$$w \left(T^{'}\right)=w \left(T\right)-w \left(x,y\right)+w \left(u,v\right) $$

$\Rightarrow \left(u,v \right) \leq w \left(x,y\right)$ as $\left(u,v \right)$ is light edge

$\Rightarrow w(T^{'}) \leq w(T)$

My doubt is -:

1.Is the above proof explained above correct?am i missing something?


2.If the above proof is correct, then i have one issue .Issue is that after proving the above inequality $w(T^{'}) \leq w(T)$,the book says that $\left(u,v \right)$ is actually a safe edge for A,but is n't this contradictory?

I mean if $\left(u,v \right)$ is safe for $A$ ,then cut $\left(S,V-S\right)$ no longer respect $A$ because $\left(u,v \right)$ is an cross edge .

please help me out !

$\endgroup$
  • $\begingroup$ You're missing a definition here, that of a "safe edge". Given that your main question is about that definition, I suggest looking it up and adding it to the question. It could also help clarify your point of difficulty. $\endgroup$ – Yuval Filmus Jul 11 '17 at 10:38
  • $\begingroup$ @YuvalFilmus sir , please give a hint to clear my doubt! $\endgroup$ – laura Jul 11 '17 at 11:55
3
$\begingroup$

For a set $A$ which is a subset of some minimum spanning tree, an edge $e \notin A$ is safe if $A \cup \{e\}$ is a subset of some minimum spanning tree. In particular, if $|A| = n-2$, then any safe edge will cross the cut $(S,V-S)$. There is absolutely no requirement that $e$ not cross the cut.

$\endgroup$
  • $\begingroup$ sir :my doubt is that there have to have atleast one edge $e$ which will cross the Cut $\left(S,V-S \right)$ otherwise graph will be divided into $2$ components $S$ and $V-S$ , and if edge $e$ crosses the Cut , then $A$ will no longer be safe $\endgroup$ – laura Jul 11 '17 at 16:05
  • $\begingroup$ I think your definition of safe is wrong. My definition looks better. $\endgroup$ – Yuval Filmus Jul 11 '17 at 16:06
  • $\begingroup$ okk sir ! rest of my proof is ok? $\endgroup$ – laura Jul 11 '17 at 16:12
  • 1
    $\begingroup$ The rest looks fine. $\endgroup$ – Yuval Filmus Jul 11 '17 at 16:13

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.