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$?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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