Imaginez un groupe d’hommes et un groupe de femmes. Chaque homme a une liste de femmes qu’il serait heureux d’épouser. Le but est de former autant de couples mariés (un homme, une femme) que possible, en respectant les préférences de chacun.
En théorie des graphes, cela se modélise par un graphe biparti.
- Un ensemble de sommets $H$ représente les hommes.
- Un ensemble de sommets $F$ représente les femmes.
- Une arête relie un homme $h \in H$ et une femme $f \in F$ si $h$ accepte d’épouser $f$.
- Un couplage (ou mariage) est un ensemble d’arêtes sans sommet commun. On cherche un couplage parfait qui couvre tous les hommes (si $|H| \le |F|$).
Dans un graphe biparti $G = (H \cup F, E)$, un couplage qui couvre tous les sommets de $H$ existe si et seulement si pour tout sous-ensemble d’hommes $A \subseteq H$, le nombre de femmes qu’ils connaissent collectivement est au moins aussi grand que le nombre d’hommes dans ce sous-ensemble.
Formellement : $\forall A \subseteq H, \quad |N(A)| \ge |A|$
Où $N(A)$ est l’ensemble des « voisins » de $A$, c’est-à-dire l’ensemble de toutes les femmes connectées à au moins un homme de $A$.
Interprétation et Applications
La condition de Hall est assez intuitive :
- Condition Nécessaire (évidente) : S’il existait un groupe de $k$ hommes qui, à eux tous, ne connaissaient que $k-1$ femmes (ou moins), il serait mathématiquement impossible de tous les marier, car il manquerait de partenaires.
- Condition Suffisante (la magie du théorème) : Le théorème de Hall nous dit que cette condition « évidente » est en fait la seule obstruction possible. Si cette condition est respectée pour tous les sous-groupes d’hommes possibles, alors une solution complète est garantie d’exister.
Applications concrètes :
Ce théorème va bien au-delà des histoires de mariages et est fondamental en optimisation combinatoire.
- Assignation de tâches : Un groupe d’employés ($H$) et un ensemble de tâches ($F$). Une arête existe si un employé est qualifié pour une tâche. Le théorème nous dit s’il est possible d’assigner une tâche unique à chaque employé.
- Jeux de cartes : Dans un jeu de 52 cartes, si on distribue les cartes en 13 paquets de 4 cartes, il est toujours possible de choisir une carte de chaque paquet de sorte à avoir exactement un représentant de chaque valeur (As, 2, 3, …, Roi).