Adultes · Reprendre les maths · ≈ 1 h 15
Des dessins aux graphes : degrés, parité et parcours eulériens · Graphes · Degrés et parité · Parcours eulériens
Sept ponts, une seule promenade ?
Un problème progressif pour découvrir les graphes sans prérequis à partir des sept ponts de Königsberg : abstraction d'une situation concrète, degrés, double comptage, parité et démonstration de l'impossibilité d'une promenade traversant chaque pont exactement une fois.
Objectifs
Ce que ce DM fait travailler
- 01Comprendre ce qu'un graphe conserve d'une situation concrète et ce qu'il oublie
- 02Utiliser le degré d'un sommet et un double comptage pour établir une propriété de parité
- 03Relier la parité des degrés aux extrémités d'un parcours utilisant chaque arête exactement une fois
- 04Modéliser les sept ponts de Königsberg et démontrer l'impossibilité de la promenade demandée
Notions
Notions utiles pour ce devoir
Ce problème mobilise notamment les notions suivantes.
- Savoir compter et distinguer nombres pairs et impairs ; les rappels utiles sont fournis dans le problème
- Aucune connaissance préalable des graphes n'est supposée
Méthode
Comment l’utiliser
Prévoir environ 1 h 15 et garder une trace des essais, y compris ceux qui échouent.
Écrire une solution justifiée avant d’ouvrir le corrigé, même si certaines questions restent incomplètes.
Repérer les différences de méthode, de précision et de rédaction plutôt que seulement les résultats.
Énoncé
Le devoir
Cet énoncé contient plusieurs cartes et graphes indispensables aux questions. Pour conserver exactement les figures validées, consultez le « Sujet PDF » dans la section Documents ci-dessus.
Continuer