Retour au reportage Retour au reportage
20210159_0094

© Christian MOREL / IRIF / CNRS Images

Reference

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

CNRS Institute(s)

Regional office(s)

Scientific topics

CNRS Images,

Our work is guided by the way scientists question the world around them and we translate their research into images to help people to understand the world better and to awaken their curiosity and wonderment.