499

L’enseignement de la théorie des graphes à l’aide d’intrigues policières

Alain Hertz [1]

I. La phobie des mathématiques

Les mathématiques font peur à beaucoup élèves, il n’y a pas de doute là-dessus.
Certains en viennent même à détester cette matière qui est pourtant l’une des plus belles conquêtes intellectuelles de l’espèce humaine. Plusieurs raisons peuvent expliquer cette phobie des mathématiques, comme la crainte de ne pas comprendre ou la nature trop abstraite de nombreux concepts qui ne semblent avoir aucun lien avec une quelconque application pratique. Le manque de formation pédagogique de certains enseignants peut aussi largement contribuer à réduire l’intérêt des élèves pour cette science qui est pourtant indispensable pour bien comprendre la société, le monde dans lequel nous vivons. Ainsi, l’apprentissage des mathématiques se réduit parfois à des exercices reproductifs et les élèves ont alors l’impression que l’enseignement vise à leur apprendre à utiliser des mécanismes sans qu’ils doivent
nécessairement les comprendre.

Ce constat ne date pas d’hier et de nombreux enseignants investissent depuis longtemps beaucoup d’énergie, d’effort et de temps pour rendre leurs cours de mathématiques plus attractifs. Je ne pense pas qu’il existe une recette miracle qui agira comme un élixir ayant le pouvoir de transformer les mathématiques en la matière la plus captivante du cursus scolaire. Il est cependant indéniable qu’on
apprend mieux en s’amusant, lorsque l’enseignement comporte une composante ludique qui permet de retenir l’attention des élèves.

II. Mathématiques et intrigues policières

Les énigmes policières captivent généralement le grand public, d’où l’idée de présenter des concepts mathématiques, a priori abstraits, en les intégrant dans une enquête de police. Les producteurs de la série télévisée Numb3rs [1] ont su tirer profit de cette idée. Depuis 2005, cette série a attiré de nombreux spectateurs en leur contant l’histoire d’un agent du FBI qui trouve une aide précieuse auprès de son frère, mathématicien de génie, pour résoudre les enquêtes les plus délicates. Les nombres et les mathématiques en général sont utilisés pour analyser les crimes, révéler des tendances et tenter de prévoir des comportements. Les scénaristes ont fait appel à de vrais mathématiciens pour écrire leur scénario, de sorte que l’introduction des mathématiques dans une affaire relève du plausible.

Mais il n’y a pas qu’à la télé que les mathématiques sont rendues plus séduisantes à l’aide d’intrigues policières. Ainsi, par exemple, Andrew Granville, professeur de mathématique à l’Université de Montréal, a écrit une pièce de théâtre intitulée MSI (Math Sciences Investigation) : Anatomy of Integers and Permutations (Enquête au cœur des mathématiques : Anatomie des entiers et permutations) dont la première a eu lieu en décembre 2009 [2]. MSI met en scène des personnages inspirés de célèbres mathématiciens qui se trouvent projetés au cœur d’une énigme policière. D’après Andrew Granville, le public aime regarder ou écouter ce qu’il ne comprend pas toujours parfaitement, pour peu que cela lui soit présenté de manière divertissante.
Sa pièce de théâtre a pour but de rendre les mathématiques accessibles à un large public.

La littérature policière n’est pas en reste. Plusieurs enseignants en mathématiques ont coiffé la casquette de l’écrivain pour rendre cette science plus attractive. Ainsi, par exemple, avec son livre intitulé « Élémentaire mon cher Watson » [3], Colin Bruce présente douze enquêtes policières résolues grâce à la logique, aux mathématiques et aux probabilités. Pour sa part, Didier Müller propose un petit cours de cryptographie classique sous la forme d’un roman policier intitulé « Les 9 couronnes » [4]. J’ai moi-même écrit un roman policier relatant les enquêtes d’un inspecteur de police que tout le monde surnomme l’Agrapheur [5]. Ce surnom, mon inspecteur le doit à ses méthodes aussi efficaces que peu conventionnelles. Il dispose en effet d’un outil redoutable pour « agrafer » les coupables des affaires criminelles : la théorie des graphes. J’ai également rédigé des notes pédagogiques d’accompagnement [6] qui contiennent les fondements théoriques des intrigues policières.

