Couplages
Le problème de couplage théorique avec de grandes portées pratiques
Problème
Algorithme optimaux
Le problème a l'air ardu mais il n'est pas NP-complet comme on pourrait s'y attendre, il est même facile à résoudre algorithmiquement. On peut noter que l'article présentant l'algorithme de résolution de ce problèmes nommé "paths trees and flowers" (Edmonds, 1965) est à l'origine même de la notion de problème polynomial (même si on trouve des références plus anciennes).
Bref. C'est un joli problème avec de jolis algorithme et utile en pratique ce qui ne gâche rien.
Chemins augmentant
Le principal outil utilisé pour résoudre le problème est le chemin augmentant. C'est le pendant graphe des chaines augmentantes des flots.
Graphes bi-parti
Cas général
Couplage de poids maximal
Couplage max pour des graphes bi-parti
Couplage max cas général
Variante
TBD couplage par listes : proofs from the book problem de Dinitz (en faire un dm/exos) TD est-ce que ça exite dans le cas général ?