Exercises and Assignments
Pen and Paper: Cross Every Bridge Once, or Prove Nobody Can
A campus on both banks of a creek, two islands, and seven footbridges you have to tour without repeating one. You find the tour, then the development office builds an eighth bridge and the tour dies. Keeping a ledger of arrivals and departures at each landmass is what tells you which map is which — and it settles Königsberg, in under a minute, on the last page.
Do this before the reading. The whole point is to reach Euler’s argument with your own pencil, so that the lecture note only has to give it a name.
Exercise: decide whether a network has an Eulerian trail
You have two problems, both of which boil down to the same question Euler asked. It will take roughly an hour.
- Binghamton, not Königsberg. Turn the rivers and bridges of Binghamton, NY into a graph of landmasses and bridges, build its adjacency matrix, and decide whether you can cross every bridge exactly once.
- A network you did not draw. Pick any network under 5,000 nodes from Netzschleuder, load its edge list with
pandas, build the adjacency matrix from it, draw it, and run the same test.
The second problem is the key to this exercise. Your Euler test must be able to work on data you have never looked at. That is to say, it must be written in terms of degrees, not in terms of a picture.
Open the exercise notebook — it runs in your browser, with nothing to install and nothing to sign into.
Prefer to work locally? The notebook is in the repository at notebooks/m01-euler-tour/03-exercises.py. Run it with marimo edit notebooks/m01-euler-tour/03-exercises.py.
Assignments
The Group Mini-Project runs in this module: The Bridges of Binghamton, in class, in teams of up to three, ending in a three-minute presentation. Your team does what the first exercise above does, to the city you are sitting in, except that the part the exercise glosses over is the whole point. Nobody tells you what counts as a landmass or what counts as a bridge — whether a railway bridge counts, or where Binghamton stops given that the river does not stop at the city line. You decide, and no two teams hand in the same graph. Because everybody read the same rivers, you can argue with somebody else’s answer in a way you never could if they had picked Prague.
Then you build a bridge. The verdict is not the end of the session: your team proposes the crossing that lets the city be walked end to end and come home, somewhere a bridge could actually go, and defends the choice to the room.
Doing the exercise first is a good way to arrive with the code already working. It will not tell you what to draw.
The Pair Notebook does not run in this module — it starts from Module 2. The exercise above is for practice only and not for submission.
Come to the mini-project session with your machine set up. The session is ninety minutes and none of them are spare.