En résumé, que ce soit par l’intermédiaire de l’audio-visuel, de l’art dramatique ou de la littérature, toutes les réalisations susmentionnées vont dans le même sens, à savoir d’offrir une approche ludique pour l’enseignement des mathématiques. Voilà peut-être de quoi réconcilier un large public avec une science trop souvent mal aimée.

III. Exemples d’énigmes mathématico-policières.

Les bases de la théorie des graphes sont en général enseignées en fin de secondaire ou dans les premières années d’enseignement supérieur. Aucune connaissance mathématique n’est nécessaire pour dessiner un graphe. Il suffit de prendre une feuille de papier, de choisir quelques emplacements en les marquant avec de petits cercles, et finalement d’ajouter quelques liaisons entre certaines paires d’emplacements. Les petits cercles sont appelés des sommets alors que les liaisons sont appelées des arêtes.

Le degré d’un sommet dans un graphe est le nombre d’arêtes dont ce sommet est l’extrémité. Un enseignant peut être intéressé à enseigner ce concept à ses étudiants en leur démontrant quelques propriétés qui s’y rattachent. Par exemple, il est bien connu que la somme des degrés d’un sommet est égale au double du nombre d’arêtes dans le graphe, ce qui conduit à la propriété suivante.

Propriété : La somme des degrés des sommets d’un graphe est toujours un nombre pair.

Pour donner un avant-goût de cette propriété à ses étudiants, l’enseignant peut débuter son cours en leur demandant de tracer 7 segments de droites sur une feuille de papier, de telle sorte que chaque segment ait une intersection avec exactement 3 des 6 autres segments. Pour illustrer sa question, l’enseignant peut dessiner au tableau 6 segments de droites ayant chacun une intersection avec exactement 3 des 5 autres segments. Un exemple d’une telle solution pour 6 segments est représenté ci-dessous.

Nous verrons ci-dessous qu’une telle construction est impossible à réaliser avec 7 segments, ce qui peut facilement être démontré à l’aide de la propriété susmentionnée. L’enseignant peut donc laisser cogiter ses élèves pendant quelques minutes et leur annoncer ensuite qu’il est inutile qu’ils s’occupent plus longtemps à tenter de résoudre ce problème car il n’a pas de solution. Avant de leur expliquer la raison de cette impossibilité, il peut leur proposer de résoudre l’énigme policière suivante.

Une énigme liée à la criminalité financière. Un inspecteur de police enquête sur une affaire de blanchiment d’argent. Il s’est construit une liste de 7 suspects et aimerait mieux connaître les activités professionnelles qui lient ces 7 personnes. Pour ce faire, il présente sa liste aux suspects et demande à chacun d’indiquer le nombre de personnes parmi les 6 autres avec qui ils ont déjà été en relation d’affaires. Chaque suspect répond que ce nombre est égal à 3, ce qui fait bondir de colère l’inspecteur qui s’écrie : « Vous ne me dites pas tous la vérité ! ».
Comment l’inspecteur peut-il être si sûr qu’au moins un suspect ment ?

La solution de l’énigme. La théorie des graphes permet de résoudre cette énigme aisément. En effet, construisons un graphe dont les sommets sont les suspects et relions deux suspects par une arête s’ils ont déjà été en relation d’affaires. Bien que les témoignages des 7 suspects ne permettent pas de construire le graphe en question, ils nous indiquent que chaque sommet est de degré 3. La somme des degrés des sommets est donc égale à 7 fois 3, soit 21.

C’est à cet instant que l’enseignant peut énoncer la propriété que la somme des degrés des sommets dans un graphe est toujours paire. Il peut facilement démontrer cette propriété en faisant remarquer qu’en additionnant les degrés des sommets d’un graphe, chaque arête est comptée deux fois, une fois dans le degré de l’une de ses extrémités et une autre fois dans le degré de l’autre extrémité. La somme des degrés des sommets est donc paire puisqu’elle est égale au double du nombre d’arêtes dans le graphe. Dans le graphe de l’énigme, si tous les suspects avaient dit la vérité, on aurait une somme des degrés paire, ce qui n’est pas notre cas puisqu’elle vaut 21.

