Pour ceux qui l'ignorent, rappelons que Pac-Man est un petit personnage jaune qui déambule dans un labyrinthe en espérant fuir de vindicatifs et voraces fantômes. En réalité, il y a également une histoire de pilule qui rend invincible mais nous oublierons ce détail pour respecter les lois antidrogue.
Pour un mathématicien, le jeu se présente un brin différemment : on se donne le labyrinthe sous forme d'un graphe connexe fini. Un graphe est un ensemble de positions, appelées sommets, reliées par des arêtes que l'on parcourt toujours dans le même intervalle de temps, indépendamment de la longueur sur le dessin (connexe veut simplement dire qu'il est d'un seul tenant).

Lire l'article de Roger Mansuy sur larecherche.fr