C. Graphes avancés

• Cours :
  • Graphes avancés
• Vidéos explicatives :
  • Quadrillages : graphes et tableaux
• Activités exploratoires :
  • Algorithme de Prim
  • Structure Union-Find : application à l'algorithme de Kruskal (arbre recouvrant)
  • Structure Unir-Trouver : algorithme de Hoshen-Kopelman (percolation)
• TP :
  • Parcours et plus courts chemins solution (à ne pas ouvrir en TP mais chez soi !)
  • Algorithmes de Prim et de Kruskal solution (à ne pas ouvrir en TP mais chez soi !)
  • Graphes orientés et applications solution (à ne pas ouvrir en TP mais chez soi !)
  • Graphes bipartis et couplage solution (à ne pas ouvrir en TP mais chez soi !)
• Fichiers :
  • Algorithme de Prim avec file de priorités
  • Algorithme de Kruskal
• Objectifs d'apprentissage :
  • expliquer le concept d'arbre recouvrant
  • connaître les algorithmes de Prim et Kruskal
  • connaître la notion de tri topologique et son lien avec le parcours en profondeur
  • expliquer le concept de forte connexité
  • expliquer l'intérêt d'un graphe biparti