D. Graphes : théorie, représentation et algorithmes

• Cours :
  • Théorie des graphes
  • Propriétés des graphes
  • Algorithmes des graphes
• Vidéos explicatives :
  • Vocabulaire des graphes
  • Représentation informatique des graphes
  • Parcours en largeur : principe et application
  • Parcours en largeur : implémentation en Python et structures de données
  • Algorithme de Dijkstra à la main
• Activités exploratoires :
  • Coloration de graphe, approche gloutonne
  • Coloration de graphe, approche gloutonne - solutions
  • Algorithme de Dijkstra, plus courts chemins dans un graphe
  • Algorithme de Dijkstra, plus courts chemins dans un graphe - Solutions
  • Algorithme A* : une heuristique pour guider la recherche
  • Algorithme A* : une heuristique pour guider la recherche - Solutions
  • Cycles eulériens
• TP :
  • Représentation des graphes : listes et matrices d'adjacences solution (à ne pas ouvrir en TP mais chez soi !)
  • Parcours de graphes et applications solution (à ne pas ouvrir en TP mais chez soi !)
  • Graphes : coloration et plus courts chemins solution (à ne pas ouvrir en TP mais chez soi !)
• Liens utiles :
  • Visualiser les différents algorithmes de parcours et de recherche dans un graphe
• Objectifs d'apprentissage :
  • représenter un graphe en machine par une liste d'adjacence ou une matrice d'adjacence
  • transformer une représentation en une autre
  • calculer les degrés des sommets d'un graphe
  • transposer un graphe
  • caractériser un graphe d'après sa séquence de degrés ou son spectre
  • trouver le plus court chemin dans un graphe
  • colorer un graphe d'une manière valide
  • détecter les cycles dans un graphe
  • connaître les complexités associées aux algorithmes des graphes (parcours en largeur, Dijkstra)
  • Savoir appliquer à la main l'algorithme de Dijsktra sur un graphe simple (compléter le tableau)
  • Connaître les conditions d'application de l'algoritme de Dijsktra
  • Connaître le lien entre le parcours en largeur et une file d'attente (FIFO)