optional · interactive figures

Explore: greedy and metric TSP

Greedy set cover purchase by purchase, and the double tree and Christofides built step by step on the deck's six points and on eight more.

optional: nothing in the lab depends on itback to the slides

23 · explore

Greedy set cover, purchase by purchase

Try: step through the three purchases and watch step 2 choose the cheaper-looking S3. Static version: greedy set cover on five elements.

23 · explore

The double tree and Christofides, step by step

Try: both algorithms on the six points, then on the eight points, where the matching has choices and Christofides wins. Static versions: double tree, Christofides, both on six points.

What it shows. Each algorithm's pieces in order: the minimum spanning tree (a lower bound), then either the doubled walk and its shortcut, or the odd vertices, the minimum-weight matching on them (red, drawn bent), the Euler circuit of tree plus matching, and its shortcut. Edge labels are distances.

Six points (the deck's, distances as on the slide): only vertices 3 and 5 are odd, so the matching is forced, and both algorithms find the same cycle, 62 against the optimum 54.
Eight points (random, seed recorded in the menu): all eight vertices odd, a real matching choice, and Christofides' tour is clearly shorter than the double tree's.

Data: slides/viz/traces/u23.py, from the reference prim, double_tree, odd_vertices, euler_circuit, shortcut and christofides, with the optimum by brute force over all tours from 0.