Rencontre #26: Chemins dans des graphes

Nous nous intéressons cette semaine à des problèmes qui consistent à calculer des chemins à travers des graphes respectant certaines propriétés.

Problèmes

Les problèmes suivants sont triés par ordre croissant de difficulté.

  1. “Build Dependencies” — Un ensemble de règles similaires à un Makefile décrit des dépendances de compilation entre des fichiers. Étant donné le nom d’un fichier ayant été modifié, lesquels autres devraient être recompilés?
  2. “Gregory the Grasshopper” — Identifiez le chemin le plus court à travers une grille n’utilisant que des déplacements de cavalier.
  3. “Collecting Beepers” — Calculez le meilleur chemin passant par une succession d’emplacements et revenant au point de départ.
  4. “Eulerian Path” — Trouvez un chemin passant exactement une fois par chaque arête d’un graphe, s’il en existe un.
  5. “Catenyms” — Deux mots sont des caténymes si le premier termine par la même lettre que la première lettre du second. À partir d’une liste de mots, donnez une chaîne de caténymes qui les visite tous exactement une fois.