Accueil / Combinatoire / Combinatoire / Couplages d'un graphe biparti

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

Description

Former des couples

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ù X 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).

Chacun à son poste

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...

Application

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

Entrée des données

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.

Lecture des solutions

Lorsque des solutions existent, elles sont présentées sur des lignes différentes de k nombres a0 a1 a2 ... an-1 et les arcs retenus pour le couplage sont les arcs (i, ai).



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
     


affect.tar.gz    Distribution de l'application écrite en C et de plusieurs fichiers d'essais.
Ou le programme C  uniquement. Bien plus rapide que le javascript.

Combinatoire   

Graphes   

Compléments

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).



Accueil / Combinatoire / Combinatoire / Couplages d'un graphe biparti

















Pour un premier contact, [utilisez ce formulaire] ou utilisez l'adresse de messagerie qui y figure. Merci d'indiquer la page précise du site "http//jm.davalan.org/...", cela m'aidera beaucoup. Ne joignez aucun document à votre message.
Jeux-et-Mathématiques n'est pas un site commercial. Aucun des liens placés sur ce site n'est rémunéré, ni non plus aucune des informations données.
Important : Si votre question a un quelconque rapport avec un travail personnel (Devoir TIPE Master...) , vous devez absolument me le préciser dès votre premier message et m'indiquer très précisément les limites des informations demandées. Vous devez aussi avertir la personne qui dirige éventuellement votre travail ou le corrige de cette communication et lui montrer les documents fournis.

J'essaie de répondre aux questions posées, mais ne lis pas les documents mathématiques amateurs, pas plus que je ne donne mon avis sur les démonstrations des conjectures de Collatz ou autres. Je ne lis pas les documents word, je ne corrige pas les programmes informatiques et depuis des années je n'utilise plus de tableur.

© (Copyright) Jean-Paul Davalan 2002-2014