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.
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