Auteur : Alain Busser

Titre : Jeux et graphes
Sous-titre : La théorie des graphes de 5 à 95 ans
Collection : Références sciences
Editeur : Ellipses
ISBN : 9782340101494
240 pages
2ème édition de mars 2025. (1ère édition : septembre 2020)
Format : 19 cm × 24 cm

Cela fait maintenant plus de 10 ans que je côtoie Alain Busser via nos activités communes dans la revue MathémaTICE et si cette recension commence ainsi ce n’est pas pour mettre en évidence le fait que l’on m’a demandé de dire du bien de son livre « Jeux et graphes. La théorie des graphes de 5 à 95 ans. » C’est plutôt pour signifier que le fait de bien connaître Alain, de partager un travail de bénévolat dans la revue m’a permis de reconnaître dans l’ouvrage « le Alain » qui anime notre comité.
Alain Busser est un enseignant singulier, tout aussi singulier que son île, la Réunion, qui revient sans cesse dans les messages qu’il partage avec nous. Alain est un volcan, comme le Piton de la Fournaise, capable de rentrer en éruption et de produire plusieurs articles sur ses sujets de prédilection en quelques semaines, comme en témoigne sa prolifique activité pour MathémaTICE, mais aussi pour l’IREMI de la Réunion et pour d’autres revues. Sa grande expérience du terrain et même des terrains les plus exotiques l’amènent à nous raconter mille anecdotes : à chaque question qui se pose dans le comité, Alain se remémore un sujet connexe, établit un pont vers un îlet [1] que nous avions tous oublié. Alain, c’est ainsi quelqu’un qui invite au Voyage [2] à travers le pays des mathématiques, avec une jolie plume, capable de nous tenir informé des dernières nouveautés tout comme de créer de toute pièces un langage de programmation (Sofus). Et Alain, c’est enfin quelqu’un dans lequel je vois la profonde certitude que tout le monde est capable de parcourir les sentiers de la connaissance, même les plus isolés comme s’il fallait se rendre à Mafate [3]. C’est donc sans surprise que le sous-titre de son ouvrage appelle les plus jeunes « lecteurs » (dès 5 ans) à s’émanciper tout autant que ceux qui abordent leur trentième année de retraite. Une cible de lectorat qui n’est pas vraiment aussi large pour la maison d’éditions Ellipses habituellement.

A travers cette recension, je vous propose de suivre les traces d’Alain Busser dans une sorte de « road-movie mathématique », à travers le temps et l’espace.

Lieu de rendez-vous

Dans l’avant-propos, nous apprenons que le point de départ de ce voyage est situé à Grand-Îlet dans le cirque de Salazie en mars 2018. Alain Busser y accompagne la caravane de l’IREM de la Réunion de villages en villages, à la rencontre des écoliers du premier degré. Il y anime des ateliers pour présenter la théorie des graphes. Mais catastrophe, une méprise au moment de la rotation des groupes d’élèves et Alain Busser se retrouve sans le réaliser avec une classe de Grande Section de Maternelle (âgés de 5 ans) ! Les élèves sont lancés avec enthousiasme, personne n’ose les arrêter alors que l’atelier est prévu pour des enfants plus âgés. Alain les observe et comprend que finalement la théorie des graphes peut être ouverte à de tout jeunes enfants. Ainsi naît le projet du livre que j’essaye de vous présenter.

Matériel de voyage

Le chapitre 1 « Vocabulaire » fait un point indispensable sur le matériel de voyage afin de poursuivre l’aventure au pays des graphes.
Il faut se munir sans aucun doute de définitions. Celles-ci sont présentées de manière pédagogique avec de nombreux schémas explicatifs.

Un graphe est défini par
– Un ensemble de sommets (en général représentés par des cercles)
– Un ensemble d’arêtes (en général représentés par des traits), chaque arête joignant deux sommets.

Rapidement, les graphes deviennent orientés et les arêtes prennent alors le nom d’arcs lorsqu’une flèche vient leur donner un sens de parcours. On établit alors le parallèle avec des rues à sens unique. Les explications fournies se veulent ludiques (espionnage, réseaux sociaux) pour laisser s’installer le fantasme d’un voyage accessible et inoubliable chez chacun. On précise également que les plus jeunes voyageurs (maternelle) ont peu de difficultés pour s’emparer de ce matériel, quitte à l’adapter un peu à leurs capacités psychomotrices.

Par exemple, ici Alice espionne Daisy (en la suivant sur les réseaux), c’est ce qu’indique l’arc orienté allant du sommet « Alice » au sommet « Daisy ». La réciproque est vraie. Alice suit également Carole, mais par contre Carole ne suit pas Alice. Enfin, aucun suivi n’est en place entre Bob et Carole, ni dans un sens ni dans l’autre.

On définit ensuite la notion de degré entrant et de degré sortant d’un sommet comme étant le nombre d’arcs orientés qui y arrivent ou en repartent. Selon l’auteur, cette notion est accessible dès le CP.
On peut ensuite essayer de colorier les graphes avec des couleurs différentes pour les sommets adjacents, ce qui est tout à fait adapté à l’activité d’enfants de Maternelle. On veillera alors à utiliser en Grande Section le nombre minimum de couleurs possibles, ce qui correspond à ce que l’on appelle le nombre chromatique du graphe.

