Histoire et cultureThéorème · Glossaire
lemme des mariages
Le lemme des mariages, ou théorème de Hall, caractérise la possibilité d'attribuer à chaque élément d'un ensemble fini un choix distinct pris dans sa liste, les choix appartenant eux aussi à un ensemble fini. Une telle attribution existe si et seulement si, pour tout sous-ensemble d'éléments, la réunion de leurs listes contient au moins autant de choix qu'il y a d'éléments : le critère repère donc exactement les groupes qui manquent collectivement de possibilités.
Sommaire
Ce que vous allez apprendre
- Interpréter la condition de Hall à partir de listes de choix.
- Vérifier la condition sur un exemple fini et construire une attribution injective.
- Traduire les listes en graphe biparti et en couplage couvrant un côté.
- Distinguer injection, bijection, couplage saturant un côté et couplage parfait.
En clair
Quatre personnes doivent chacune recevoir un choix différent parmi ceux qu'elles acceptent. Le problème ne vient pas du nombre total de choix, mais des choix partagés par certains groupes. Si trois personnes ne disposent ensemble que de deux possibilités, l'une restera forcément sans attribution.
Le théorème de Hall affirme que cette obstruction est la seule. Dès que chaque groupe de personnes possède collectivement au moins autant de possibilités distinctes que de membres, une attribution sans doublon existe.
Définition
Le lemme des mariages, aussi appelé théorème de Hall, caractérise l'existence d'un choix distinct pour chaque membre d'un ensemble fini. Soient F l'ensemble des personnes à servir et G l'ensemble des choix possibles. À chaque élément f de F, l'application c associe le sous-ensemble c(f) des éléments de G qu'il accepte. Pour une partie X de F, le voisinage c(X) est la réunion de toutes les listes c(f) lorsque f parcourt X.
La condition de Hall exige que tout sous-ensemble X de F possède au moins autant de voisins distincts que d'éléments : . Cette condition est nécessaire et suffisante pour qu'il existe une application injective m de F vers G telle que m(f) appartienne à c(f) pour chaque f. L'injectivité impose que deux éléments de F ne reçoivent jamais le même choix.
Dans un graphe biparti fini, F et G forment les deux côtés, et une arête relie f à chacun de ses choix acceptables. Le résultat garantit alors un couplage qui couvre tous les sommets de F. Si ce couplage couvre aussi tous les sommets de G, il est parfait au sens usuel ; cela suppose notamment que les deux côtés aient le même nombre de sommets.
Le principe
Soient F et G deux ensembles finis. À chaque élément f de F est associée une liste c(f) d'éléments de G. Si, pour toute partie X de F, la réunion c(X) contient au moins |X| éléments distincts, alors il existe une injection m de F vers G telle que m(f) appartienne à c(f) pour tout f. Réciproquement, l'existence d'une telle injection entraîne cette condition pour chaque partie X.
Quand l'utiliser
Le théorème s'applique à deux ensembles finis et à des listes d'acceptabilité connues. Il faut tester tous les sous-ensembles du côté F que l'on souhaite couvrir, y compris F lui-même. Pour chacun, on compte les choix distincts présents dans la réunion des listes, et non la somme des longueurs de ces listes : un même choix partagé ne compte qu'une fois.
Si trois éléments A, B et C n'acceptent ensemble que les choix 1 et 2, leur voisinage a deux éléments pour un groupe de taille trois. La condition échoue et aucune attribution injective ne peut couvrir A, B et C. Il faut alors modifier les listes, ajouter un choix disponible ou accepter qu'un élément de F ne soit pas servi.
Un exemple, pas à pas
Quatre personnes A, B, C et D doivent recevoir des choix distincts parmi 1, 2, 3 et 4. Leurs listes sont A : {1, 2}, B : {1, 3}, C : {2, 3} et D : {3, 4}. Le graphe associé rend visibles toutes ces possibilités et met en rouge une attribution admissible.
1. Chaque liste contient deux choix, donc la condition est satisfaite pour les groupes d'une personne.
2. Les six groupes de deux ont trois ou quatre choix distincts à eux tous. Les quatre groupes de trois en ont trois ou quatre. Enfin, le groupe {A, B, C, D} réunit les quatre choix. La condition de Hall est donc vérifiée pour tous les groupes.
3. Une attribution possible est A→2, B→1, C→3 et D→4. Chaque choix appartient bien à la liste de la personne qui le reçoit.
4. Le contrôle final retrouve quatre images distinctes, {2, 1, 3, 4}. L'application est injective et couvre les quatre personnes sans réutiliser un choix.
En pratique
Dans le problème des listes, on commence par chercher un groupe dont les possibilités disponibles collectivement sont trop peu nombreuses. Un tel groupe fournit immédiatement un certificat d'impossibilité : aucune tentative d'attribution ne pourra éviter le doublon.
Dans un graphe biparti, on place les éléments à couvrir d'un côté et leurs choix de l'autre. Une attribution correspond à des arêtes sans sommet commun. Le théorème décide si des arêtes peuvent couvrir tout le premier côté.
Lorsque la condition est satisfaite, le théorème garantit l'existence d'une attribution, mais il ne dit pas qu'elle est unique. Dans l'exemple, A→1, B→3, C→2 et D→4 convient aussi.
À ne pas confondre
Injection et bijection. Le théorème demande que chaque élément de F reçoive un élément différent de G : c'est une injection. Si G contient un cinquième choix inutilisé pour seulement quatre éléments de F, l'attribution reste injective, mais elle n'est pas une bijection de F sur G.
Couplage couvrant F et couplage parfait. Un couplage couvrant F peut laisser des sommets de G libres. Un couplage parfait couvre les deux côtés. Avec quatre sommets dans F et cinq dans G, le premier peut exister, tandis que le second est impossible.
Limites et pièges
Tester seulement les listes individuelles ne suffit pas. Trois listes peuvent chacune contenir deux choix tout en ayant la même réunion {1, 2}. Le symptôme est le groupe de taille trois avec seulement deux voisins ; il faut examiner les réunions de listes.
Tester seulement le groupe entier ne suffit pas. L'ensemble F peut avoir assez de voisins au total alors qu'un sous-groupe reste bloqué. Il faut vérifier la condition pour toute partie X de F, car une possibilité réservée à d'autres éléments ne débloque pas ce sous-groupe.
Existence ne signifie pas unicité. La condition de Hall assure au moins une attribution injective. Dans l'exemple conducteur, deux attributions différentes conviennent ; il faut donc une information supplémentaire si l'on cherche à établir l'unicité.
Le vocabulaire dépend de ce qui doit être couvert. Lorsque |G| est supérieur à |F|, couvrir tout F laisse nécessairement des choix inutilisés. Il faut parler de couplage saturant F, et réserver « parfait » au cas où chaque sommet des deux côtés est couvert.
Pour aller plus loin
Le graphe biparti donne le cadre visuel du théorème : deux familles de sommets, reliées seulement d'un côté à l'autre.
La fiche sur l'injection précise pourquoi des images distinctes traduisent exactement l'interdiction d'attribuer deux fois le même choix.
L'analyse combinatoire replace ce critère d'existence dans l'étude des choix et des configurations finies.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres