10 repetitions of the contraction procedure. The 5th repetition finds the minimum cut of size 3.
I think a lot of “free” intuition about an algorithm is gained from just seeing it run, and this particular algorithm is hard to do well on the blackboard. You need a big enough enough instance, which you need to update several times (requiring eraser work and covering you in dust), and then you’d have to repeat the whole thing several times.
So I spent some time drawing these illustrations myself. I implemented the algorithm in Python, using the nifty networkx library. The graphs are quite well laid out using neato from the graphviz package. For each contraction I pinned the other nodes, made the midpoint of the two contracted nodes the new starting point of the new, merged node, and let neato’s embedder move that new node around. (Though I ended up laying out the initial graph by hand, which is just so much nicer.)
Networkx lets you display graphs in mathplotlib, which works moderately well. I even had an animated run for the lecture. Sexy stuff. (But I’ve become somewhat soured on animations. Good, static “animations” of all the steps in an algorithm are much more instructive, a lesson I’ve learned from looking at the amazing illustrations appearing in the textbooks of Robert Sedgewick and Kevin Wayne.)
Mathplotlib doesn’t do curved edges, though. So in the end I wrote a bit more code that transforms a networkx graph (with layout) to a TikZ picture. The result is run trough LaTeX, converted to SVG, and Bob’s your uncle. Or Dave, in this case. Phew.
Uploaded to Wikimedia Commons, free to use and modify with attribution.
- File:10_repetitions_of_Karger’s_contraction_procedure.svg
- File:Single_run_of_Karger’s_Mincut_algorithm.svg
- File:Edge_contraction_in_a_multigraph.svg
By the way, the Wikipedia entry for Karger’s algorithm is not in good shape. (But does contain the images now…)
Thore Husfeldt 
could you please provide the python code you wrote for implementing karger’s min cut algorithm using networkx… Thanks
The Python code for the algorithm itself couldn’t be more beautiful. It’s something like this:
while(len(G)>2):
e= random.choice(G.edges())
G = contract(G, e)
The only (slight) difficulty is writing the code for contract. (Which is not part of the networkx library.) My own code contains too much cruft for the visualisation (juggling coordinates, unpinning vertex positions, etc.) to be interesting.