Il faut se munir enfin de quelques polyèdres qui sont en quelque sorte des représentations tridimensionnelles des graphes à la manière de Casimir Kuratowski (en 1930).

Représentation en perspective du tétraèdre

Le graphe du tétraèdre

Le graphe du cube

Le chapitre s’achève par des définitions qui concernent davantage les lecteurs et les lectrices un peu plus expérimentées :
– le graphe complet qui est celui où deux sommets quelconques sont toujours adjacents (comme par exemple le tétraèdre) ;
– le graphe homogène qui a tous ses sommets de même degré (comme par exemple l’octaèdre) ;
– le graphe cubique qui a tous ses sommets de degré 3 (comme par exemple le cube ou le prisme droit à base hexagonale) ;
– le graphe planaire qui admet une représentation où aucune arête ne vient en croiser une autre ;
– le graphe bipartite qui possède un regroupement de ses sommets en deux parties.

A cette occasion sont présentées de manière presque anecdotique deux solides ou graphes de Kuratowski qui pourtant vont jouer un rôle important dans la suite de l’ouvrage : $K_{3,3}$ et $K_{5}$. En voici une représentation :

Deux graphes historiquement importants

Aucun des deux n’est planaire.

Quelques passe-temps pour un long voyage ?

Alain Busser n’ignore pas que les jeunes enfants à qui il a destiné une part de son premier chapitre sont non lecteurs. Ainsi, il s’adresse à leurs guides, ceux qui les accueillent dans les classes de la Réunion ou de Navarre. Et quoi de plus naturel pour des jeunes élèves que de se frayer un chemin vers les apprentissages par le jeu et notamment par des activités de coloriage.
Le chapitre 2, intitulé "Coloriage" présente plusieurs jeux où les graphes tiennent le premier rôle.

– Planarity, jeu de téléphone portable dont le but est d’obtenir une représentation planaire d’un graphe qui ne l’était pas au départ ;
– le jeu de Snort [4] qui consiste à colorier les sommets d’un graphe planaire contre un adversaire jusqu’à ce que l’un des joueurs soit contraint de colorier un sommet adjacent à un sommet déjà colorié par la partie adverse. Ce qui signifie la défaite. Par exemple, ici, le joueur bleu qui doit jouer le prochain coup, a perdu la partie.

Le livre permet d’apprendre quelques anecdotes et ouvre sur la recherche de stratégie gagnante.
Le lecteur intéressé peut retrouver sur l’internet des ressources complémentaires d’Alain Busser : jeu en ligne ou
cet article récent dans Repères-Irem sur le sujet.
– le jeu de Col [5]. Ce jeu entre 2 joueurs, qui se déroule sur graphe planaire également, consiste à ne jamais colorier de la même couleur deux sommets adjacents. Le perdant est donc celui qui y est contraint par son adversaire.
Ainsi dans cette situation, le joueur qui colorie en rouge et dont c’est le tour a perdu la partie :

La présentation de ces jeux aurait pu s’accompagner de "plateaux" prêts à l’emploi car devant la multiplicité des graphes, il est peu évident de savoir si le graphe auquel on a pensé offre un terrain de jeu stimulant ou non.

Le chapitre se poursuit par l’explication de la notion de coloration propre et de nombre chromatique.
Une coloration est dite propre si deux sommets adjacents ne sont jamais de la même couleur et le nombre chromatique est le nombre minimum de couleurs qu’il faut pour colorier le graphe de façon propre. Cela rappellera peut-être au lecteur l’étude du coloriage des cartes géographiques sans que deux pays limitrophes ne soient de la même couleur. On retrouve ainsi page 43 le théorème des 4 couleurs, démontré avec l’assistance de l’ordinateur en 1976 après plusieurs échecs retentissants, qui est en fait transposable en termes de graphes et devient alors :

tout graphe planaire est coloriable (proprement) avec 4 couleurs au maximum. Ou encore son nombre chromatique est inférieur ou égal à 4.

4 couleurs suffisent pour colorier toute la carte (Source Wikipedia)

Au passage, nous aurons appris sous quelles conditions réduire le nombre de couleurs nécessaires à 3, voire même à 2.
L’ensemble du chapitre constitue un univers d’activités de coloriage qui peuvent être développées auprès des très jeunes générations, à partir de la Moyenne ou de la Grande Section.

La multiplicité de ces activités ludiques et manipulatoires donne donc du grain à moudre pour une part du lectorat. Mais la grande force du livre d’Alain Busser est de parvenir à proposer en parallèle le développement d’exemples et de connaissances pour tous les publics, y compris en présentant des concepts délicats comme les problèmes NP [6] ou en explicitant l’état des recherches actuelles. C’est en ce sens que le sous-titre de l’ouvrage se trouve pleinement justifié.
D’autre part, la recherche d’un coloriage optimal a forcément du succès à tout âge si l’on se pique au jeu. Le chapitre s’achève justement par le parallèle avec l’un des jeux de logique préférés des adultes, le Sudoku, dont la résolution peut être assimilée au coloriage propre d’un graphe.

