Max-flow et ensembles disjoints

Cette séance de cours couvre la méthode Ford-Fulkerson pour trouver le débit maximal dans un réseau, y compris l'augmentation des chemins et le calcul des goulots d'étranglement. Il explique également le concept de min-cut et sa relation avec max-flow. La séance de cours se penche ensuite sur les applications de max-flow, telles que l'appariement bipartite et les chemins disjoints. En outre, il introduit la structure de données disjointe, détaillant des opérations comme MAKE-SET et UNION, et leur application dans les composants connectés. La séance de cours se termine par l'heuristique syndicale pondérée pour les opérations syndicales en ensembles disjoints, fournissant une analyse théorique de sa complexité temporelle.