Peut-on parcourir tous les ponts d'une ville une seule fois chacun ? Le problème des ponts de Königsberg
Euler a montré en 1736 qu'un graphe connexe admet un chemin passant une fois par chaque arête seulement s'il a 0 ou 2 sommets de degré impair. Königsberg en a 4 (degrés 3, 3, 3 et 5) : la promenade est impossible. La somme des degrés, 14, vaut deux fois le nombre de ponts.
Grand oral session 2027 : exposé de 10 minutes debout, puis 10 minutes d'échange, sans calculatrice. Plan prévu pour 9,5 min.
Pourquoi cette question : un modèle d'introduction
Le jury attend que vous expliquiez pourquoi vous avez choisi la question. Inspirez-vous de ce modèle, mais racontez votre propre parcours.
J'ai découvert l'histoire des sept ponts de Königsberg, que les habitants essayaient de traverser chacun une fois lors d'une promenade, sans jamais y arriver. Euler a démontré que c'était impossible, en inventant au passage la théorie des graphes. J'ai trouvé admirable qu'un argument de parité règle définitivement la question, et j'ai voulu le refaire.
L'enjeu et les notions du programme
Démontrer une impossibilité par un argument de parité, et en déduire un critère algorithmique simple.
Mathématiques
- Raisonnement par l'absurde, parité (seconde)
- Dénombrement : compter deux fois la même chose (terminale)
- Pour aller plus loin : graphes, degré, chaîne eulérienne (maths expertes)
Numérique et sciences informatiques
- Graphes : sommets, arêtes, degré, connexité (terminale)
- Parcours de graphe (terminale)
Le plan de l'exposé en 9,5 min
1. Introduction
1 minLa ville de Königsberg comportait quatre quartiers reliés par sept ponts. Problématique : peut-on faire une promenade qui traverse chaque pont exactement une fois ?
2. Mathématiques : un argument de parité
4 minOn modélise : un sommet par quartier, une arête par pont. Le degré d'un sommet est le nombre d'arêtes qui en partent. Ici, les degrés sont 3, 3, 3 et 5.
Lemme des poignées de main : la somme des degrés vaut deux fois le nombre d'arêtes, car chaque arête est comptée par ses deux extrémités. 3+3+3+5=14=2×7. Conséquence : le nombre de sommets de degré impair est toujours pair.
Théorème d'Euler : lors d'une promenade, chaque passage par un sommet intermédiaire utilise deux arêtes (une pour entrer, une pour sortir). Un sommet qui n'est ni le départ ni l'arrivée a donc un degré pair. Seuls le départ et l'arrivée peuvent être de degré impair. Un chemin passant une fois par chaque arête impose donc 0 ou 2 sommets de degré impair. Königsberg en a 4 : c'est impossible.
Réciproquement (admis), un graphe connexe ayant 0 ou 2 sommets impairs possède un tel chemin.
3. NSI : vérifier et construire
3 minLe critère se programme facilement : on calcule le degré de chaque sommet à partir de la liste d'adjacence, on compte les degrés impairs et on vérifie la connexité par un parcours en profondeur. Le test coûte de l'ordre du nombre d'arêtes, alors qu'essayer tous les ordres de passage serait exponentiel.
Quand le chemin existe, l'algorithme de Hierholzer le construit. Applications : tournées de déneigement, de collecte des déchets ou de lecture des compteurs, où il faut parcourir chaque rue. Si le critère échoue, on ajoute des passages doublés sur certaines rues, au moindre coût : c'est le problème du postier chinois.
4. Conclusion
1,5 minLa promenade de Königsberg est impossible parce que quatre quartiers ont un nombre impair de ponts : un argument de parité suffit. Euler a ainsi fondé la théorie des graphes. J'ouvre sur le problème voisin des chemins passant une fois par chaque sommet, beaucoup plus difficile.
Ce que j'écris au tableau
Pas de calculatrice ni de support numérique : un calcul clé écrit au tableau rend l'exposé concret et montre la solidité des connaissances.
chemin eulérien ⇔ connexe et 0 ou 2 sommets de degré impair Königsberg : 4
Conclusion : la réponse à la question
Euler a résolu un problème de promenade par un raisonnement sur les degrés. L'impossibilité se démontre en une ligne, et le critère donne un algorithme rapide là où la recherche exhaustive serait sans fin.
Les questions probables du jury
Pendant les 10 minutesd'échange, le jury vous fait préciser et approfondir, sur tout le programme de vos spécialités en lien avec la question.
Pourquoi le nombre de sommets de degré impair est-il pair ?
La somme des degrés est paire (2 × nombre d'arêtes) ; une somme de nombres est paire seulement si les impairs sont en nombre pair.
Quel pont faudrait-il supprimer pour rendre la promenade possible ?
N'importe quel pont reliant deux quartiers de degré impair : il resterait 2 sommets impairs.
Et pour revenir au point de départ ?
Il faut un cycle eulérien : tous les degrés doivent être pairs.
Peut-on dessiner une enveloppe ouverte (carré + diagonales + toit) sans lever le crayon ?
Oui : elle a exactement deux sommets de degré impair, on part de l'un et on arrive à l'autre.
Comment tester la connexité en NSI ?
Par un parcours en largeur ou en profondeur depuis un sommet : le graphe est connexe si tous les sommets sont visités.
Les pièges qui coûtent des points
- Oublier l'hypothèse de connexité dans le critère.
- Confondre passer une fois par chaque arête (Euler) et par chaque sommet (Hamilton).
- Compter les ponts au lieu des degrés.
Revoir les notions
Autres questions : graphes et réseaux
- Comment un GPS trouve-t-il le plus court chemin sans essayer tous les itinéraires ?
- Comment classer les pages du web par importance en ne regardant que les liens entre elles ?
- Est-il vrai que tout le monde sur Terre est relié à n'importe qui par une chaîne de six connaissances ?
- Combien de créneaux faut-il au minimum pour organiser des examens sans qu'aucun élève n'en ait deux en même temps ?
Préparer l'oral, pas seulement le contenu
Gestion des 20 minutes de préparation, usage du tableau, posture debout, réponses au jury : la méthode complète, conforme aux règles de la session 2027.
Méthode : traiter une question de Grand oral →