De Bâle à Saint-Pétersbourg

Dans le chapitre 3, nommé "Parcours", le voyage commence à proprement dit en suivant les traces de Leonhard Euler, grand chercheur suisse, expatrié dans l’Empire russe et en Allemagne à partir de 1727. C’est l’occasion de présenter un autre aspect des graphes : parcourir leurs arêtes selon des règles bien spécifiques ou autrement dit "promener un pion" sur un graphe non orienté.

La promenade commence "à cheval" avec le fameux problème du cavalier qui est un problème logique fondé sur les déplacements du cavalier du jeu d’échecs : un cavalier partant d’une case quelconque doit visiter chaque case sans jamais y repasser. Euler prouve qu’un tel déplacement est impossible dans un échiquier 4X4 avant de publier en 1759 à l’Académie de Saint-Pétersbourg plusieurs solutions pour un échiquier 5X5 et par extension un échiquier 10X10 et surtout une ribambelle de solutions élégantes pour l’échiquier standard 8X8 [7].

Source Wikipedia

Cette reproduction laisse apparaître la parenté avec les graphes et montre également qu’un cavalier ne peut que passer d’une case à une autre case de couleur différente, ce qui induit un graphe bipartite où les sommets adjacents sont nécessairement de couleurs différentes.

C’est l’occasion de définir les concepts assez intuitifs de chemin dans un graphe non orienté (tous les sommets sont de degré 2 sauf éventuellement le départ et l’arrivée) et de chemin hamiltonien (chemin passant par tous les sommets du graphe). Les illustrations de l’ouvrage permettent de bien assimiler ces notions dans le cadre du problème de l’échiquier 4X4.

Une halte à Königsberg (Kaliningrad)

On trouve dans ce même chapitre l’un des problèmes les plus célèbres de la théorie des graphes : le problème des 7 ponts de Königsberg. Celui se résume par une question simple au regard du plan de la ville :

Les 7 ponts de Königsberg (Source Wikipedia)

Comment établir un circuit touristique au travers de Königsberg, qui passe une fois et une seule par chacun des 7 ponts sur la Pregel ?

Pour résoudre ce problème, on découvre la notion de multigraphe (graphe où il est possible d’avoir plusieurs arêtes entre deux sommets adjacents). On représente les "quartiers" de la ville par des sommets A, B, C, D reliés par des arêtes que sont les différents ponts. En gardant la disposition spatiale du plan ci-dessus, on obtient le multigraphe :

Mais le caractère obligatoire de ne franchir qu’une seule fois chaque pont (et donc dans des sens différents entre A et B) permet d’éliminer du graphe des parcours (circuits) comme A->B->A et A->C->A, sinon on ne pourrait plus quitter un quartier. Le graphe se réduit donc à :

Ce qui apporte définitivement une réponse en forme de constat d’échec. On dit que ce graphe n’est pas eulérien (il ne possède pas de chemin passant une fois et une seule par chaque arête.)

Histoire de ne pas spoiler l’intégralité du livre, je laisse au lecteur du livre d’Alain Busser le plaisir de découvrir à quelle condition un graphe est eulérien ainsi que le lemme des poignées de main (page 57). Car quand on voyage, c’est bien connu, on rencontre beaucoup de gens !

Le chapitre s’achève sur de nouvelles ouvertures sur les jeux et en particulier sur ceux qui peuvent intéresser les enseignants du premier degré : jeu de l’oie, des petits chevaux. Est suggérée notamment l’idée de produire son propre plateau de jeu de l’oie et les règles qui y correspondent par l’intermédiaire d’un graphe orienté. C’est aussi l’occasion de parler de chaînes de Markov et d’en montrer des représentations par l’intermédiaire de graphes orientés munis d’un pion et sur lesquelles des probabilités conditionnelles viennent agrémenter les arêtes. Les exemples typiques de marche aléatoire et d’urnes d’Ehrenfest sont présentés. Cette approche vient compléter celle plus classique des chaînes de Markov par l’intermédiaire des matrices de transition.

Graphes et chaînes de Markov

Les pages 58 à 68 intéresseront donc les enseignants du second degré (ou leurs élèves), a fortiori ceux qui ayant passé la quarantaine ou mieux et n’en ont jamais entendu parler dans leur formation. Car ne l’oublions pas l’arrivée des graphes dans les programmes du secondaire est très récente et cantonnée au triptyque SNT/NSI/Maths expertes. La quatrième de couverture le rappelle, rares sont les situations aussi paradoxales : comprendre et utiliser les graphes est ludique et immédiat, et pourtant leur enseignement est repoussé à la fin du secondaire et souvent pour des "spécialistes".

Mais reprenons le fil du voyage. Mais en allant vers l’aéroport, on tombe dans :

Les embouteillages

