Couplages d'un graphe biparti
Problèmes d'affectations

Supposez que dans une assemblée de k hommes et n femmes on désire des couples en tenant compte des préférences de tous.
Dans un premier temps vous dessinez deux colonnes avec les noms des hommes dans l'une, ceux des femmes dans l'autre.
Vous reliez les noms de l'une des colonnes à ceux de l'autre lorsque le trait correspond aux préférences des deux personnes.
Vous obtenez alors un graphe biparti G(X, Y, E) où E est l'ensemble des hommes et Y celui des femmes (à moins que ce ne soit l'inverse) et où E est l'ensemble des arêtes reliant X et Y.

On supposera que le nombre k=|X| d'éléments de X est inférieur ou égal au nombre n=|Y] d'éléments de Y.

Trouver un couplage de X dans Y consiste à trouver un sous-ensemble de k arêtes deux à deux non adjacentes (sans extrémités communes). Tous les sommets de X sont extrémités d'une arête unique, les sommets de Y sont extrémités d'une arête au plus. (Le couplage obtenu est alors maximal).

Un ensemble X de k ouvriers et un ensemble Y de n machines (k inférieur ou égal à n).
Chaque ouvrier est qualifié pour travailler sur certaines machines seulement.
Problème : Comment placer les ouvriers face aux machines qui leu conviennent.

Variantes : Vous placez k convives autour d'une table en les plaçant uniquement aux endroits qu'ils souhaitent. Ou k élèves dans une classe de n places...

L'application ci-dessous détermine toutes les solutions, lorsqu'elles existent. Pour utiliser l'application, inspirez-vous des exemples.

Une ligne est consacrée à chaque ouvrier.
Pour chaque ouvrier, écrivez uniquement les numéros (en partant de 0) des machines qui conviennent et en terminant cette liste par un point virgule avant de passer à l'ouvrier suivant.

Autrement dit, dans le cadre ci-dessous, chaque ligne de l'exemple est l'ensemble des successeurs d'un seul et même élément de l'ensemble X. Elle se termine par un point-virgule.
Un nombre y sur la ligne numéro x correspond donc à une arête (x, y) reliant l'élément x de X à l'élément y de Y.

Lorsque des solutions existent, elles sont présentées sur des lignes différentes de k nombres a₀ a₁ a₂ ... a_n-1 et les arcs retenus pour le couplage sont les arcs (i, a_i).



Cliquez sur l'image pour cet exemple :
Une solution est notée 8 4 9 1 7 6 0 5 2 lorsque ces valeurs sont les extrémités des arcs d'origines respectives 0 1 2 3 4 5 6 7 8.
Les arcs sont donc (0, 8) (1, 4) (2, 9) (3, 1) (4, 7) (5, 6) (6, 0) (7, 5) (8, 2) ou encore x0->y8, x1->y4, x2->y9, x3->y1, x4->y7, x5->y6, x6->y0, x7->y5, x8->y2 si vous préférez cette notation.
Cette solution est la première des 148 trouvées par l'application.

Couplages

      # k = 8 n = 11 (ligne de commentaire) 2 3 6 ; 2 6 ; 2 6 7 8 9 10 ; 1 2 3 4 9 ; 3 5 6 9 ; 0 2 3 5 8 ; 6 7 9 10 ; 8 10 ; ------------ tout ce qui suit est un commentaire et est ignoré

L'application précédente permet de trouver, s'ils existent, tous les couplages (maximaux) de X dans Y.
Il existe aussi des algorithmes permettant de trouver un couplage maximal (et un seul à la fois).