🎛️ Essaie de traverser les 7 ponts
Clique sur un secteur pour démarrer, puis sur les ponts pour les traverser. Le but : passer une seule fois sur chacun des 7 ponts. Bonne chance — Euler te dira pourquoi c'est impossible.
Ponts traversés
0 / 7
Secteur actuel
—
Statut
Choisis un départ
Indice : chaque secteur a un nombre impair de ponts qui y arrivent. Euler dit que c'est rédhibitoire...
🏰 1736 : une ville prussienne, une énigme populaire
Königsberg (aujourd'hui Kaliningrad, en Russie) est au XVIIIᵉ siècle une ville prussienne traversée par la rivière Pregel. Cette rivière forme deux îles reliées entre elles et aux deux rives par 7 ponts.
Les habitants, après le repas du dimanche, se posent une énigme devenue célèbre :
« Peut-on partir d'un quartier, faire le tour de la ville en empruntant chacun des 7 ponts exactement une fois, et revenir au point de départ ? »
Personne n'y arrive. Mais personne ne sait non plus prouver que c'est impossible.
🎯 Euler entre en scène
Leonhard Euler (1707-1783), mathématicien suisse, est alors à Saint-Pétersbourg. Carl Ehler, le maire de Dantzig, lui écrit pour lui soumettre le problème. Euler répond d'abord que « la question lui paraît peu mathématique ». Puis il se ravise et publie en 1736 l'article « Solutio problematis ad geometriam situs pertinentis ».
Le coup de génie d'Euler : il abandonne la géométrie. Peu importent les distances, les formes des îles, les longueurs des ponts. Tout ce qui compte, c'est :
- Combien y a-t-il de quartiers (sommets) ?
- Combien de ponts (arêtes) relient chaque paire de quartiers ?
Pour Königsberg : 4 sommets (deux rives + deux îles) et 7 arêtes (les ponts). C'est le premier graphe de l'histoire des mathématiques.
🔑 La condition d'Euler : une histoire de parité
Euler observe : si tu fais un parcours qui passe par chaque arête une seule fois (un « parcours eulérien »), alors chaque fois que tu entres dans un sommet, tu en ressors. Sauf si c'est le départ ou l'arrivée.
Donc : pour un sommet « intermédiaire », le nombre d'arêtes qui y aboutissent (le degré) doit être pair (autant d'entrées que de sorties).
Théorème d'Euler (1736)
Un graphe connexe admet un cycle eulérien (revenant au départ)
⇔ tous ses sommets sont de degré pair.
Il admet un chemin eulérien (sans retour)
⇔ il a exactement 0 ou 2 sommets de degré impair.
❌ Königsberg : les 4 sommets sont impairs
À Königsberg, calcule les degrés :
- Île nord : 3 ponts (degré 3, impair).
- Île sud : 5 ponts (degré 5, impair).
- Rive nord : 3 ponts (degré 3, impair).
- Rive sud : 3 ponts (degré 3, impair).
4 sommets impairs > 2. D'après Euler, ni cycle ni chemin eulérien possible. Les habitants de Königsberg avaient raison empiriquement : aucune solution n'existe. Euler en donne la première démonstration mathématique.
📚 Vocabulaire fondateur
- Graphe G = (V, E) : ensemble de sommets V (« vertices ») et d'arêtes E (« edges »).
- Degré d'un sommet : nombre d'arêtes qui y sont incidentes.
- Connexe : on peut aller de n'importe quel sommet à n'importe quel autre.
- Cycle eulérien : parcours fermé qui emprunte chaque arête exactement une fois.
- Chemin eulérien : variante ouverte (départ ≠ arrivée).
- Cycle hamiltonien : variante stricte — passer une seule fois par chaque sommet (et non chaque arête). Beaucoup plus dur (NP-difficile).
🌍 Le 9 août 1944 : un pont en moins
Pendant la Seconde Guerre mondiale, les bombardements alliés détruisent 2 des 7 ponts. Königsberg devient Kaliningrad (URSS, 1946). Aujourd'hui, il reste seulement 5 ponts originaux, et les degrés des sommets ont changé : il existe maintenant un parcours eulérien possible. L'histoire a réglé l'énigme à coups d'explosifs.
🚀 Les graphes aujourd'hui : partout
Depuis Euler, la théorie des graphes a explosé. Quelques applications massives :
- Internet : modélisé comme un graphe géant (~50 milliards de pages web, chaque hyperlien = une arête).
- Réseaux sociaux : Facebook, X (Twitter), LinkedIn — chaque utilisateur est un sommet, chaque « ami »/« follow » est une arête. Théorie de Milgram (6 degrés de séparation), centralité, communautés.
- GPS et Google Maps : carte routière = graphe (carrefours = sommets, rues = arêtes pondérées par la distance/temps). Plus court chemin → Dijkstra (cf. concept suivant).
- Distribution électrique : transformateurs et lignes haute tension forment un graphe à équilibrer.
- Biologie : réseaux de neurones, interactions protéines-protéines, métabolomes, arbres phylogénétiques.
- Chimie : molécules = graphes (atomes = sommets, liaisons = arêtes).
- Logistique : optimisation des tournées (problème du voyageur de commerce), planification d'horaires, recettes Amazon.
- Compilateurs : analyse de flot de contrôle, graphes d'appels, coloration de registres.
- Cryptographie : graphes d'expansion, codes correcteurs LDPC (utilisés dans la 5G et le Wi-Fi).
📐 Le lien avec ton programme
Les graphes ne sont pas au programme BAC SM marocain, mais plusieurs notions s'y connectent directement :
- Parité : la preuve d'Euler repose entièrement sur l'arithmétique pair/impair. Programme arithmétique 2BAC SM.
- Récurrence : la plupart des théorèmes de graphes se démontrent par récurrence sur le nombre de sommets ou d'arêtes.
- Dénombrement : compter les chemins, les arbres couvrants, les cliques. Programme dénombrement 2BAC.
- Matrices (post-bac, prépa) : tout graphe a une matrice d'adjacence. La puissance Aⁿ donne le nombre de chemins de longueur n.
- Algorithmique : DFS, BFS, Dijkstra, A* — algorithmes que tu verras en info en prépa et en école d'ingé.
🎓 Une formule d'Euler bonus : V − E + F = 2
Toujours en 1750, Euler découvre une formule magique sur les graphes planaires (qui peuvent être dessinés sans croisements) :
V − E + F = 2
V = sommets, E = arêtes, F = faces (régions, y compris l'extérieur)
Cette formule s'applique aussi aux polyèdres convexes : pour un cube, V=8, E=12, F=6 → 8−12+6=2. Pour un tétraèdre, 4−6+4=2. Pour un dodécaèdre, 20−30+12=2. C'est un invariant topologique fondamental, généralisé au XXᵉ siècle en caractéristique d'Euler-Poincaré, base de toute la topologie algébrique moderne.