Le chapitre 4, nommé simplement "Embouteillages", traite essentiellement de jeux et en particulier de jeux de poursuite. Ceux-ci se jouent avec 2 joueurs, dès le CP d’après Alain Busser. La plupart du temps, il s’agit de bloquer le ou les pions de l’adversaire pour l’empêcher de bouger lorsque c’est son tour.
Des parties sont détaillées coup par coup entre deux joueurs fictifs appelés Fey et Guy, notamment sur le graphe de Bidiakis. C’est une manière agréable et claire pour comprendre la recherche d’une stratégie gagnante. On apprend que pour bloquer le pion unique de Fey, il faut disposer d’au moins autant de pions que le degré minimal des sommets du graphe sur lequel on joue. C’est assez intuitif. Mais le fait de le savoir ne donne pas forcément la stratégie gagnante.
Ci-dessous, Fey ne peut plus bouger son pion. Sur ce graphe, le degré minimal des sommets est 3, comme le nombre de pions de Guy. Le blocage serait impossible avec 2 pions seulement car alors Fey pourrait toujours se dégager par la troisième voie de circulation.

Jeu de poursuite sur le graphe de Bidiakis (extrait du livre)

Le tour du monde des jeux de poursuite ou de déplacement

Alain Busser présente ensuite, à partir de la page 74, un grand nombre de jeux de poursuite à travers le monde, en voyageant dans le temps également depuis l’Antiquité romaine :
– les jeux romains ou nordiques avec des graphes gravés sur pierre ;
– le jeu militaire (qui daterait du Moyen-Âge en France) mais dont la popularité est due à Edouard Lucas qui le présente vers 1890 dans un des tomes de ses Récréations mathématiques ;
– le jeu de la madelinette, aussi présenté par Edouard Lucas ;
– le jeu du fer à cheval ou Temeen Tavag, jeu mongol ;
– le fanorona, jeu traditionnel malgache et son dérivé le fanorona-dimy ;
– le jeu des deux châteaux, autre jeu malgache ;
– le jeu Konane, jeu national d’Hawai’i (qui n’est pas un jeu de poursuite) et son "dérivé" le jeu de Lewthwaite (qui lui en est un) ;
– le jeu de taquin, populaire aux USA à partir de 1870 , peut-être sous l’impulsion de Sam Loyd ;
– les jeux de M. Fleury (caméléon, rose mystique, paradoxal, France et Russie, trifolium diabolique) qui rivalisent d’ingéniosité pour le graphe sur lequel ils se jouent ;
– le jeu sliding Tokens (années 2000).

Notons dans l’ouvrage d’Alain Busser de nombreuses références aux travaux publiés en 4 tomes d’Edouard Lucas de 1890 à 1896.

Edouard Lucas (source Wikipedia)

Ce dernier, connu pour ses travaux en théorie des nombres (test de primalité de Lucas-Lehmer) est donc aussi inventeur de jeux (tours de Hanoi) et passionné de jeux et de problèmes en tout genre. Ses Récréations mathématiques constituent un panorama exhaustif pour l’époque d’un grand nombre de jeux ou de défis de traversées de ponts, de labyrinthes...Si la parenté avec le livre d’Alain Busser est évidente, on pourra noter la grande différence des modes de présentation qui ont drastiquement changés en 130 ans. En consultant, la page de la BNF Gallica, on pourra y appréhender dans l’approche de Lucas une vision des graphes, disons sans graphes, où les déplacements se résument par des permutations de lettres du type ADBC, de longs textes ou des tableaux....On y retrouvera une présentation du problème des ponts de Königsberg à partir de la page 21 (deuxième récréation). Cela tranche forcément avec Jeux et graphes. La théorie des graphes de 5 à 95 ans où la présentation se veut avant tout visuelle et où les multiples figures viennent guider le lecteur pas à pas. L’approche de Lucas, comme celle de ces illustres prédécesseurs Euler, Hamilton ou Cayley est celle des automates, nous en reparlerons un peu plus loin.

Tout voyageur aime connaître la distance parcourue

Le chapitre 5, intitulé "Distances" commence avec la définition de nouveaux éléments : la distance entre deux sommets d’un graphe, l’excentricité d’un sommet, le rayon, le diamètre, le centre et le bord d’un graphe. Pour les appréhender, il est nécessaire de savoir dénombrer ce qui ferme la porte aux élèves de maternelle. Mais leur manipulation sera envisageable en cycle 3 et constitue surtout le cœur du programme de SNT en seconde.
Et l’on retrouve ainsi rapidement le fameux problème du voyageur de commerce. Est présentée également la méthode de Edger Dijkstra pour déterminer la distance minimale entre deux sommets d’un graphe pondérée par les distances ou la durée de transmission d’une information. Alain Busser la conseille dès le CE1 avec des nombres entiers à additionner ou plus tard avec des nombres décimaux. Cette approche ludique a du succès.

Un passage par Fort Boyard ?

Vous avez déjà certainement vu un candidat de Fort Boyard affronter le maître des jeux dans une partie de jeu de la soustraction : chacun à tour de rôle doit ôter 1, 2 ou 3 bâtonnets d’un ensemble de 20 ou 21 bâtonnets [8]. Celui qui prend le dernier a perdu.

Le maître des jeux prend 3 bâtonnets

