The Seven Bridges of Cardiff ?
This is a straight copy of the initial questions I posed at Cardiff #MathJam on Tuesday 20th October 2015, at the ‘Grape and Olive’ pub.
Königsberg: Seven Bridges for Seven Brothers
In 1736 Leonhard Euler was in desperate need of a new idea for that year’s Math Jam Pub Crawl. He happened to be in Königsberg (now Kaliningrad, an exclave of Russia) and wondered if they could visit the inns of the city by only crossing each of its bridges once (no swimming or using boats). However, they could start or finish where they liked.
To simplify things, it didn’t matter what they did on each of the ‘land masses’ they entered (presumably finding the quickest way round their respective hostelries, but that’s another story), so they could be represented by a single point, vertex or node. Indeed once he took this line of thought, each bridge could be represented by a connection or edge (see below).
“Now we’re getting somewhere. This looks like maths to me!”, he thought. “I shall call this structure a graph”, and Graph Theory was born. Now, on a ‘dry run’ (lemonade only) Euler observed that except at the start and end vertices, for each transitional vertex he could only enter by one connection and leave by another, or, the number of times he entered the transitional vertex equalled the number of times he left i.e. the number of bridges (or edges) must be even for a vertex one doesn’t start or finish on.
“Duh, obvious !”, said his fellow Math Jammer, Dan Bernoulli.
The trouble with Königsberg was that each land mass had an odd number of bridges attached, so no matter which way he looked at it no-one could complete a ‘Eulerian Pub Crawl’. “Hopefully everyone will be so drunk after the first few pubs, my six Maths Jam comrades won’t notice”, he considered.
Given a some wood, paint, a little ingenuity and a bit of DIY, how could this problem have been solved ?
NB: 100 years later William Hamilton (founder of ’Physics Chutney’) turned the problem on its head. “What about if each vertex only once?”, and the Hamiltonian Pub Crawl was invented. Not that difficult for Königsberg, but more tricky for other graphs.
The Bridges of Cardiff County
It’s long been a contention of mine that Cardiff doesn’t have enough bridges across the Taff. I thought at the time that there were only 7 bridges, so I enlisted Leonhard Euler to help. Let’s start by looking at a map. There are 3 main rivers slicing through area of Cardiff County: Rhymney, Taff and Ely, giving us 4 land masses, or vertices.
Now the M4 poses a problem. If we cross the Taff from Vertex 2 using the M4, we can only re-enter the city at Culverhouse Cross. This is at Vertex 4, so connection or edge should be drawn from 2 to 4, although the actual bridge crosses from 2 to 3.
P.S. There are in fact 9 bridges across the Taff.
Using this information, can you create an Eulerian Pub Crawl (or Path) across the city?
Answers to come…
There’s a more interesting practical problem. The city not only has river bridges but many railway bridges. If we’ve got enough time the evening I’ll take you through. It creates up to 13 vertices !
Post to come JAH 23.10.15