Seven Bridges for Seven Truckers

Subtitle: An Eulerian circuit through the neighborhood

Seven Trucks

We live in a small, quiet neighborhood. Still, trucks come fairly often.

seven-trucks

Once a week the trash truck drives through, and the next day the recycling truck comes. The town provides street maintenance with three trucks. The leaf-eater truck is a giant Roomba for leaves, the stick-picker truck picks up large branches and sticks, and the gutter-sucker truck is a combination street sweeper and debris vacuum. FedEx and Amazon send trucks around several times a day, too.

The delivery trucks operate with controls on the left as is typical here in the U.S., but the other five put the driver on the right side so equipment can be guided by the driver. The trash and recycling trucks have a grabber to lift the bin, dump it into the truck, and return it to the side of the road. The leaf-eater vacuum tube can be swung back and forth from inside the truck to suck in large leaf piles. Even the delivery trucks tend to stop in front of the house so the driver can grab the package and step out on the right side of the vehicle without crossing the road.

One day, I watched the recycling truck come around and saw it make an efficient tour of the neighborhood. Naturally, I wondered what the most efficient route would be, and if there might be a way to figure it out. As any right-thinking person would say to themselves at this point, “Hey, this looks like the famous seven bridges of Königsberg problem!”

Seven Bridges

Königsberg (now Kaliningrad) used to be in Prussia before the Soviet Union annexed the city on 9 April 1945. Königsberg was the home of philosopher Immanuel Kant, mathematician David Hilbert, and author Hannah Arendt.

konigsberg-bridges

Konigsberg Bridges

Six bridges connect the city on either side of the river to the two islands in the river, and one bridge connects the two islands. People in Königsberg wondered if you could find a walking path that crossed all seven bridges exactly once. Swimming back across the river is not allowed. They tried all sorts of routes through the city, but no one ever found a path that didn’t require crossing at least one of the bridges twice.

Euler’s Graphs

Leonhard Euler, seen here wearing a pillowcase on his head (allegedly!), lived in nearby St. Petersburg. He proved why it isn’t possible to cross all of the bridges exactly once, publishing his results in 1736, thus beginning the era of graph theory and topology.

leonhard-euler

Leonhard Euler

Euler’s insight was that each of the four areas could be condensed down to a point or node, and the bridges could be represented as lines or edges connecting the nodes. The locations of the bridges didn’t matter, but Euler realized the number of edges had to match the number of bridges connected to each node. Here’s the way he thought about it, with land areas as red nodes and bridges as yellow arcs connecting them.

konigsberg-graph-overlay

Can you start at any node and make a path to trace each yellow arc exactly once? Let’s start with some simpler cases. If you doodle around with two or three nodes you might come up with these possible node-edge connections.

digraphs-two-three-nodes

Notice the first graph in the top row is essentially identical to the third one in the top row. They both connect two nodes with a single edge, although in the second example, a third unconnected node can’t be reached.

The second graph in the top row is the same as the third graph in the second row because each connects three nodes in order. You can solve these two cases as long as you don’t start with the middle node. All of these examples are solvable, but you may need to be careful about where you start and the path you take.

In one of my abstract algebra classes, the professor told us he didn’t know how many times we had walked through the classroom door, but he knew it was an odd number. His reasoning was we had all walked through the door once the first time we came into the room. From then on, at the end of each class and the beginning of the next, we walked through two times. To get back into the classroom we were now in required an out and an in, in multiples of two. Adding up the initial entry and any subsequent pairs of leaving and re-entering gave an odd number of passages through the doorway for each of us.

One of the students, who shall remain nameless and blameless, crawled out a window, walked around to the front entrance, and back through the classroom door. This student clearly remembers the classroom being on the first floor, which was a good thing. This stunt was equivalent to swimming back across the river in the Königsberg bridge problem.

The professor’s point is useful for this problem because if you have a valid path you can always add a pair of edges connecting any two nodes and you’ll still have a solution. When you reach one of the nodes with your two new edges, cross over to the other node on one of the new edges, and back on the other one. Then, carry on with your original solution.

There’s another possibility I haven’t shown here. I call it the La-Z-Boy solution which is the case where none of the nodes are connected by any edges. If there aren’t any bridges, you can cross all of them without getting up out of your La-Z-Boy.

The Four Lands

The Königsberg problem requires four nodes. The river divides the city into two pieces North and South, and two more nodes represent the islands in the middle of the river. How many ways can you connect four nodes with either zero (the La-Z-Boy case) or one edge? To simplify the problem, think of the four nodes as vertices of a square.

With one edge, any orientation of the four nodes is equivalent to every other orientation. A rotation by 90°90\degree doesn’t change the problem, and you can make a diagonal into an edge of the square by switching two vertices.

digraphs-four-nodes-one-edge

Flipping the square vertically or horizontally doesn’t change anything, nor do flips along the diagonals. Here are all the unique combinations of zero or one edge on four nodes. I included the number of edges at each node at the top of each graph, and a red “X” indicates graphs without solutions.

digraphs-four-nodes

Euler’s Solution

The three impossible cases have odd numbers of edges at each of the four nodes. This is a clue as to why no solution exists. Imagine that at each end of a bridge is a gate. As soon as you pass through the gate, it locks and you can’t get through anymore. Suppose a node has 3 gates. You can enter the node through one gate, leave through another, leaving one more gate.

