Dans cet atelier, nous allons traiter d’un problème classique en mathématique : est-ce que l’on peut parcourir un graphe en passant par chaque sommet (au moins une fois) et chaque arête. Si c’est le cas, vous avez trouvé un chemin ou cycle dit eulérien. Au lieu de travailler au tableau noir ou sur une feuille de papier, vous dirigerez un petit personnage dans un jeu vidéo appelé Matheminecraft.
Trouver un chemin eulérien revient à parcourir le graphe sans lever le crayon. C’est le cas, par exemple, d’un carré ou d’un triangle. Mais plus le graphe est compliqué, plus la recherche d’un chemin eulérien se complique.
Dans le jeu Matheminecraft, développé par des mathématiciens de l’EPFL à l’intérieur du célèbre jeu Minecraft, chaque niveau est un graphe dont vous devrez trouver un chemin eulérien.
Muni d’une carte représentant le graphe, vous allez devoir trouver un chemin passant par chaque sommet et chaque arête. Une fois une arête traversée, vous ne pourrez pas faire demi-tour car les arêtes parcourues se transforment en rivières de lave…
À vos claviers et souris! Saurez-vous trouver un cycle eulérien sans tomber dans la lave et accéder aux niveaux supérieurs de notre jeu, Matheminecraft?
Par la section et l’institut de mathématiques – Orane Jecker, David Strütt