L’enseignant peut maintenant également expliquer pourquoi la construction des 7 segments demandée en début de cours était impossible. On peut en effet construire un graphe en associant un sommet à chaque segment et en reliant deux sommets par une arête si les deux segments correspondants ont une intersection commune. À nouveau, si une telle construction était possible, on obtiendrait un graphe à 7 sommets de degré 3, ce qui donnerait une somme des degrés égale à 21, soit un nombre impair. Pour illustration, la solution à 6 segments donnée ci-dessus peut être représentée par le graphe ci-dessous dans lequel les sommets de gauche correspondent aux trois segments horizontaux alors que les sommets de droite correspondent aux trois segments verticaux. On a ici un graphe avec 6 sommets de degré 3, pour un total des degrés égal à 18, ce qui est bien égal au double du nombre d’arêtes de ce graphe.

L’énigme policière couplée avec le problème des 7 segments permet donc d’illustrer une propriété de base en théorie des graphes. Supposons maintenant qu’un enseignant désire bâtir un cours portant sur les graphes bipartis. Ces graphes ont la particularité qu’il existe une partition de leurs sommets en deux ensembles disjoints
tel que chaque arête relie un sommet du premier ensemble à un sommet du deuxième ensemble de la partition.
À titre d’illustration, le graphe dessiné ci-dessus est biparti puisque chaque arête relie l’un des trois sommets à gauche à l’un des trois sommets à droite. L’enseignant peut vouloir démontrer la propriété suivante.

Propriété. Étant donné trois sommets dans un graphe biparti, il existe nécessairement au moins deux de ces trois sommets qui ne sont pas reliés par une arête.

La preuve de la validité de cette propriété peut par exemple être donnée en considérant un triplet quelconque A,B,C de sommets dans un graphe biparti et en supposant que des arêtes relient le sommet A aux sommets B et C. Il reste alors à démontrer qu’il n’existe pas d’arête reliant B à C. Puisque chaque arête relie un sommet d’un ensemble de la partition à un sommet de l’autre ensemble, les arêtes reliant A à B et C nous indiquent que A fait partie de l’un des deux ensembles de la partition alors que B et C font partie de l’autre ensemble. Ainsi, puisque B et C font partie du même ensemble de la partition, ils ne peuvent pas être reliés par une arête.

Le concept de graphe biparti ainsi que la propriété démontrée ci-dessus peuvent paraître bien abstraits pour la majorité des élèves. Il me semble bien plus aisé d’enseigner ces notions en les présentant dans le cadre d’une intrigue policière L’énigme qui suit illustre parfaitement la technique que j’utilise pour préparer mes étudiants à la compréhension de telles notions abstraites grâce à des exemples concrets.

Une énigme liée à l’univers carcéral. Le directeur d’une prison décide d’organiser deux ateliers qui se dérouleront en parallèle et demande à sept détenus de participer à l’atelier de leur choix. Le lendemain, chacun des animateurs vient voir le directeur pour lui dire que seuls trois détenus ont pris part à leur atelier, ce qui signifie que l’un des sept détenus n’a participé à aucun des deux ateliers. Malheureusement, les animateurs n’ont pas constitué de liste de présence et, comme ils ne sont pas physionomistes, ils se sentent incapables d’indiquer avec certitude quels sont les détenus qui ont pris part à l’activité qu’ils avaient la charge d’animer.

Pour déterminer le détenu qui n’a participé à aucun des deux ateliers, le directeur décide d’interroger les sept détenus. De crainte de passer pour des délateurs, ceux-ci refusent d’indiquer les noms des camarades qui se trouvaient dans leur atelier, mais ils acceptent de donner chacun deux noms de détenus qui n’ont pas participé au même atelier qu’eux. Les témoignages sont résumés dans le tableau ci-dessous.

En analysant ce tableau, le directeur réussit à déterminer le coupable. Et vous, êtes-vous capable d’en faire autant ?

La solution de l’énigme. La théorie des graphes permet de résoudre cette énigme sans trop de difficulté. Construisons pour cela un graphe dont les sommets sont les détenus et relions deux détenus par une arête si au moins l’un des deux dit ne pas avoir vu l’autre dans son atelier. Le graphe représentant les témoignages est représenté ci-dessous.

