Débit maximal : théorie et applications

Cette séance de cours couvre le concept de débit maximal dans les graphiques, en discutant de l'algorithme Ford-Fulkerson, de la conservation du débit, des contraintes de capacité et de la notion de coupe minimale. L'instructeur explique comment déterminer le débit maximal dans un réseau en construisant une partition de sommets accessibles à partir de la source. À travers des exemples et des démonstrations, la séance de cours illustre comment identifier la coupure minimale qui correspond au débit maximal, en soulignant l’importance de la conservation du débit et des limitations de capacité. L'instructeur présente également le concept de graphes résiduels et montre comment les utiliser pour trouver le flux maximal dans un réseau. La séance de cours se termine par des exercices permettant aux étudiants de pratiquer l'application des concepts théoriques discutés.