Décrit à l’origine par Claude-Gaspard Bachet de Méziriac [9] au XVIIème siècle, on peut voir ce jeu comme une variante d’un jeu de Nim (de Charles Bouton vers 1900) où l’objectif pour les joueurs est d’épuiser un ou plusieurs tas de pièces. Le chapitre 6 du livre est consacré justement aux "jeux de type Nim".
Vous y découvrirez comment Aviezri Fraenkel a eu l’idée dans les années 1990 de jouer à un jeu de Nim en déplaçant directement un pion sur le graphe orienté du jeu et donc sans avoir de matériel particulier comme les pièces et les bâtonnets. Ce chapitre, quoique un peu technique, propose de façon lumineuse de trouver des stratégies gagnantes pour les jeux correspondants. Les principes de coloration de Sprague et Grundy sont ainsi explicités.
Si Alain Busser ne parle pas du jeu de Fort Boyard à proprement parler (il se contente d’un jeu à 7 bâtonnets où l’on gagne en prenant le dernier), rien n’empêche d’essayer d’en bâtir une stratégie gagnante par le graphe. Le graphe que voici est celui de Jérôme Cottanceau dans Chou romanesco, vache qui rit et intégrales curvilignes ici :.
On joue ici avec 20 bâtonnets.

Les nombres représentent alors le nombre de bâtonnets restant en jeu et ainsi par exemple, le sommet n°10 n’est relié par un arc orienté (allant dans le bon sens) qu’aux sommets n°7, n°8 et n°9 puisqu’on ne peut prendre qu’ un, deux ou trois bâtonnets à son tour de jeu. Pour gagner, il faut pouvoir se placer à la position d’arrivée, sommet n°1, puisqu’alors on force l’adversaire à prendre le dernier bâton.
La stratégie de Sprague est alors de :
– colorier en clair toutes les arrivées (le n°1) ;
– chaque fois qu’au moins un successeur d’un sommet est colorié en clair, colorier ce sommet en foncé ;
– chaque fois que tous les successeurs d’un sommet sont coloriés en foncé, colorier ce sommet en clair.
La stratégie gagnante pour le premier joueur consiste à mener à chaque fois le pion vers un sommet colorié en clair, quelque soit ce que l’adversaire a joué.
Le graphe devient ainsi "colorié" :

Ainsi colorié, le graphe fait apparaître la stratégie gagnante

Au premier tour, si le premier joueur laisse 17 bâtonnets à son adversaire, quoiqu’il arrive (id est que celui-ci prenne 1, 2 ou 3 bâtonnets), il pourra toujours s’arranger (en prenant ainsi respectivement 3, 2 ou 1 bâtonnets) pour laisser 13 bâtonnets au tour suivant. Puis 9. Puis 5. Puis 1. Il remportera donc la partie.

Sachant que je suis le prototype même de personne à qui l’on n’a jamais enseigné les graphes et qui n’a jamais eu l’occasion de les enseigner, on pourra voir l’efficacité du discours d’Alain qui m’a permis de reconstituer facilement cette stratégie gagnante par des outils que je ne connaissais pas avant l’ouverture de Jeux et graphes. La théorie des graphes de 5 à 95 ans. D’autre part, la technique est si facile à expliquer ainsi qu’elle séduira les enfants, bien sûr grands amateurs de Fort Boyard. [10]

Emprunter le réseau secondaire

Dans le chapitre 7, le lecteur pourra vraisemblablement découvrir un cas particulier de graphe orienté bipartite appelé "Réseaux de Petri". Véritable outil de modélisation, les réseaux de Petri permettent par exemple de vérifier le comportement dynamique des systèmes à événements discrets comme les systèmes manufacturiers, les systèmes de télécommunications ou encore les réseaux de transport. Des aspects que l’auteur ne détaille pas, se concentrant sur les jeux sur de tels réseaux. Il précise qu’une activité débranchée, menée en CM2 en 2021, sur des réseaux de Petri permet d’introduire et de calculer le PGCD de 2 entiers. Je n’ai pas pu consulter la référence bibliographique associée sur le site de l’IREMI, actuellement indisponible après une vague de cyberattaques.

Les réseaux de Petri sont dotés de deux types de sommets, les places où l’on place des jetons (représentés par des cercles) et les transitions (représentés par des rectangles) qui sont en quelque sorte des nœuds de correspondance où l’on ne s’attarde jamais. Lorsque des jetons sont posés sur une des places, on peut déclencher le transport de jetons par l’intermédiaire d’un ou plusieurs arcs orientés (1 jeton par arc) jusqu’à une transition qui déclenche à son tour le transport jusqu’à de nouvelles places. Mais pour déclencher les transitions, il faut disposer d’un nombre de jetons suffisant, sinon la transition n’est pas "vivante". Quand toutes les transitions sont "mortes" et que c’est à son tour de jouer, on a perdu le jeu.

Alain Busser présente alors une autre illustration du jeu de la soustraction avec 7 jetons (bâtonnets) sous la forme de réseau de Petri. Les transitions sont étiquetées 1, 2 et 3 selon le nombre de jetons qu’elles reçoivent. Voici le déroulement d’une partie.

