Hall et König

1. Le couplage maximum mesuré vaut $3$ : par exemple $e_1{s}_0$, $e_0{s}_1$, $e_3{s}_2$. On ne peut pas saturer les quatre étudiants, et l'argument est le certificat de Hall : posons $S=\{e_0,e_1,e_2\}$. Le voisinage de $S$ est $N(S)=\{s_0,s_1\}$, donc

$$|N(S)|=2<3=|S|.$$

Trois étudiants qui se disputent deux stages : deux d'entre eux au plus peuvent être placés, quel que soit l'algorithme. Le théorème de Hall dit que cette condition est la seule obstruction : un couplage saturant la partie gauche existe si et seulement si $|N(S)|\ge |S|$ pour tout sous-ensemble $S$ de la partie gauche.

Ce que le certificat apporte. Quand l'algorithme échoue à placer tout le monde, il ne se contente pas de dire « je n'y arrive pas » : l'ensemble des sommets visités lors de la dernière recherche infructueuse fournit un tel $S$. On peut donc expliquer l'échec à l'utilisateur — « ces trois étudiants ne visent que ces deux stages » —, ce qui est une information autrement plus utile qu'un refus.

2. Sur l'affectation à cinq étudiants et cinq stages, la plus petite couverture mesurée compte 5 sommets, exactement comme le couplage maximum. Ce n'est pas une coïncidence : c'est le théorème de König, vérifié ici sur $4000$ graphes bipartis aléatoires sans un seul écart.

$$\text{dans un graphe biparti :}\underset{\text{couplage}}{\max }|M|=\underset{\text{couverture}}{\min }|C|.$$

L'inégalité $|M|\le |C|$ est facile — chaque arête du couplage a besoin d'un sommet de la couverture, et deux arêtes du couplage ne peuvent pas partager ce sommet. C'est l'égalité qui est le théorème, et le problème « Le théorème de König » la démontre en construisant la couverture à partir d'un couplage maximum.

Attention : l'égalité est fausse hors du cas biparti. Sur un triangle, le couplage maximum vaut $1$ et la couverture minimale $2$.