ECTS : 4
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
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