1
$\begingroup$

Corollary 23.2

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$, and let $C = (V_C,E_C)$ be a connected component (tree) in the forest $G_A = (V,A)$. If $(u,v)$ is a light edge connecting $C$ to some other component in $G_A$, then $(u,v)$ is safe for $A$.

Proof The cut $(V_C,V-V_C)$ respects $A$, and $(u,v)$ is a light edge for this cut. Therefore, $(u,v)$ is safe for $A$. $\quad\blacksquare$

I did understand the original proof for the Cut property in CLRS (Theorem 23.1). But I am unable to grasp how does the above corollary follow from the original proof? Why does the cut $(V_C,V-V_C)$ respect $A$?

$\endgroup$
1
$\begingroup$

The cut $(V_C,V-V_C)$ respects $A$ since $C$ is a connected component in $(V,A)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.