En réponse au problème des ponts de Königsberg
(voir page 170), Leonhard Euler rédige un article appelé
Solutio problematis ad geometriam situs pertinentis, que l’on trouve dans les mémoires de l’Académie des Sciences de Berlin (1759).
Les trois figures ci‑contre en sont extraites.
Cet article a donné naissance à la théorie des graphes.
La figure 1 représente la situation de Königsberg et la figure 3 une situation inventée par Euler pour illustrer le résultat qu’il venait de découvrir. La figure 2 sert à établir une partie de son résultat : si l’itinéraire à suivre contient
n ponts à emprunter une et une seule fois, alors il reliera
n+1 zones.
Tout d’abord, Euler constate que le nombre de ponts qui relient chacune des quatre zones de Königsberg est impair et donc que le problème n’a pas de solution. Expliquer ce raisonnement.
Dans la suite de
Solutio Problematis ad Geometriam Situs Pertinentis, Euler s’attache à trouver un raisonnement généralisable à toute situation.
Dans les paragraphes 11 et 12, Euler montre que si le nombre de ponts qui donnent sur une région A est impair, c’est‑à‑dire qu’il existe un entier naturel
p tel que le nombre de ponts soit égal à
2p−1, alors l’itinéraire passe
p fois par cette région A.
a) À partir de la figure 1, compléter le tableau ci‑dessous de la situation de Königsberg.
Zones |
A |
B |
C |
D |
Somme |
Nombres de ponts |
5 |
3 |
3 |
3 |
|
p |
|
|
|
|
|
b) Expliquer pourquoi le problème des ponts de Königsberg n’a pas de solution.
Dans les paragraphes 13 à 15, Euler démontre le résultat général : si le nombre de ponts qui donnent sur une région A est pair, c’est‑à‑dire que s’il existe un entier naturel
p tel que le nombre de ponts soit égal à
2p, alors cette région A devra figurer
p+1 fois dans l’itinéraire si on part de cette région, ou
p fois si on ne fait qu’y passer. Il s’invente la ville représentée en figure 3. En complétant le tableau ci‑dessous, déterminer si on peut suivre ou non un parcours dans cette ville, en empruntant une, et une seule, fois chaque pont.
Zones |
A |
B |
C |
D |
E |
F |
Somme |
Nombres de ponts |
|
|
|
|
|
|
|
p |
|
|
|
|
|
|
|