Découvrir
La ville de Königsberg avait sept ponts. Peut-on faire une promenade qui traverse chaque pont exactement une fois ? En 1736, Euler répond.
- Non, c'est impossible
- Oui, en partant du bon endroit
L'idée clé
Des ponts de Königsberg aux chaînes de Markov.
- Étape 1Leonhard Euler 1707–1783Jakob Emanuel Handmann, 1753. Domaine public1736 : Euler démontre qu'on ne peut pas traverser les sept ponts une seule fois chacun.
- Étape 2Andreï Markov 1856–1922Auteur inconnu, 1886. Domaine publicMarkov (1856–1922) : chaînes où le futur ne dépend que du présent ; voyelles et consonnes.
En 1736, Euler résout le problème des ponts de Königsberg : un graphe a un chemin passant une fois par chaque arête seulement s'il a 0 ou 2 sommets de degré impair. Andreï Markov (1856–1922) étudie les chaînes qui portent son nom, où le futur ne dépend que du présent ; il les applique aux voyelles et consonnes d'un texte littéraire.
À Königsberg, en Prusse, il y a une île, entourée par deux bras de la rivière, et sept ponts. On demande si quelqu'un peut organiser sa promenade de façon à passer une fois et une seule sur chacun des ponts.
Qu'est-ce qui compte vraiment pour répondre ?
- Quelles rives et îles chaque pont relie, pas les distances
- La longueur de chaque pont
Exemple corrigé
Königsberg : quatre zones reliées par sept ponts ; les degrés sont 5, 3, 3 et 3.
Entraînement ★
- À quoi Markov a-t-il appliqué ses chaînes ?
- Aux voyelles et consonnes d'un texte littéraire
- Aux ponts de Königsberg
- Aux moteurs de recherche
- Un graphe a 11 sommets, tous de degré 4. Combien a-t-il d'arêtes ?
- Un graphe a 8 sommets, tous de degré 4. Combien a-t-il d'arêtes ?
- Dans tout graphe, la somme des degrés vaut le double du nombre d'arêtes (c'est pourquoi les sommets impairs vont par paires, comme chez Euler). Un graphe a 15 arêtes : quelle est la somme des degrés ?
Fiche résumé
Les graphes aujourd'hui
- GPS et livraisons : plus courts chemins dans un réseau routier.
- Réseaux sociaux : qui est relié à qui.
- Prédiction de texte : le mot suivant dépend des mots précédents, comme chez Markov.
Sources : article de MacTutor sur l'histoire de la topologie ; biographie de Markov (voir « Sources et crédits »).