Le premier joueur dispose de 7 jetons.
Il déclenche la transition n°3 et y dépose 3 jetons.
1 jeton est acheminé au puits, 2 sont défaussés. C’est le tour du second joueur qui dispose de 4 jetons.
Le second joueur déclenche la transition n°2 et y dépose 2 jetons.
Un deuxième jeton rejoint le puits, 1 jeton est défaussé. C’est de nouveau au premier joueur qui dispose de 2 jetons.
Il déclenche la transition n°2 et y dépose les deux derniers jetons.
Un troisième jeton est acheminé au puits et 1 jeton est défaussé. Il ne reste plus de jetons pour le second joueur et toutes les transitions sont donc mortes. Il perd ainsi la partie quand le nombre de jetons au puits est impair. Il la gagnerait sinon.

Plus fort, l’ajout d’une transition et d’une place supplémentaire à droite selon ce modèle permettrait d’obtenir le quotient et le reste (au puits) de la division euclidienne par 2.

Encore une fois le novice que je suis est sidéré par la simplicité de l’approche d’une notion qui est l’affaire d’étudiants post-bac et de spécialistes. La découverte par le jeu est à nouveau efficace même s’il ne faut pas se leurrer, les réseaux de Petri ont bien d’autres subtilités et des applications beaucoup plus sérieuses qu’un jeu de Nim à 7 jetons. Mais cette approche donne envie d’en savoir plus et permet au passage de jouer au jeu de la soustraction sur un graphe encore plus réduit et simple, le même quelque soit le nombre de jetons d’ailleurs.
Justement, le chapitre se termine par une nouvelle notion : le graphe de marquage d’un réseau de Petri. Celui-ci permet de comprendre le lien entre les "mots" formés par les étiquettes que l’on retrouve dans les ouvrages anciens (comme ceux de Euler ou de Lucas) et la théorie des graphes initiée par Cayley dans la seconde moitié du XIXème siècle. Ainsi "322" constituerait le mot synonyme de victoire pour le premier joueur dans la partie précédente du jeu de la soustraction.

Simple visite au musée des automates

Un automate est un graphe orienté particulier où :
– chaque étiquette n’est présente, au maximum, que sur un seul arc issu d’un sommet donné ;
– les sommets sont appelés les états ;
– le départ est appelé état initial ;
– les arrivées sont appelés états finaux ;
– le sommet où se trouve le pion s’appelle état courant ;
– les arcs orientés modélisent donc les changements d’état.

Le parcours du pion entre le départ et l’arrivée peut être décrit par un "mot" qui informe donc de la succession effective des états. Ainsi, jouer sur un automate nécessite une feuille de papier sur laquelle on écrit un mot. Une sorte de "cadavres exquis" des surréalistes (années 1920) mais avec des lettres au lieu de mots.
Il est ainsi clair qu’une chaîne de Markov est un automate qui change d’état au hasard. Les "machines de Turing" (1936) sont eux des automates munis de ruban pour lire et modifier les lettres du "mot".
En 1948, Claude Shannon présente un automate qui reconnaît le code Morse, ce qui signifie que toutes les possibilités de mots du code peuvent être obtenus par déplacement du pion sur l’automate...Stephen Kleene publie en 1951 un article dans lequel il montre qu’un réseau de neurones est un automate capable de reconnaître des mots. Plus de détails dans l’ouvrage bien entendu.

Le chapitre 8 regorge d’exemples d’automates et de parties à un seul joueur. Le but du jeu est alors de voir à quoi ressemblent les mots obtenus (aux propriétés parfois déroutantes). On notera avec intérêt ces automates qui reconnaissent certains mots binaires écrits par des 0 ou des 1, qui ont donné vie à une animation lors de la fête de la science 2019 qui a du succès auprès des enfants réunionnais.
On s’attardera aussi sur les automates de Mealy qui au cours de la reconnaissance de 0/1 peuvent en parallèle écrire des lettres, par exemple pour traduire dans une autre langue.
Le chapitre s’achève avec l’utilisation d’automates pour engendrer des programmes de calcul, en guise de graphe orienté étiqueté par des instructions à mener en séquence. On en trouve des exemples dans des manuels allant du CP à la terminale en section technologique.

J’aimerais tant voir Syracuse...

Dans les années 1930, Lothar Collatz s’intéressait aux itérations dans les nombres entiers, qu’il représentait au moyen de graphes et d’hypergraphes. Parmi ces problèmes qu’il a présentés lors de conférences, il y en a un qui est resté célèbre, celui présenté à l’université de Syracuse par son collègue Helmut Hasse.
Une suite de Syracuse est une suite d’entiers naturels définie de la manière suivante : on part d’un nombre entier strictement positif ; s’il est pair, on le divise par 2 ; s’il est impair, on le multiplie par 3 et l’on ajoute 1. En répétant l’opération, on obtient une suite d’entiers strictement positifs dont chacun ne dépend que de son prédécesseur.
Par exemple, à partir de 14, on construit la suite des nombres : 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1 et ainsi de suite. C’est la suite de Syracuse du nombre 14. Après que le nombre 1 a été atteint, la suite des valeurs 1, 4, 2, 1, 4, 2… se répète indéfiniment en un cycle de longueur 3, appelé cycle trivial.

