Note liminaire : Tout ce qui suit est une fiction narrative. Les résultats mathématiques sont historiquement documentés ; la conversation est inventée.
Königsberg est traversée par la rivière Pregel, qui forme une île et se divise en deux bras. Sept ponts relient les quatre zones de la ville. La question est simple : peut-on faire une promenade en traversant chaque pont exactement une fois, puis revenir au point de départ ?
Les habitants essayaient depuis longtemps, sans jamais y parvenir. Moi, j’ai prouvé que c'était impossible — et pour cela, j’ai dû inventer un nouveau type de mathématiques.
Mon premier geste a été de simplifier. La forme des rives, la longueur des ponts, la géographie — rien de tout cela n’importe. Seule compte la structure de connexion : quelles zones sont reliées par combien de ponts. J’ai remplacé la carte par un schéma abstrait — des sommets (les zones) reliés par des arêtes (les ponts).
C'était la naissance de ce que vous appelez un graphe.
Note historique : L’article d’Euler, Solutio problematis ad geometriam situs pertinentis (1736, publié en 1741), est considéré comme l’acte fondateur de la théorie des graphes et de la topologie. Euler y introduit la notion de graphe sans la nommer explicitement.
J’ai compté le nombre de ponts arrivant à chaque zone — ce qu’on appelle le degré d’un sommet :
| Zone (sommet) | Ponts (degré) | Pair ou impair ? |
|---|---|---|
| A | 5 | Impair |
| B | 3 | Impair |
| C | 3 | Impair |
| D | 3 | Impair |
Voici mon raisonnement. Si l’on traverse chaque pont exactement une fois et qu’on revient au point de départ (un circuit eulérien), alors à chaque sommet visité, on arrive par un pont et on repart par un autre. Chaque passage consomme donc deux arêtes. Conclusion : le degré de chaque sommet doit être pair.
Or à Königsberg, les quatre sommets ont un degré impair. La promenade est donc impossible. ∎
Théorème (Euler, 1736) : Un graphe connexe admet un circuit eulérien (parcours fermé passant par chaque arête exactement une fois) si et seulement si tous les sommets sont de degré pair.
Corollaire : Un graphe connexe admet un chemin eulérien (parcours ouvert) si et seulement s’il a exactement 0 ou 2 sommets de degré impair.
Exemples :
Euler s’intéresse aux chemins déterministes dans un graphe — on choisit où aller. Moi, j’ai ajouté le hasard. Imaginez qu'à chaque sommet, on lance un dé pour choisir l’arête suivante, avec des probabilités fixées. C’est une chaîne de Markov.
Le principe fondamental est la propriété de Markov : l'état futur ne dépend que de l'état présent, pas du passé. Si vous êtes au sommet B, la probabilité d’aller au sommet C est toujours la même, quel que soit le chemin qui vous a amené en B.
On peut alors représenter tout le système par une matrice de transition, et calculer l'évolution du système par multiplication matricielle.
Exemple : Un internaute navigue entre 3 pages A, B, C. À chaque page, il clique sur un lien au hasard.
| De \ Vers | A | B | C |
|---|---|---|---|
| A | 0 | 0,5 | 0,5 |
| B | 0,3 | 0 | 0,7 |
| C | 0,4 | 0,6 | 0 |
Chaque ligne somme à 1 (l’internaute va forcément quelque part). La matrice de transition est :
Après \(n\) clics, la distribution de probabilités est \(\pi_n = \pi_0 \cdot M^n\). À long terme, elle converge vers un état stable \(\pi\) indépendant du point de départ. C’est le principe de Google PageRank.
Mes graphes étaient statiques — une carte de connexions. Vous y avez insufflé le mouvement et le hasard. C’est une extension remarquable.
Et votre idée de base — réduire un problème concret à un schéma abstrait de sommets et d’arêtes — reste le fondement de tout ce que je fais. Sans graphe, pas de matrice de transition. Sans votre Königsberg, pas de PageRank.
Note historique : Andrei Markov publie sa théorie en 1906. Son premier exemple est l’analyse statistique de la succession des voyelles et consonnes dans Eugène Onéguine de Pouchkine. Aujourd’hui, les chaînes de Markov sont utilisées en physique (mouvement brownien), en biologie (modèles d'évolution), en informatique (PageRank, correcteurs orthographiques) et en finance (modèles de risque).
Partout ! Mon problème de promenade est devenu un outil universel :
Et les chaînes de Markov sont les graphes en mouvement :
| Date | Auteur | Contribution |
|---|---|---|
| 1736 | Euler (Königsberg) | Problème des 7 ponts, invention des graphes, théorème du circuit eulérien |
| 1847 | Kirchhoff (Allemagne) | Théorème des arbres couvrants (circuits électriques) |
| 1878 | Cayley (Angleterre) | Dénombrement des arbres (chimie moléculaire) |
| 1906 | Markov (Saint-Pétersbourg) | Chaînes de Markov, matrices de transition, état stable |
| 1936 | König (Hongrie) | Premier traité de théorie des graphes |
| 1998 | Brin & Page (Stanford) | PageRank — les chaînes de Markov au cœur de Google |
Idée centrale : Euler a inventé les graphes en montrant qu’un problème de promenade n’est pas un problème de géographie, mais un problème de structure. Markov a ajouté le hasard, et les matrices sont devenues un outil de prédiction. D’un problème de ponts au XVIIIe siècle au moteur de recherche Google — les mathématiques transforment les questions naïves en outils universels.