Méthode Ford-Fulkerson : Structures de données disjointes

Cette séance de cours couvre la méthode Ford-Fulkerson pour trouver le flux maximal dans un réseau, en commençant par un flux initial et en l'augmentant itérativement le long de chemins croissants jusqu'à ce qu'aucun autre chemin ne puisse être trouvé. La séance de cours explique également comment déterminer le temps de fonctionnement de la méthode et pourquoi elle fonctionne en la reliant à des problèmes d'appariement. En outre, la séance de cours introduit des structures de données disjointes, également connues sous le nom de union-find, qui maintiennent des ensembles dynamiques avec des éléments représentatifs. Des opérations telles que MAKE-SET et UNION sont discutées, ainsi que la représentation en liste des ensembles et l'opération syndicale. Diverses stratégies pour les opérations syndicales sont explorées, comme l'ajout d'une liste d'un ensemble à l'autre. La séance de cours se termine par des exemples pratiques et des applications de ces concepts.