Friday, 24 November 2017

Proof- Safe edges in a Graph

Consider the following theorem:(23.1 in CLRS)
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$.
Now, from what I understood after reading the book, we take an edge $(u,v)$ (that is not in $A$), that is either in $T$ or not. If it is in $T$, then it is already safe. But if it isn't, we can see that since $T$ must include all the vertices of the graph $G$, then there must be some edge $(x,y)$ crossing the cut. (Since $(u,v)$ isn't in $T$). Now, if we make another tree $T'$ that contains $(u,v)$, but not $(x,y)$, then we'll still have an MST, since $(u,v)$ is a light edge, thus $w(u,v) \leq w(x,y)$, therefore, $$w(T') = w(T) - w(x,y)+w(u,v) \\ \leq w(T)$$. Thus $T'$ is an MST of $G$ that contains $(u,v)$. Thus all-in-all, $(u,v)$ is a safe edge. Cool!

No comments:

Post a Comment

1498C - Planar reflections

1498C - Planar reflections Problem We have a set of $n$ 2D planes. A particle comes from the left, and goes through all the planes. Initiall...