3
$\begingroup$

While I was doing CLRS (3rd edition), I came across this question on page 629:

Professor Sabatier conjectures the following converse of Theorem 23.1:

Let $G = (V,E)$ be a connected, undirected graph with a real-valued weight function $w$ defined on $E$. Let $A \subseteq E$ that is included in some minimum spanning tree for $G$, let $(S,V -S)$ be any cut of $G$ that respects $A$, and let $(u,v)$ be a safe edge for $A$ crossing $(S, V - S)$. Then, $(u,v)$ is a light edge for the cut.

Show that the professor’s conjecture is incorrect by giving a counterexample.

Theorem 23.1:

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

Can anybody please give a proof or a counterexample to the conjecture also because I used to think that all safe edges added to the graph are light edges.

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.

I have written most of the definition but for more queries you can also refer to CLRS chapter 23.

$\endgroup$

closed as unclear what you're asking by Raphael May 4 '14 at 10:23

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ What is a cut that respects $A$ and what is a safe edge for $A$? $\endgroup$ – Pål GD Jul 1 '13 at 9:33
  • 1
    $\begingroup$ Here are some definitions..... A 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.A cut respects a set A of edges if no edge in A crosses the cut.An edge is a light edge crossing a cut if its weight is the minimum of any edge crossing the cut.**Safe edge** is the edge which we can add to MST without any violation of it's property. For more clarity refer CLRS chapter 23 MST. $\endgroup$ – RYO Jul 1 '13 at 11:02
  • 1
    $\begingroup$ Could you please put them in the main question? You can edit by pressing the edit button. The field also accepts $\LaTeX$ notation, so please add that (you can see how, by looking at how I edited your post). $\endgroup$ – Pål GD Jul 1 '13 at 11:28
  • $\begingroup$ I agree with Pål GD's advice to edit the post to add these definitions to the question -- and it would be great if you could define "safe edge" a bit more carefully/precisely. I did not fully follow the explanation of safe edge in your comment. $\endgroup$ – D.W. Jul 3 '13 at 7:42
  • $\begingroup$ I'm sorry, but I still don't understand the definition of a "safe edge". If you have a minimum spanning tree $T$, you certainly cannot add any edge to it. Therefore, if I read your definition of safe edge literally, no edge can possibly qualify as a safe edge. I suspect you must be summarizing some definition, and you must have left out some nuance. Would you care to try again to define what a "safe edge" is? It's important for questions to be self-contained (sorry, I don't have a copy of CLRS where I am at the moment; and I expect you to do the work of understanding all terms). $\endgroup$ – D.W. Jul 3 '13 at 21:45
1
$\begingroup$

OK, here's a big hint.

Take any $G,A,S$ that satisfy the premises of the question. Now add a new vertex $v'$ to the graph, and draw an edge from $v'$ to one of the vertices of $A$ with a weight of your choice. (This means that $v'$ will be connected to the rest of the graph only by this one new edge; there are no other edges out of $v'$.)

What can you say about this new edge? Does it cross the cut? Is it a light edge? Is it a safe edge? Does this suggest any method for choosing the weight on that edge, to make things fortuitous to you? Hint: if you think about it (or try some examples), I bet you'll see how you can arrange things to get a violation of the conjecture.

People learn best by finding the solution for themselves (rather than reading someone else's solution), so I'm not going to post more than a hint. This hint ought to be enough to understand what's going on here....

$\endgroup$
  • $\begingroup$ @RYO I still don't get it :( $\endgroup$ – Rajat Saxena Apr 17 '17 at 14:15

Not the answer you're looking for? Browse other questions tagged or ask your own question.