Généralités sur les graphes. Représentation des graphes. Notions de base : degré, chemins, cycles, planarité, connexité, fermeture transitive.Arbres recouvrants minimaux, algorithmes de Kruskal et Prim. Problème de plus courts chemins.algorithmes de Djikstra et de Bellman-Ford.algorithme de Floyd-Warshall.Parcours en largeur et en profondeur des graphes. Applications (plus courts chemins, ordre topologique, composantes fortement connexes, calcul de noyau).Implémentation des algorithmes en Python.
Pour la mise en pratique de ces algorithmes on privilégiera l’étude de situations issues des SHS.
