Algorithmes dans les graphes

Ects : 5
Compétence à acquérir :
Fournir les concepts de base concernant les graphes. Souligner l’apport des graphes en informatique en tant qu’outil de modélisation. Présenter certains algorithmes fondamentaux

Description du contenu de l'enseignement :
Introduction à la théorie des graphes.
Étude et résolution des problèmes suivants :
Connexité dans un graphe, connexité forte (algorithme de Kosaraju-Sharir).
Plus court chemin (algorithmes de Bellman, de Dijkstra, de Ford et de Floyd), ordonnancement (Méthodes PERT, CPM).
Structures d’arbres, arbre couvrant de poids minimum (algorithmes de Prim et de Kruskal)
Flot maximum (algorithme de Ford et Fulkerson).