The simulator shows a graph shrinking edge by edge as Karger's algorithm randomly selects and contracts edges, visually merging vertices into growing super-vertices while parallel edges accumulate between them, until only two super-vertices and their connecting edges remain as the candidate minimum cut. Running many independent trials side by side reveals how cut sizes vary between attempts and how the best-so-far result converges toward the true global minimum cut as more trials accumulate.
Load or generate a graph, then step through contractions one at a time to watch a single random edge get selected and its endpoints merge, or let the run play automatically to completion. Compare the resulting cut size against the graph's known true minimum cut. Switch to repeated-trial mode to launch many independent runs in sequence, track the smallest cut size found so far after each trial, and watch the empirical failure rate shrink as the trial count grows, directly illustrating the Monte Carlo repetition argument.
Controls include graph selection or random graph generation with adjustable vertex and edge counts, a step-by-step contraction button alongside an auto-run speed slider, a trial counter with a run-many-trials button for the repeated Monte Carlo phase, a running display of the best cut size found so far compared to the graph's true minimum, and a toggle between the basic full-contraction algorithm and the faster recursive contraction refinement.
For a graph shaped like a simple cycle of n vertices, where the true minimum cut has size exactly 2, a single run of Karger's algorithm succeeds in finding that minimum cut with probability exactly 2 over n, meaning on a 100-vertex cycle a lone attempt only succeeds about 2 percent of the time, yet a few hundred independent repetitions push the overall success probability above 99 percent.
The simulator shows a graph shrinking edge by edge as Karger's algorithm randomly selects and contracts edges, visually merging vertices into growing super-vertices while parallel edges accumulate between them, until only two super-vertices and their connecting edges remain as the candidate minimum cut. Running many independent trials side by side reveals how cut sizes vary between attempts and how the best-so-far result converges toward the true global minimum cut as more trials accumulate.
The simulator shows a graph shrinking edge by edge as Karger's algorithm randomly selects and contracts edges, visually merging vertices into growing super-vertices while parallel edges accumulate between them, until only two super-vertices and their connecting edges remain as the candidate minimum cut. Running many independent trials side by side reveals how cut sizes vary between attempts and how the best-so-far result converges toward the true global minimum cut as more trials accumulate.
Load or generate a graph, then step through contractions one at a time to watch a single random edge get selected and its endpoints merge, or let the run play automatically to completion. Compare the resulting cut size against the graph's known true minimum cut. Switch to repeated-trial mode to launch many independent runs in sequence, track the smallest cut size found so far after each trial, and watch the empirical failure rate shrink as the trial count grows, directly illustrating the Monte Carlo repetition argument.
For a graph shaped like a simple cycle of n vertices, where the true minimum cut has size exactly 2, a single run of Karger's algorithm succeeds in finding that minimum cut with probability exactly 2 over n, meaning on a 100-vertex cycle a lone attempt only succeeds about 2 percent of the time, yet a few hundred independent repetitions push the overall success probability above 99 percent.