Graph theory.

English: The problem of the Seven Bridges of K...

The problem of the Seven Bridges of Königsberg. (Photo credit: Wikipedia)

I used to think that there was no point in giving someone a math problem that was unsolvable.

What could you learn from that except your tolerance for frustration?

It turns out, though, that mathematicians, even when they suspect a problem has no answer, are not happy until they can prove it.

That is the case with the famous Seven Bridges of Königsburg problem.

Leonhard Euler, a Swiss mathematician and physicist, proved this problem had no solution in 1735, and in the process, invented graph theory, structures used to model pairs of objects.

Materials:

  • Pen or pencil
  • Paper

Instructions:

  • Draw two banks of land with a river in the middle
  • Draw two islands in the middle of the river
  • Draw seven bridges
    • Two bridges from one bank to the first island
    • Two bridges from the other bank to the first island
    • One bridge connecting the two islands
    • One bridge connecting one bank to the second island
    • One bridge connecting the other bank to the second island
  • Find a path across the bridges in which you cross each one once and only once
  • You don’t have to start and end at the same place
  • You can’t walk halfway across a bridge, turn around and cross the other half later
  • The islands can only be reached by the bridges.

What Should Happen?

Since you must enter and leave each landmass over a bridge, there have to be an even number of bridges.

You cannot enter and leave on an odd number of bridges.

In this problem, each landmass has an odd number of bridges.

So, it is not possible to cross every bridge once and only once.

If only two of the the land masses had had an odd number of bridges, you could trace a route across the bridges once and only once, in what is called a Eulerian path.

Koenigsburg is a real city that was in Germany, founded in 1255.

Since 1946, the city has been called Kalingrad and is in Russia.

The bridges described were built between 1286 and 1542.

In World War II, two of those bridges were destroyed.

Before Euler, its citizens used to try, on Sunday afternoons, to walk around the city and solve this puzzle.

Euler figured out something to simplify the puzzle to start with.

It didn’t matter where else people walked in the city.

The only thing that mattered for solving this problem was where the bridges met the land.

He turned the key factors into a graph, with nodes representing landmasses and lines connecting them representing bridges.

The Königsberg Bridges graph. This graph is no...

The Königsberg Bridges graph. This graph is not Eulerian, therefore, a solution does not exist. (Photo credit: Wikipedia)

Why Is This Useful?

Graphing theory was a precursor for topology.

These mathematical disciplines are used to schedule efficient routes and networks, like those for computers.

This post first appeared on grandmotherdiaries.com

Carol Covin, Granny-Guru

Author, “Who Gets to Name Grandma? The Wisdom of Mothers and Grandmothers

http://newgrandmas.com

 

Related posts

 

Enhanced by Zemanta