Algorithmique des graphes

Notions	Commentaires
Notion de parcours (sans contrainte). Notion de parcours en largeur, en profondeur. Notion d’arborescence d’un parcours.	On peut évoquer la recherche de cycle, la bicolorabilité d’un graphe, la recherche de plus courts chemins dans un graphe à distance unitaire.
Accessibilité. Tri topologique d’un graphe orienté acyclique à partir de parcours en profondeur. Recherche des composantes connexes d’un graphe non orienté.	On fait le lien entre accessibilité dans un graphe orienté acyclique et ordre.
Recherche des composantes fortement connexes d’un graphe orienté par l’algorithme de Kosaraju.	On fait le lien entre composantes fortement connexes et le problème 2-SAT.
Notion de plus courts chemins dans un graphe pondéré. Algorithme de Dijkstra. Algorithme de Floyd-Warshall.	On présente l’algorithme de Dijkstra avec une file de priorité en lien avec la représentation de graphes par listes d’adjacences. On présente l’algorithme de Floyd-Warshall en lien avec la représentation de graphes par matrice d’adjacence.
Recherche d’un arbre couvrant de poids minimum par l’algorithme de Kruskal.	On peut mentionner l’adaptation au problème du chemin le plus large dans un graphe non-orienté.
Recherche d’un couplage de cardinal maximum dans un graphe biparti par des chemins augmentants.	On se limite à une approche élémentaire; l’algorithme de Hopcroft-Karp n’est pas au programme. Les graphes bipartis et couplages sont introduits comme outils naturels de modélisation; ils peuvent également constituer une introduction aux problèmes de flots.

Une attention particulière est portée sur le choix judicieux du mode de représentation d’un graphe en fonction de l’application et du problème considéré. On étudie en conséquence l’impact de la représentation sur la conception d’un algorithme et sur sa complexité (en temps et en espace). On se concentre sur l’approfondissement des algorithmes cités dans le programme et le ré-emploi de leurs idées afin de résoudre des problèmes similaires. La connaissance d’une bibliothèque d’algorithmes fonctionnant sur des principes différents mais résolvant un même problème n’est pas un objectif du programme.