Graphes
Programme complet de R2.07 : vocabulaire, plus courts chemins (Dijkstra), Bellman et ordonnancement, flots (Ford-Fulkerson), graphe de configurations — avec l'outil Grapp.
Modéliser un problème sous forme de graphe, puis le résoudre : plus courts chemins,
ordonnancement, flots, recherche par configuration. L'outil du cours est Grapp, un
serveur en ligne de commande (load, list, draw, maximum-flow), et les TP de
modélisation s'écrivent en Java avec AbstractImplicitGraph.
Cours5 chapitres
Ch. 1 — Vocabulaire et arbresSommets, arêtes, chemins, cycles, connexité, arbres, matrice d'adjacenceCh. 2 — Plus courts cheminsGraphe valué, distance, algorithme de Dijkstra (distances et prédécesseurs)Ch. 3 — Bellman et ordonnancementDAG, ordre topologique, plus long chemin, potentiel-tâches, chemin critiqueCh. 4 — FlotsRéseau de transport, capacité, flot, coupe minimale, Ford-FulkersonCh. 5 — Configurations et affectationGraphe implicite, parcours en profondeur, affectation par flot biparti
TDTD et TP (5 semaines)
Évaluation : un DS (notes de cours seules autorisées), 3 tests Moodle en TP et le livrable de la SAé 2.02.
Dernière mise à jour le