Cut in a Graph

A is a partition of vertices into disjoint sets and where is the set of all vertices.

Pasted image 20240422004522.png > invert

  • An edge crosses the cut if one endpoint is in and the other is in .

Cuts respecting edges

A cut respects a given set of edges , if no edge in crosses the cut.

Light edges

An edge is considered a light edge, if its weight is minimum compared to all other edges that cross the cut.

Note

For a given cut, there can be more than 1 light edge crossing it. This is when multiple minimum edges have identical weights.