Stoer–Wagner Global Minimum Cut

The Stoer–Wagner algorithm calculates the global minimum cut of an undirected, non-negative weighted graph. Instead of relying on a source-sink max-flow calculation for all pairs of nodes, it computes the min-cut efficiently through a series of phases. In each phase, the graph is contracted to find the minimum cut separating a specific pair of vertices.

Experiment

Explore how different graph topologies affect the minimum cut and the canonical side by selecting different graphs from the controls. See Stoer–Wagner Global Minimum Cut.

1. Select the Path graph. Notice that the minimum cut weight is 2, separating node 0 from the rest.
2. Change the Graph control to Disconnected. Observe that the minimum cut weight drops to 0, representing the absence of edges between the components, with a canonical side of "0,1".
3. Switch to the Complete graph to see the minimum cut weight increase to 3.