Si les sept détenus avaient participé aux ateliers, ce graphe serait biparti. En effet, on pourrait considérer la partition des détenus en deux groupes selon l’atelier auquel ils ont pris part, ce qui signifierait que chaque arête relierait un détenu du premier groupe à un détenu du deuxième groupe puisque chaque témoignage indique que deux individus ne se sont pas rencontrés.

Le triangle reliant Alain, Bernard et Claude montre cependant clairement que le graphe de la Figure 1 n’est pas biparti. En effet, ces trois détenus prétendent ne pas s’être rencontrés dans les ateliers, ce qui ne serait possible que si trois (et non deux) ateliers avaient été organisés. En d’autres termes, étant donné un triplet de détenus, il doit nécessairement exister au moins deux parmi eux qui ne sont pas reliés par une arête. Il existe donc nécessairement un menteur parmi Alain, Bernard et Claude. La même conclusion peut être tirée du triangle reliant Claude, Edgar et Georges. Étant donné que Claude est le seul détenu qui fait partie de ces deux triplets, il est la personne recherchée. Lorsqu’on ôte Claude du graphe, il ne reste que 6 détenus qui peuvent cette fois bel et bien être répartis en deux groupes de trois personnes représentés ci-dessous par les couleurs noires et blanches. On remarque que chaque arête relie un sommet noir à un sommet blanc, c’est-à-dire un détenu du premier groupe de la partition à un détenu du deuxième groupe. Il s’agit donc bien d’un graphe biparti.

La résolution de cette énigme a donc permis d’illustrer le concept de graphe biparti ainsi que la propriété susmentionnée.

IV. Conclusion

Bien d’autres concepts de la théorie des graphes peuvent être illustrés à l’aide d’intrigues policières. J’en suis bien sûr convaincu puisque j’ai inventé une énigme pour chaque notion de base de la théorie des graphes. Alors que je demande à mes étudiants de résoudre ces intrigues dans le cadre de devoirs à domicile, d’autres enseignants préféreront peut-être faire lire une énigme et sa solution à leurs élèves, en leur demandant ensuite de jouer l’histoire sous la forme d’une pièce de théâtre.

Pendant la représentation théâtrale, on pourrait également demander à quelques étudiants d’écrire au tableau les raisonnements mathématiques utilisés pour résoudre l’énigme et de dessiner les graphes apparaissant dans l’histoire. Le but est de s’assurer que tous les étudiants puissent créer dans leur esprit une image claire des concepts que l’enseignant va vouloir introduire par la suite de manière plus formelle.
Cet enseignement plus classique qui suivra la résolution de l’intrigue sera facilement assimilé par les étudiants grâce à l’aventure qu’ils viennent de vivre de manière théâtrale et aux notes inscrites sur le tableau.

Mes étudiants adorent ce genre d’enseignement qui sort de l’ordinaire et je suis persuadé qu’une telle pratique permet de réconcilier beaucoup d’élèves avec l’apprentissage des sciences. Mon expérience pédagogique m’a en tout cas convaincu qu’il est réellement possible d’enseigner une branche des mathématiques en captivant ses élèves.

Bibliographie

[1] Columbia Broadcasting System (CBS). Site officiel de la série Numb3rs. Adresse URL : http://www.cbs.com/primetime/numb3rs

[2] Sylvain-Jacques Desjardins. Lumières, rideaux, arithmétique : Andrew Granville met les mathématiques en scène. UdeMNouvelles, Communiqué du 10 décembre 2009.

[3] Colin Bruce. Élémentaire mon cher Watson. Flammarion. Janvier 2002. ISBN : 2-080353-55-1

[4] Didier Müller. Les 9 couronnes. Société jurassienne d’émulation. Juin 2009. ISBN : 2-940043-41-8.

[5] Alain Hertz. L’Agrapheur - intrigues policières à saveur mathématique. Presses Internationales Polytechnique, Canada. Mars 2010. ISBN : 978-2-553-01543-4
(Le livre est également disponible en France, à la librairie Lavoisier)

[6] École Polytechnique de Montréal. Site Web du livre l’Agrapheur. Adresse URL : http://www.polymtl.ca/pub/sites/lagrapheur.

<redacteur|auteur=500>

Notes

[1Professeur à l’École Polytechnique de Montréal.

Les Journées Nationales
L’APMEP

Publications
Ressources

Actualités et Informations
Base de ressources bibliographiques

 

Les Régionales de l’APMEP