🌉 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 =
- 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.
Vérifie ta compréhension
3 questions courtes pour valider tes acquis. Tu peux réessayer.