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 ?

Implémentations