La célèbre conjecture de Syracuse affirme qu’en partant de n’importe quel entier positif, on finit toujours par aboutir à ce cycle trivial.

Elle résiste encore aux mathématiciens qui s’y intéressent.

S’il ne s’agit pas à proprement parler d’un programme de calcul, à cause du test de parité à chaque étape qui impose de prendre une décision contrainte, il est facile de représenter le programme sous forme de graphe. Les sommets d’un tel graphe agrémenté d’un test "if" sont représentés sous forme de losange depuis Turing. Avec celui-ci les programmes prennent la forme d’algorithmes qui prennent la forme de graphes ou organigrammes ou algorigrammes. Ainsi on peut voir l’informatique théorique comme une des applications de la théorie des graphes.

Mais il ne s’agit pas non plus d’un jeu puisque les décisions ne sont pas prises par les joueurs mais imposées par le caractère pair ou impair du dernier résultat. Adieu Syracuse, l’île de Pâques et Kairouan !
C’est sans compter sur John Isbell qui transforme le programme en un jeu nommé beanstalk : lorsqu’on trouve un nombre impair, le joueur suivant a le droit de choisir entre deux options :
– calculer son triple puis ajouter 1 ;
– calculer son triple puis soustraire 1.
Le perdant est celui-ci qui arrive à 1.
Cela modifie considérablement les suites de Syracuse comme l’explique Alain Busser page 175. Mais avec le nombre 5 comme nombre de départ par exemple, l’un des deux joueurs n’a en fait jamais eu de choix tactique, ayant à chaque fois un nombre pair au moment de jouer son tour :
5 - 14 - 7 - 22 - 11 - 32 -16 - 8 - 4 - 2 - 1.

John Conway, l’auteur du fameux jeu de la vie qui n’est autre qu’un automate cellulaire, propose alors une variante nommée beans don’t talk qui améliore cet aspect. Chaque fois qu’un joueur a ajouté ou soustrait 1 au triple du nombre précédent, il divise le résultat par 2 aussi souvent que possible pour aboutir à un nombre impair. Le joueur suivant pourra ainsi prendre la décision d’ajouter ou de soustraire 1 à sa guise après avoir triplé. Autrement dit, les étapes de division par 2 ne sont plus à faire systématiquement par le joueur adverse.
La partie commençant par 5 devient :
5 - 14 puis 7 - 22 puis 11 - 34 puis 17 - 52 puis 26 puis 13 - 40 puis 20 puis 10 puis 5 -16 puis 8 puis 4 puis 2 puis 1.
Le joueur rouge a fait une erreur stratégique avec 5 en en calculant 5 $\times$ 3 + 1 = 16 car 16 est une puissance de 2.
Il aurait dû faire 5 $\times$ 3 - 1 = 14, ce qui aurait pu faire une partie qui "boucle" au départ et aurait certainement provoqué un match nul.

Voilà ainsi deux petits jeux à jouer aux environs du cycle 3-4 et qui sont plutôt amusants pour les novices. Novices dont Alain Busser ne fait plus partie puisqu’à la page 176, il donne un graphe qui montre clairement un cycle entre les nombres 5 et 7 pour jouer le nul et le danger des nombres 3, 5 et 11 qui peuvent engendrer clairement la défaite en cas de mauvais choix. En effet :
3 $\times$ 3 - 1 = 8 = $2^{3}$
5 $\times$ 3 + 1 = 16 = $2^{4}$
11 $\times$ 3 - 1 = 32 = $2^{5}$
Saurez-vous étendre son graphe et trouver d’autres nombres entiers synonymes de situation dangereuse ?

Quand le réseau de transport est interrompu

Tous les ans au mois de février, chez moi à Nice, le réseau de tramway subit des interruptions partielles et temporaires en raison du fameux carnaval qui prend ses quartiers autour de la place Massena. La circulation de la ligne 1 est alors interrompue entre les stations Jean Médecin et Garibaldi. Les locaux en ont désormais l’habitude.
Si l’on souhaite aller d’Henri Sappia à l’hôpital Pasteur par la ligne 1 aux heures d’un spectacle, il faut donc descendre à Jean Médecin pour emprunter la ligne 2 en correspondance jusqu’à Garibaldi ou on peut récupérer la ligne 1 pour finir le trajet.

Plan simplifié du réseau de tramway niçois

Si l’on considère le plan du réseau niçois comme un graphe, tout se passe comme si on avait effacé les sommets Massena, Opéra et Cathédrale. Toutes les arêtes rouges entre Jean Médecin et Garibaldi disparaissent alors aussi. Ainsi à Jean Médecin, il n’y a plus de choix : l’usager est obligé d’emprunter l’arête bleue qui mène à Durandy et de continuer toujours sur l’arête bleue jusqu’à Garibaldi. On récupère alors le chemin tracé en rouge puisqu’à cette station, le réseau vers le nord n’est pas impacté par l’interruption de service.