Your path will need to either start or end at that node because once you’ve passed through all pairs of gates, you’re stuck at that node. A solution always exists for the unconnected (La-Z-Boy) case because zero is an even number.

This is how Euler showed that the Königsberg bridge problem couldn’t be solved. On the left is the original graph shown in the overlay above. In the middle, I shifted the nodes to the vertices of a square, and on the right I removed paired edges. Now you can see this is the impossible case (1,1,1,3)(1,1,1,3). Removing edge pairs doesn’t change whether a solution exists or not, but it declutters the problem.

konigsberg-graph-reduced

Digraphs

Digraphs, or directed graphs, are one-way streets meaning you can only travel from one node to the other if the edge points in the right direction. Intersections are nodes, and each side of the street is a directed edge between the nodes.

directed-graph-in-nbrhd

The recycling truck made a U-turn at the intersection of Creekview Circle and Waterside Drive (in the upper right corner of the map). I didn’t see the full route through the neighborhood, but the truck seemed to need only one trip per side of a street. It may have used Rock Spring Court to reverse direction rather than making two U-turns.

The numbers next to each node are the total number of connections. In parentheses are the number of edges in and out of each node. Entries and exits match in every case because there are two sides to the roads, and every node has an even number of connections meaning a solution exists.

Using the Strava app on my phone, I walked a path connecting all of the nodes using each edge exactly once.

strava-path

Strava Path

If the graph makes a closed loop, it’s called an Eulerian graph. I didn’t quite close the gap at the intersection of Pathway Drive and Spring Valley Road in my Strava hike, but this path is an Eulerian circuit.

Applications of Graph Theory

Every time you type a word or phrase into Google, the search algorithm uses graph theory to find relevant web pages. It uses the number and importance of other websites connected to a site to determine how high to rank the page relative to other pages.

pageranks-example

Page Ranks Example

Since page BB is considered very important, page CC receives a higher rank than page EE even though there are only two links to CC, but nine to EE.

Social networking sites like LinkedIn and Facebook connect people and groups forming online graphs. Manufacturing supply chains connect manufacturers of subassemblies to factories performing final assembly. Printed circuit boards form graphs through the connections between components.

circuit-board-blue

Circuit Board

In our previous post, “A Research Rubric” we showed citation tools like Connected Papers and Citation Gecko that use graphs to link scientific papers through citations, or similar topics. VOSviewer is a tool to construct and visualize bibliographic networks.

Other applications include scheduling, molecular and genomic biology, Feynman graphs in physics, and chemical modeling where atoms are nodes and bonds form the edges of the graph.

avogadro-molecule

Molecule in Avogadro

In 1956, Edsger Dijkstra created an algorithm to find the shortest path between any two nodes in a graph, and it can even be used to find your way out of a maze!

Software Tools

Graphs can be represented as sparse matrices where the (i,j)th(i,j)^{th} entry in the matrix indicates how many edges connect node ii to node jj. For the Königsberg bridges, the adjacency matrix looks like

K=[0102101101022120]K = \left[ \begin{array}{cccc} 0 & 1 & 0 & 2 \\ 1 & 0 & 1 & 1 \\ 0 & 1 & 0 & 2 \\ 2 & 1 & 2 & 0 \\ \end{array} \right]

konigsberg-graph-unreduced

The top row says node aa is connected once to node bb, zero times to node cc, and twice to node dd. These matrices are called sparse because often most of the entries are zero, especially in graphs with many nodes.

Four programming languages used by scientists have graph theory toolboxes:

Some standalone open-source or free packages are:

A free online textbook by Robin J. Wilson, “Introduction to Graph Theory” is available here.

Graph theory has a lot to offer mathematically, and there are many applications for you to explore.


Image credits

Hero: Seven Brides for Seven Brothers (1954 poster), Wikimedia Commons.

Konigsberg Bridges: Wikimedia Commons.

Leonhard Euler: Wikimedia Commons.

Strava Path: Generated with Strava App.

Page Ranks Example: Wikimedia Commons.

Circuit Board: Álvaro Marques, Man Cave Office, Pinterest.

Molecule in Avogadro: Avogadro: an open-source molecular builder and visualization tool.


Software

Julia

The Julia Project as a whole is about bringing usable, scalable technical computing to a greater audience: allowing scientists and researchers to use computation more rapidly and effectively; letting businesses do harder and more interesting analyses more easily and cheaply.

Posts using Julia

Octave

GNU Octave is a high-level language, primarily intended for numerical computations. It provides a convenient command line interface for solving linear and nonlinear problems numerically, and for performing other numerical experiments using a language that is mostly compatible with Matlab.

Posts using Octave

Graphviz

Graphviz is open source graph visualization software. Graph visualization is a way of representing structural information as diagrams of abstract graphs and networks. It has important applications in networking, bioinformatics, software engineering, database and web design, machine learning, and in visual interfaces for other technical domains.

Gephi

Gephi is the leading visualization and exploration software for all kinds of graphs and networks.

Microsoft Automatic Graph Layout

MSAGL is a .NET tool for graph layout and viewing. MSAGL is available as open source here.

Tulip

Tulip is an information visualization framework dedicated to the analysis and visualization of relational data. Tulip aims to provide the developer with a complete library, supporting the design of interactive information visualization applications for relational data that can be tailored to the problems he or she is addressing.

Neo4j

Neo4j is the world’s leading Graph Database. It is a high performance graph store with all the features expected of a mature and robust database, like a friendly query language and ACID transactions.

See all software used on wildpeaches →