4- Connections

4.1- Points and Lines

Königsberg, 1736: is it possible to go through the city by crossing each of its seven bridges once and only once?

To resolve this problem, Euler holds the essential information: the city is divided into four districts represented by four points, connected by seven lines which symbolise the seven bridges.

The problem is then: on this plan, is there a road which passes only once over each line? It is the beginning of graph theory.
Euler's answer: how many points are there where an odd number of lines ends.
There is a solution if this number is equal to zero or two! Leonhard Euler (1707-1783)

Experience on table

Paths trough a Cube

Build a 3x3x3 cube or a 2x3x3 wall, so that the red line is continue.
Once this is done, can you minimize the number of straight circuits.

To remember

It’s Euler who gave birth to Graph Theory with this type of problems.
First, you have to find a solution.
The problem is also to find out if there are minimal solutions:
How can we be sure that there isn’t a circuit with no straight line ? How can we prove that all solutions have a minimum of 2 or 3 straight lines?
Idea & Realisation: Centre•Sciences

4.2- Are 4 colors enough?

How many colours are enough to colour a map in such a way that two adjacent countries are of different colours?

Graph theory allows us to model this problem and to reduce the number of cases to be studied to a finite (but still large) number. But thanks to the computer all these cases have been analysed.

Graph theory is used to model and study very important situations like electronic circuits, telecommunication networks, distribution networks -water, gas, electricity, post...- and numerous problems of logistics, transport and production.

Experience on table

A Coloring Game

Two players: each, in turn, assigns a chosen color to a neighboring country.
The trick is that no 2 neighboring countries must have the same color.
The rule: 2 nearby countries have to be of different colors. The loser is the one who can play again.

To remember

If you play alone, the graph’s theory said that 4 colors suffice to color all the map!
It’s possible to find an algorithm to color the map with 6 colors.
The algorithm’ problem have not yet general solution with 4 colors.
Idea & Realisation: Jean Lefort (Strasbourg) & Centre•Sciences

4.3- Hello! Is that you?

How is your phone call connected?
It travels from relay to relay right up to the station nearest to your correspondent who is alerted by a bell.

In a town, these stations of the telephone network are best placed by taking into account the irregular topology of the streets.

Each station defines a zone of proximity of the call in the shape of a polygon which is connected to its neighbours.

These zones define a pavement of the city, called Voronoï's mosaic. If one connects the stations in neighbouring areas, one obtains a randomly determined graph which represents the cables along which the call will travel.
Graphs, probability theory and geometry all join to allow you to communicate!

Experience on table

Go around The World

Choose a globe and try to find a path going through all stations only one time.

To remember

To find Hamilton’s path is to find a path which passes by each vertex only once.
At time, we haven’t found a general solution for this type of problem.
But Hamilton showed that there was solution for a regular dodecahedral polyhedron (a 12 faces polyhedron with regular pentagones).
On the drawing, can you draw this “hypercube” with one finger, pathing only once through all vertices? Idea & Realisation: Euler, Hamilton & Centre•Sciences – Illustration : JF Colonna