🌉 Königsberg, 1736 : un casse-tête pour les promeneurs
Königsberg (aujourd'hui Kaliningrad, en Russie) est traversée par la rivière Pregel, qui forme deux îles reliées entre elles et aux rives par 7 ponts.
Les habitants se posent la question : peut-on faire une promenade qui traverse chaque pont exactement une fois ? Personne n'y arrive en pratique. Est-ce physiquement possible ?
En 1736, le mathématicien suisse Léonard Euler, alors à Saint-Pétersbourg, s'attaque au problème. Sa solution va non seulement répondre à la question, mais aussi inventer une nouvelle branche des mathématiques : la théorie des graphes.
🎛️ Essaye toi-même
Clique sur les ponts pour les traverser. Réussis-tu à passer une seule fois par chacun en revenant au point de départ ?
🎛️ Les 7 ponts de Königsberg
Clique un sommet de départ, puis traverse les ponts un par un. But : tous les ponts, exactement une fois.
Ponts traversés
0 / 7
Clique d'abord sur un sommet pour démarrer.
🧠 La géniale abstraction d'Euler
Euler réalise une chose subtile : la forme exacte des îles et des ponts n'a aucune importance. Ce qui compte, c'est uniquement :
- Quels morceaux de terre sont connectés (les sommets)
- Par combien de ponts (les arêtes)
Il abstrait la carte en un dessin schématique : 4 points (les terres), reliés par des traits (les ponts). C'est le premier graphe de l'histoire des mathématiques.
📐 Le théorème d'Euler (1736)
Un graphe admet un parcours eulérien (passant exactement une fois par chaque arête) si et seulement si :
- Le graphe est connexe (d'un seul tenant), ET
- Il a 0 ou 2 sommets de degré impair (le degré = nombre d'arêtes connectées au sommet)
De plus, le parcours est fermé (revient au point de départ) si et seulement si tous les sommets sont de degré pair.
Pour Königsberg : les 4 sommets ont des degrés 3, 3, 3, 5 — tous impairs. 4 sommets impairs > 2. Donc le parcours est impossible. Euler démontre rigoureusement ce que les habitants pressentaient.
🌐 Une nouvelle science est née
À partir de cette question concrète, la théorie des graphes est née. C'est aujourd'hui un domaine immense :
- Cartes routières : villes = sommets, routes = arêtes (GPS, Plus Court Chemin)
- Réseaux sociaux : personnes = sommets, amitiés = arêtes
- Internet : pages web = sommets, liens = arêtes (PageRank de Google)
- Circuits électriques : composants = sommets, fils = arêtes
- Coloriage de cartes (théorème des 4 couleurs, concept Atlas)
- Voyageur de commerce (concept Atlas) — problème NP-complet sur graphes pondérés
- Bio-informatique : réseaux de gènes, métabolisme
🎯 Quelques résultats classiques
- Théorème d'Euler (parcours eulérien) : vu ci-dessus
- Théorème des 4 couleurs (Appel-Haken 1976) : tout graphe planaire est 4-coloriable
- Théorème de Cayley : nombre d'arbres étiquetés sur n sommets = nn−2
- Formule d'Euler pour les polyèdres : V − E + F = 2 (sommets − arêtes + faces)
- Algorithme de Dijkstra : plus court chemin entre 2 sommets, base du GPS
🌉 La question hamiltonienne
Une variante : peut-on passer une seule fois par chaque sommet (au lieu des arêtes) ? C'est le problème du cycle hamiltonien, beaucoup plus difficile que celui d'Euler.
En fait, déterminer si un graphe contient un cycle hamiltonien est NP-complet — même famille que le voyageur de commerce. Donc pas de réponse rapide en général. Étrange symétrie entre les deux problèmes : l'un (Euler) est en O(n), l'autre (Hamilton) résiste depuis 200 ans.
🎓 Programme BAC SM
Les graphes ne sont pas au programme officiel du BAC SM marocain (2026), mais certains concepts y touchent :
- Dénombrement (concept Atlas) : comptage des chemins dans un graphe
- Logique et raisonnement : démonstrations par cas, par récurrence sur le nombre de sommets
- Matrices (concept Atlas) : la matrice d'adjacence d'un graphe est un objet matriciel
- Algorithmes : BFS, DFS, Dijkstra — fondamentaux d'informatique théorique
🧠 Réflexion finale
L'histoire des ponts de Königsberg est une leçon de méthode en mathématiques. Euler n'a pas tenté toutes les promenades possibles. Il a fait quelque chose de plus profond : il a changé le problème. En abstrayant la situation, il a vu que ce qui comptait n'était ni la rivière, ni la ville, mais une structure abstraite.
C'est l'essence des maths : chercher la bonne abstraction. Pas la solution directe d'un problème, mais la structure générale dont ce problème n'est qu'un exemple. Maîtriser ça, c'est savoir penser comme un mathématicien.