Simanaitis Says

On cars, old, new and future; science & technology; vintage airplanes, computer flight simulation of them; Sherlockiana; our English language; travel; and other stuff

NETWORKING ALONG KÖNIGSBERG’S SEVEN BRIDGES

“THE SEVEN Bridges of Königsberg” sounds like a romantic novel set elsewhere than Iowa. In fact, though, it’s a classic problem of mathematics, one that led to modern mathematics’ graph theory, topology and theory of networks.

N

The essentials of the Seven Bridges of Königsberg. Image from The World of Mathematics: A Four-Volume Set.

Königsberg, Prussia, B and C, is on the Pregel River, with two major islands, A and D, seven bridges, a through f, being part of the landscape in the 1700s.

A Google Map of what is now Kalingrad, Russia, shows that, indeed, five of the seven crossings still exist. Two of them, a and c, are the major thoroughfare of Leninsky Prospect. The third bridge, e, is on Kahta Street connecting the larger island D to Königsberg Cathedral on A, the smaller one. Modern bridges g and f are now part of Oktyabrskaya Street. The other two historic bridges, b and d, linking the Cathedral to the city proper, were destroyed in World War II.

m

Kalingrad today. Image from Google Maps.

And aren’t Google Maps fun, especially in satellite mode?

Back in the 1700s, Königsbergers entertained themselves with a puzzle: Was it possible to take a continuous stroll of all seven bridges without crossing any bridge twice?

n

Leonard Euler, 1707 – 1783, Swiss-born mathematician and physicist. This wonderfully iconoclastic image of him appeared on the Swiss 10-franc note.

Leonard Euler is considered the greatest mathematical mind of the 1700s. James R. Newman cites in The World of Mathematics that “Euler calculated without apparent effort, as men breathe, or as eagles sustain themselves in the wind…. He dashed off memoirs in the half-hour between the first and second calls to dinner.”

Euler solved the Seven Bridges of Königsberg puzzle in the negative (a more difficult task than showing it could be done). In doing so, he distilled the puzzle into its essentials in a way that’s characteristic of modern mathematics: Seek generalities rather than specifics. Study relationships in the abstract.

n

Euler’s three steps to modern graph theory: from the Königsberg map to its essential linkages to abstract edges and nodes.

Each node of his graph represents a land mass; each edge represents a bridge. Everything else in the Königsberg map is irrelevant, as are the relative placements of nodes and edges. This idea of deformable invariants is fundamental to the modern mathematical area of topology (think about the similarity of a doughnut and a coffee cup—each is pierced with a single hole).

The puzzle can then be restated: Can a continuous path trace each edge of the graph precisely once?

Euler reasoned that, with the exception of the start and end of a successful Königsberg walk, a land mass is entered by one bridge and left by another. Thus, he recognized that these intermediate nodes must have an even number of edges, “nodes of even degree.” Others are nodes of odd degree.

Finally, he concluded that a successful walk must have either precisely two nodes of odd degree (the start and end) or none at all. Since the four nodes of the Königsberg puzzle all have odd degree, there is no successful bridge tour.

n

By contrast, here’s a graph with precisely two nodes of odd degree. Trace a successful Euler walk.

In his honor, such a walk is also called an Eulerian path.

As a final exercise (extra credit!), sketch a map with islands and bridges that fits the geography of this particular Euler walk. ds

© Dennis Simanaitis, SimanaitisSays.com, 2014

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Information

This entry was posted on September 1, 2014 by in Sci-Tech and tagged , , , , , .
%d bloggers like this: