Dots and lines: tours, maps, mazes and shortcuts

Stations and tracks, islands and bridges, towns and roads. Join round dots with lines and many different problems take the same shape. The dots are called vertices, the lines edges, and the picture of dots and lines a graph. The five works here are all played on graphs.

A tour of the dodecahedron (the site’s “Icosian Tour”)

Walk along the edges of a dodecahedron (a solid made of 12 pentagons), visit all 20 corners exactly once, and come back to the start. Such a route is called a Hamiltonian cycle. The Irish mathematician Hamilton showed the game at a meeting in Dublin in 1857, and is said to have licensed it to a London toy maker, which put it on sale around 1859. Thomas Kirkman in England was studying similar routes at the same time. We cannot say Hamilton was first, but his name stayed attached to the routes.

The program checked that the figure has 20 vertices and 30 edges, that every vertex has three edges, and that a 20-edge round trip exists (icosian-tour/engine.test.ts). It also checked by exhaustive search that the slightly altered figure in the work has no such route at all. To say that no route exists you must either try everything or find a reason.

Colouring maps with four colours (the site’s “Four-colour Map”)

If neighbouring countries must get different colours, how many colours do you need? In 1852 Francis Guthrie in England is said to have noticed, while colouring a map of counties, that four seemed to be enough. A proof appeared in 1879, but an error was found in 1890. The theorem was finally proved in 1976 by Appel and Haken, who used a computer to check thousands of cases. In 2005 the proof was verified once more inside a proof-checking program. It also started a debate about how to accept a proof that no human can read through in full.

The program checked that the work’s map with an island in the middle needs four colours and that three are impossible. There is also a six-country map that two colours are enough for (four-color-map/engine.test.ts). The maps are fictional ones made for this site. Two countries count as neighbours only if they touch along a line of real length, not just at a corner.

Finding your way out of a maze (the site’s “Maze Explorer”)

A classic method is the right-hand rule: keep one hand on the wall and walk. It is guaranteed to work only in a maze whose walls are all joined to the outer wall, with no loops. If the goal lies around an island, you simply circle the island. Another method marks the passages you have used. It is named after the nineteenth-century Frenchman Trémaux and is the same idea as today’s depth-first search. It solves any maze with clear passages, but not necessarily by the shortest way.

The program tried 200 seeds and checked that every maze of the work is connected and loop-free. With no loops, the right-hand rule always reaches the exit. A breadth-first search finds a route that is never longer than the wall walk, and in these mazes the route to the exit is unique, so the shortest route is the only one (maze-explorer/engine.test.ts).

The shortest road (the site’s “Shortest Path”)

When each road has its own time or cost, Dijkstra’s algorithm finds the route with the smallest total by settling places in order of closeness to the start. Dijkstra worked on this problem in Amsterdam in 1956 and published it in 1959. In a later interview he said he thought of it in about twenty minutes at a café while out shopping (that is his own recollection).

The program checked that the algorithm’s answers match a count of every route from every starting point. In the work’s two road networks the cheapest costs are 6 and 5. The route with the fewest stops (breadth-first) costs 11 in the first network, more than the cheapest. Few steps and low cost are different things (shortest-path/engine.test.ts).

The order of a round trip (the site’s “Round-trip Route”)

Visit several towns once each and come back: which order is shortest? This is the travelling salesman problem. It goes back to Hamilton and others in the 19th century, and Julia Robinson’s 1949 report is said to be the first to use the name. A 49-city case was solved in 1954, larger ones later, and in 2006 one with 85,900 cities. In 1972 Karp showed that a related problem is NP-complete, which makes this problem NP-hard. That does not mean it cannot be solved; it means that as towns are added, trying every order stops being realistic.

With the work’s eight stops there are 7! = 5040 orders. The program checked that the shortest one found by trying them all matches a separately written exhaustive search. Always going to the nearest town (nearest neighbour) ends up at least 1 longer than the best on the first map. From there, repeatedly swapping two crossing roads (2-opt) gets closer to a good tour (tsp-route/engine.test.ts).

What they share

• Turn it into dots and lines: strip away the decoration and the same shape appears.
• “There is” versus “there isn’t”: a route, or a four-colouring, is shown by finding it. “None” needs a full search or a reason.
• There is more than one kind of short: least time, fewest changes and easiest to find are different yardsticks.

The maps, mazes and road networks are all made for this site.