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)$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!
be a light edge crossing $(S,V- S)$. Then, edge $(u,v)$ is safe
for $A$.
No comments:
Post a Comment