Maison » Les sept ponts de Königsberg

Les sept ponts de Königsberg

1736
  • Leonhard Euler
Carte du problème du pont de Königsberg illustrant les fondements de la théorie des graphes d'Euler.

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

Type

Système abstrait

Perturbation

Fondamentaux

Utilisation

Une utilisation répandue

Précurseurs

  • Concepts de base de la géométrie 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
  • la recherche opérationnelle
  • l'analyse des réseaux sociaux

Brevets :

NA

Innovations potentielles Idées

!niveaux !!! Adhésion obligatoire

Vous devez être membre de l'association pour accéder à ce contenu.

S’inscrire maintenant

Vous êtes déjà membre ? Connectez-vous ici
En rapport avec : Königsberg, Euler, théorie des graphes, chemin eulérien, sommet, arête, topologie, analyse des réseaux.

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *

DISPONIBLE POUR DE NOUVEAUX DÉFIS
Ingénieur mécanique, chef de projet, ingénierie des procédés ou R&D
Développement de produits efficace

Disponible pour un nouveau défi dans un court délai.
Contactez-moi sur LinkedIn
Intégration électronique métal-plastique, Conception à coût réduit, BPF, Ergonomie, Appareils et consommables de volume moyen à élevé, Production allégée, Secteurs réglementés, CE et FDA, CAO, Solidworks, Lean Sigma Black Belt, ISO 13485 médical

Nous recherchons un nouveau sponsor

 

Votre entreprise ou institution est dans le domaine de la technique, de la science ou de la recherche ?
> envoyez-nous un message <

Recevez tous les nouveaux articles
Gratuit, pas de spam, email non distribué ni revendu

ou vous pouvez obtenir votre adhésion complète - gratuitement - pour accéder à tout le contenu restreint >ici<

Contexte historique

(si la date est inconnue ou n'est pas pertinente, par exemple "mécanique des fluides", une estimation arrondie de son émergence notable est fournie)

Invention, innovation et principes techniques connexes

Retour en haut

Vous aimerez peut-être aussi