Théorème de Hall

1 Théorème de Hall

Le théorème de Hall, parfois appelé critère de Hall ou théorème du mariage, est un résultat fondamental en théorie des graphes et en combinatoire. Ce théorème fournit une condition nécessaire et suffisante pour qu'une famille finie de sous-ensembles possède une transversale, c'est-à-dire un système distinct de représentants. Il est notamment utilisé pour établir l'existence de couplages parfaits dans certains graphes bipartis.

1.1 Introduction au théorème de Hall : importance et contexte

Le théorème de Hall tire son origine du travail de Philip Hall en 1935. Il joue un rôle crucial dans la résolution de problèmes d’affectation et de couplages parfaits, où il est souvent nommé théorème du mariage en raison de son application imagée : garantir que chaque personne puisse être "mariée" à une cible compatible sans conflit.

1.1.1 Définition intuitive

Imaginez un groupe de personnes et un ensemble de chaussures de tailles différentes. Chaque personne aime certaines chaussures. Le théorème de Hall dit exactement quand il est possible de distribuer à chaque personne une chaussure qu'elle aime, sans que deux personnes aient la même chaussure.

1.2 Énoncé formel du théorème de Hall

Soit une famille finie de sous-ensembles $\mathcal{F} = \{A_1, A_2, \dots, A_n\}$ d’un ensemble $U$. On dit que $\mathcal{F}$ possède une transversale (ou SDR, pour System of Distinct Representatives) s’il existe une suite $(x_1, x_2, \dots, x_n)$ telle que pour tout $i$, $x_i \in A_i$, et tous les $x_i$ sont distincts.

1.2.1 Énoncé

Le théorème de Hall affirme que :

La famille $\mathcal{F} = \{A_1, A_2, \dots, A_n\}$ possède une transversale si et seulement si pour tout sous-ensemble $J \subseteq \{1, 2, \dots, n\}$, on a :

$$ \left| \bigcup_{j \in J} A_j \right| \geq |J|. $$

Cette condition est appelée « condition de Hall ».

1.3 Applications du théorème de Hall : couplages parfaits et problèmes d’affectation

1.3.1 Couplages parfaits dans les graphes bipartis

Dans un graphe biparti $G = (X \cup Y, E)$, un couplage parfait est un ensemble d’arêtes couvrant tous les sommets. Le théorème de Hall assure l'existence d'un couplage parfait reliant $X$ à $Y$ si et seulement si, pour tout sous-ensemble $S \subseteq X$, le nombre de voisins de $S$ dans $Y$, noté $N(S)$, est au moins $|S|$ :

$$ \forall S \subseteq X, \quad |N(S)| \geq |S|. $$

Ce critère est crucial pour les algorithmes d’affectation optimale et trouve des applications en économie, informatique et télécommunications.

1.3.2 Résolution pratique de problèmes d'affectation

Le théorème de Hall permet de confirmer l'existence d'une solution possible dans des contextes variés : assigner des tâches à des agents, distribuer des ressources ou organiser des rencontres.

1.4 Preuve simple du théorème de Hall

On démontre le théorème par récurrence sur la taille $n$ de la famille $\mathcal{F}$. Pour $n=1$, la condition est évidente. Supposons vrai pour $n-1$. Deux cas se présentent :

• Si pour tout $J \subsetneq \{1,...,n\}$, $\left| \bigcup_{j \in J} A_j \right| > |J|$, alors on peut extraire un élément d’un $A_i$ et appliquer l’hypothèse de récurrence.

• Sinon, il existe un sous-ensemble $J$ avec l’égalité stricte, permettant de séparer le problème en deux sous-problèmes indépendants.

Ce raisonnement garantit la construction progressive d’une transversale.

1.5 Exemple concret avec application

Considérons la famille $\mathcal{F} = \{A_1, A_2, A_3\}$ avec

• $A_1 = \{a,b\}$,
• $A_2 = \{b,c\}$,
• $A_3 = \{a,c\}$.

On vérifie la condition de Hall :

• $|A_1| = 2 \geq 1$,
• $|A_2| = 2 \geq 1$,
• $|A_3| = 2 \geq 1$,
• $|A_1 \cup A_2| = |\{a,b,c\}|=3 \geq 2$,
• $|A_2 \cup A_3| = 3 \geq 2$,
• $|A_1 \cup A_3| = 2 \geq 2$,
• $|A_1 \cup A_2 \cup A_3| = 3 \geq 3$.

La condition est satisfaite, donc il existe une transversale. Par exemple, on peut choisir $x_1 = b \in A_1$, $x_2 = c \in A_2$, $x_3 = a \in A_3$.

1.6 Voir aussi

• Système distinct de représentants
• Couplage parfait
• Théorème de König
• Théorie des graphes
• Combinatoire