Algorithmes dans les graphes
Ects : 4
Enseignant responsable :
Volume horaire : 36Description 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
- Plus court chemin (algorithmes de Bellman, de Dijkstra, de Ford et de Floyd), ordonnancement (Méthodes potentiel-tâches).
- Structures d ’ arbres, arbre couvrant de poids minimum (algorithmes de Prim et de Kruskal)
- Flot maximum (algorithme de Ford-Fulkerson).
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.