Le chapitre 9 "Destruction de graphes" est consacré à ce genre de modifications. Munis d’une gomme, les joueurs peuvent effacer des arêtes et des sommets.
Dans un premier temps, Alain Busser montre avec pédagogie (parties à l’appui) comment le fait d’effacer des sommets et des arêtes permet de simplifier les jeux de coloriage comme celui de Snort ou de Col. En enlevant les sommets qui n’interviendront plus dans le jeu (car coloriables par personne), on peut alors retravailler l’allure du graphe et ainsi trouver des stratégies gagnantes.
C’est sur cette base que John Conway ou Richard Guy (nul ne sait lequel exactement) a créé le jeu Green Hackenbush ou que David Gale a créé le jeu Bridg-it où l’on fabrique cependant des arêtes, mais qui est équivalent à un jeu de Claude Shannon où l’on efface bien des arêtes. C’est l’occasion de découvrir la notion d’arbre couvrant d’un graphe et pourquoi pas d’en chercher sur des graphes biscornus.
Je conseille ce chapitre qui, comme diraient les adeptes de jeu de société, renouvelle l’expérience de jeu, un peu comme le font les extensions des jeux à la mode. Ici, les nouveaux jeux sont encore une fois adaptés à la toute jeune génération grâce à quelques astuces à mettre en œuvre dans les classes.

Créer son propre univers

Justement, à force de jouer, les fans de société rêvent tous de créer leur propre jeu. Le chapitre 10, "construction de graphes" montre que c’est certainement un objectif abordable s’il s’agit d’un jeu basé sur des graphes comme le jeu japonais Hashiwokakero qui consiste à relier les îles (sommets) d’un archipel par des ponts (arêtes), sachant que le nombre de ponts (le degré) de chaque île est fixé à l’avance.
Cela revient donc à construire un graphe correspondant à ce que l’on appelle une suite graphique qui donne la liste des degrés des sommets. Un peu comme s’il s’agissait de bâtir un plan de voyage passant par tous les lieux cités dans la chanson Syracuse d’Henri Salvador en respectant un nombre imposé de liaisons au départ de chaque lieu en quelque sorte.
Par exemple, sauriez-vous trouver un graphe non orienté avec ces sommets et leurs degrés respectifs :

Solutions : page 203.

Le chapitre se poursuit par la présentation d’un autre jeu dû à Edouard Lucas. Dans un développement assez technique, Alain Busser présente la stratégie gagnante qui annihile l’intérêt du jeu si l’on admet que les joueurs jouent "correctement". Mais ce jeu possède une version améliorée, proposée par John Conway et Michael Paterson en 1967 : le jeu de Sprouts.
Ce jeu est adapté à l’école élémentaire : il s’agit de relier des villes par des routes (maximum 3 routes menant à une ville), sans que les routes ne se croisent (graphe planaire), sachant que pour chaque route construite, une nouvelle ville naît au milieu. Ce jeu permet de travailler des compétences géométriques autour des notions de milieu, de centre...Le perdant est bien sûr celui qui ne peut plus relier de villes parce que les routes ainsi construites croiseraient celles déjà existantes.
Alain Busser qui a déjà observé des collégiens jouer avec plus de 10 villes au départ note que la durée de jeu est finie et n’excède pas en nombre de coups le triple du nombre initial de villes. Ce résultat est dû à John Conway. Une démonstration en est donnée à partir de la page 213. Alain en conseille la lecture car la preuve est autant lumineuse qu’instructive.

Il est temps de rentrer à la Réunion

Ce grand tour d’horizon sur les graphes s’achève par le chapitre 12 qui est sobrement intitulé "fonctions". Les liens entre programmes de calcul et fonctions n’étant plus à démontrer, on s’attendait en effet à voir des graphes représenter des fonctions.
Pour cette dernière étape, Alain Busser a choisi de traiter un sujet bassement terre-à-terre, le sujet de DNB de septembre 2019 à la Réunion. Il montre ainsi comment les graphes peuvent aider à résoudre des problèmes de collège.

Extrait du sujet de DNB

On peut se demander comment montrer cette conjecture. La représentation suivante peut indiscutablement en simplifier l’accès :

Les souvenirs de voyage

Voilà, je suis (nous sommes) de retour dans mon (notre) quotidien après 230 pages dans un pays singulier, le pays des jeux et des graphes. Alain Busser m’ (nous) y a guidé par l’intermédiaire de nombreux dessins et de textes qui détaillent les étapes des jeux qu’il présente ou des notions mathématiques qu’il explicite. Le voyage fut donc organisé de mains de maître, par un spécialiste qui n’oublie pas que les lecteurs ont certainement des points communs :
– leur formation première a pu éviter les graphes ;
– les adultes sont de grands enfants.
C’est ainsi qu’il réussit le tour de force de réunir les gens de 5 à 95 ans autour d’un projet basé sur l’envie de s’amuser, de manipuler, de créer, de dessiner et de verbaliser. Et ainsi d’aborder des choses diablement complexes avec la plus grande des simplicités et des motivations.
Voilà mon plus beau souvenir de ce voyage !