Theorem 23.1 Let G = (V, E) be a connected, undirected graph with a real-valued
ID: 3806317 • Letter: T
Question
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. It seems that any cut of G will work so long as it respects A. Let's say that we make the cut far away from the minimum spanning tree T that contains A, so that no vertex in T has an edge that crosses the cut. Let (u, v) be the light edge crossing the cut. Given our choice of cut, neither u or v can have an edge that is in T. So if we added the edge (u, v) to A, u and v would not be connected to anything else in T, so T would not be a minimum spanning tree anymore. It is not clear to me that there exists a different minimum spanning tree T' that would also satisfy our loop invariant. I feel like I'm misunderstanding something but I'm not sure what. Can someone explain?Explanation / Answer
see its clear from the definition of light edge crossing which says: An edge is light egde crossing the cut if its weight is minimum of any edge crossing the cut, which means it will be definelty a part of A which is again the part of minimum spanning tree in which only minimum weighted edges are included.
secondly
Considering an cut/edge away from the spanning tree is violating the condition. In addition to this it is a connected graph which says all vertices are connected so in your case treating an edge which is not connected to G is not valid
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.