Friday 24 November 2017

[CLRS-23.1-2] Proving the conjecture wrong

23.1-2 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$ be a subset of $E$ that is included in some minimum spanning tree $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.

So, the basic problem that I faced here was :
Every edge is added to $A$ only after comparing all the other edges that connect both the components of $G_A$. So, $(u,v)$ connecting any two components must be a light edge.
Well, this is obviously wrong. Since, the two components that we're talking about, in both the scenarios are different. That is to say, when we added $(u,v)$ to $A$, there might not be any other edge connecting the two components (like for example, if both the components contain only one vertex), but when we have our present $A$,then we might have many other edges other than $(u,v)$, which connect the chosen components. So, in that case $w(u,y)$ is not necessarily the minimum of all the edges' weights connecting those components.
For example see:
Here, we have a tree (which itself is a graph), let $A$ have all the edges (that is $A$ is the MST here)  $S = \{A,E,D\}$ and $V-S = \{B,C\}$. Now see that $(A,B)$ is not a light edge, even though it is a part of $A$, and is safe.

1 comment:

  1. It is given that "let (S,V−S) be any cut of G that RESPECTS A" so according to this, edge (B,D)and edge(B,A) should not be in set A.Please correct me if i am wrong

    ReplyDelete

1295D - Same GCDs

 1295D - Same GCDs Link to the problem :  https://codeforces.com/problemset/problem/1295/D I had to see the tutorial to understand this. $$ ...