Retour au reportage Retour au reportage
20210159_0094

© Christian MOREL / IRIF / CNRS Images

Référence

20210159_0094

Diagramme de Hasse du treillis des matchings stables

Diagramme de Hasse du treillis des matchings stables. Il représente la structure de l’ensemble des matchings stables. Un exemple d’instance pour ce type de problème est le suivant : 8 étudiants (numérotés de 1 à 8) doivent être affectés dans 8 écoles (numérotées de A à G) en tenant compte de leurs préférences. Une paire formée d'un étudiant et d'une école est bloquante s'ils se préfère mutuellement à leurs affectations respectives. Un matching est stable s'il n'existe aucune paire bloquante. L'ensemble des matching stables a une structure de treillis complet. Il est conjecturé que le nombre maximal de matchings stable est atteint par une famille d'instances généralisant l'exemple donné.

Délégation(s)

Thématiques scientifiques

CNRS Images,

Nous mettons en images les recherches scientifiques pour contribuer à une meilleure compréhension du monde, éveiller la curiosité et susciter l'émerveillement de tous.