Histoire des graphes : Euler et Markov

Lessons and exercises follow the school system and stay in its language.Les leçons et les exercices suivent le système scolaire et restent dans sa langue.Lektionen und Übungen folgen dem Schulsystem und bleiben in seiner Sprache.

À propos de cette leçon

Terminale, mathématiques expertes › Chaînes de Markov

Pour obtenir un PDF, choisis « Enregistrer au format PDF » dans la fenêtre d'impression.

Sources et crédits

Écrit à partir de cette source :

sedifier a réécrit le texte et ajouté ses propres exemples et exercices.

Rédigé avec l'aide d'une IA ; chaque réponse est vérifiée par notre moteur de calcul. Pas encore relu par un enseignant.

Cette leçon : CC BY-SA 4.0, © sedifier · Tous les crédits

Histoire des graphes : Euler et Markov

Chaînes de Markov. chaîne de Markov, matrice de transition, distribution invariante

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.

  1. Non, c'est impossible
  2. Oui, en partant du bon endroit

L'idée clé

Des ponts de Königsberg aux chaînes de Markov.

17501800185019001736Euler1736Euler
  1. Étape 117501800185019001736Euler1736EulerLeonhard Euler 1707–1783Jakob Emanuel Handmann, 1753. Domaine public1736 : Euler démontre qu'on ne peut pas traverser les sept ponts une seule fois chacun.
  2. Étape 217501800185019001736Eulervers 1900Markov1736Eulervers 1900MarkovAndreï 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.

Source

À 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.

Leonhard Euler, Solutio problematis ad geometriam situs pertinentis, 1736 : le problème qu'il pose, résumé avec nos mots

Qu'est-ce qui compte vraiment pour répondre ?

  1. Quelles rives et îles chaque pont relie, pas les distances
  2. 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.

4
Sommets de degré impair.
promenade impossible
Plus de 2.

Entraînement ★

  1. À quoi Markov a-t-il appliqué ses chaînes ?
    1. Aux voyelles et consonnes d'un texte littéraire
    2. Aux ponts de Königsberg
    3. Aux moteurs de recherche
  1. Un graphe a 11 sommets, tous de degré 4. Combien a-t-il d'arêtes ?
  2. Un graphe a 8 sommets, tous de degré 4. Combien a-t-il d'arêtes ?
  1. 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 »).

Fin de la leçon

Sources et crédits

Écrit à partir de cette source :

sedifier a réécrit le texte et ajouté ses propres exemples et exercices.

Rédigé avec l'aide d'une IA ; chaque réponse est vérifiée par notre moteur de calcul. Pas encore relu par un enseignant.

Cette leçon : CC BY-SA 4.0, © sedifier · Tous les crédits