Product Design, Manufacturing & Innovation Resources
Maison » Les sept ponts de Königsberg

Les sept ponts de Königsberg

1736
  • Leonhard Euler
Königsberg bridge problem map illustrating Euler's graph theory foundation.

(Image générée à titre d'illustration uniquement)

Il s'agit d'un problème historique important en mathématiques. Sa résolution négative par Leonhard Euler en 1736 a jeté les bases de la théorie des graphes et préfiguré l'idée de topologie. Le problème demandait si les sept ponts de la ville de Königsberg pouvaient tous être traversés en un seul voyage sans revenir sur ses pas, le voyage se terminant sur la même masse terrestre qu'au départ.

La ville de Königsberg en Prusse (aujourd'hui Kaliningrad, en Russie) était située de part et d'autre de la rivière Pregel et comprenait deux grandes îles reliées l'une à l'autre, et au continent, par sept ponts. Le problème était de trouver un chemin à travers la ville qui traverserait chacun de ces ponts une fois et une seule. Euler a eu l'idée d'abstraire le problème en supprimant toutes les caractéristiques, à l'exception des masses terrestres et des ponts qui les relient. Il a représenté chacune des quatre masses terrestres comme un point (un sommet) et chaque pont comme une ligne (une arête) reliant les sommets. La structure mathématique qui en résulte est un graphe. Euler s'est rendu compte qu'un chemin traversant chaque arête exactement une fois (un chemin eulérien) n'est possible que si le graphe est connecté et a zéro ou deux sommets de degré impair (le degré étant le nombre d'arêtes connectées à un sommet). Le graphe de Königsberg avait quatre sommets, tous de degré impair (un de degré 5 et trois de degré 3). Euler a donc prouvé qu'un tel chemin était impossible. Cette solution est considérée comme le premier théorème de la théorie des graphes et l'un des premiers résultats en topologie, car elle ne dépend pas de mesures ou d'une géométrie spécifique, mais uniquement de la connectivité du graphe.

UNESCO Nomenclature: 1203
- Géométrie

Taper

Système abstrait

Perturbation

Fondamentaux

Usage

Utilisation généralisée

Précurseurs

  • Concepts de base de la géométrie d'Euclide
  • Problèmes combinatoires précoces et mathématiques récréatives

Applications

  • le routage des réseaux (par exemple, le trafic internet, la logistique)
  • conception de circuits
  • séquençage du génome
  • recherche opérationnelle
  • l'analyse des réseaux sociaux

Brevets:

NA

Idées d'innovations potentielles

En raison du trafic généré par les robots de scraping, actuellement supérieur à 40 000 par jour, ce contenu est réservé aux membres de la communauté.
> Connexion < ou > Registre < (100% gratuit) pour y accéder, ainsi qu'à tous les autres contenus et outils à accès restreint.

En rapport avec : Königsberg, Euler, théorie des graphes, chemin eulérien, sommet, arête, topologie, analyse des réseaux.

Contexte historique

Les sept ponts de Königsberg

-550
1635
1650
1736
1750
1763-12-23
1780
-500
150
1640
1650
1747
1758
1777
1799

(si la date est inconnue ou non pertinente, par exemple « mécanique des fluides », une estimation arrondie de son émergence notable est fournie)

Inventions, innovations et principes techniques connexes

Les images en pleine résolution et les téléchargements sont uniquement disponibles, et 100% gratuits, pour les membres inscrits.