L'objectif de cette unité d'enseignement est d'étudier les graphes tant du point de vue de leurs possibilités de modélisation de problèmes réels, en tant que structure de données avec les algorithmes associés et aussi pour leurs caractéristiques mathématiques propres.
-
Algorithmes de plus court chemins (algorithmes de Dijkstra et Floyd-Warshall)
-
Parcours de graphes : propriétés et applications (tri topologique, composantes fortement connexes)
-
Flots dans un graphe, coupe minimum
-
Énumération et algorithmes par rebroussement
-
Programmation récursive
-
Algorithmes d'approximation
-
Algorithmes randomisés
-
Géométrie algorithmique
-
Circuits Hamiltoniens, cycle Eulérien, graphes bipartis
-
Couplages
-
Coloration de graphes