Algorithmes dans les graphes

Ects : 4
Volume horaire : 36

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