Méthode Ford-Fulkerson: Max Flow et Min Cut

Cette séance de cours couvre la méthode Ford-Fulkerson pour trouver le débit maximal dans un réseau, où le débit est égal à la coupe minimale. Il explique la définition d'un flux, la valeur d'un flux, le réseau résiduel, et fournit des exemples. La séance de cours introduit également le concept de flux net à travers une coupe, la capacité d'une coupe, et la relation entre max-flow et min-cut. L'algorithme de Ford-Fulkerson est détaillé, ainsi que le théorème indiquant que le flux maximum est égal à la capacité d'un min-cut. La séance de cours se termine par une preuve du théorème de min-cut max-flow.