Graphe biparti et mariage de Hall

Énoncé du problème

Dans une école, chaque élève choisit exactement k cours parmi n cours disponibles. Chaque cours est choisi par exactement k élèves.

Modéliser la situation par un graphe biparti k-régulier.
Énoncer le théorème de Hall : un graphe biparti G=(A∪B, E) possède un couplage parfait de A vers B si et seulement si pour tout S ⊆ A, |N(S)| ≥ |S| (où N(S) est l'ensemble des voisins de S).
Montrer que dans le cas k-régulier ci-dessus (même nombre d'élèves et de cours), il existe un emploi du temps où chaque cours peut être assigné à un élève différent (couplage parfait).

1. Sommets A = élèves, sommets B = cours. Arête entre élève e et cours c si e suit c. Chaque sommet de A a degré k, chaque sommet de B a degré k → graphe biparti k-régulier.

2. Théorème de Hall : G biparti a un couplage parfait (A → B, chaque sommet de A a un partenaire distinct dans B) ⇔ ∀S⊆A, |N(S)| ≥ |S|. (Le sens → est évident ; le sens ← se prouve par induction ou par flots max.)

3. Vérifions la condition de Hall. Soit S ⊆ A (ensemble d'élèves). Les arêtes issues de S : |S|×k arêtes. Ces arêtes arrivent dans N(S) ⊆ B, et chaque sommet de B a degré ≤ k → |N(S)|×k ≥ |S|×k → |N(S)| ≥ |S|. La condition de Hall est vérifiée → couplage parfait existe. ✓

Énoncé du problème

Solution détaillée