Corrigé CCINP 2025 Informatique MPI — Partie III (III.1) (Q17 à Q25) : Couplages stables : l'algorithme de Gale-Shapley et son optimalité pour V

Sujet officiel du concours CCINP, session 2025, épreuve Informatique MPI. Corrigé rédigé par Ibrahim Alame.

Énoncé

Deux groupes $V$ et $U$ de même cardinal $n$ ; chaque élément a un ordre de préférence total sur l'autre groupe : $v_{1} >^{u} v_{2}$ signifie que $u$ préfère strictement $v_{1}$ à $v_{2}$ (et $⩾^{u}$ l'ordre large). Un couplage $A \subseteq V \times U$ est un ensemble de paires où chaque élément apparaît au plus une fois ; il est parfait si chacun apparaît exactement une fois ; $m_{A} (x)$ est alors le partenaire de $x$ . Un couplage parfait est stable s'il n'existe pas $(v_{1}, u_{1}), (v_{2}, u_{2}) \in A$ avec $u_{2} >^{v_{1}} u_{1}$ et $v_{1} >^{u_{2}} v_{2}$ . Pour deux couplages parfaits stables $A$ , $A^{'}$ et $E \subseteq V \cup U$ , $A$ Pareto-domine $A^{'}$ sur $E$ si $m_{A} (x) ⩾^{x} m_{A^{'}} (x)$ pour tout $x \in E$ , strictement pour au moins un ; un couplage est Pareto-optimal s'il est stable et non Pareto-dominé sur $V \cup U$ .

Algorithme 3 (Gale-Shapley) : $A := \emptyset$ ; tant qu'un $v \in V$ est libre, on choisit un tel $v$ , qui propose au $u$ qu'il préfère parmi ceux à qui il n'a pas encore proposé ; si $u$ est libre, $(v, u)$ entre dans $A$ ; si $u$ est apparié à $v^{'}$ avec $v >^{u} v^{'}$ , $(v^{'}, u)$ sort de $A$ et $(v, u)$ y entre ; sinon rien ne change. On rend $A$ .

Jeu de données $D$ (ligne de $u_{2}$ : le sujet imprime $>^{u_{1}}$ en second, coquille relevée par le jury) :

$V$	$U$
$u_{2} >^{v_{1}} u_{1} >^{v_{1}} u_{3}$	$v_{1} >^{u_{1}} v_{3} >^{u_{1}} v_{2}$
$u_{1} >^{v_{2}} u_{2} >^{v_{2}} u_{3}$	$v_{2} >^{u_{2}} v_{1} >^{u_{2}} v_{3}$
$u_{1} >^{v_{3}} u_{2} >^{v_{3}} u_{3}$	$v_{2} >^{u_{3}} v_{1} >^{u_{3}} v_{3}$

Q17. Trace de l'algorithme 3 sur $D$ , le $v$ libre d'indice minimal proposant.
Q18. L'algorithme 3 termine.
Q19. Un invariant (sans preuve) montrant qu'il rend un couplage parfait.
Q20. Le couplage rendu est stable.
Q21. Il y a moins de $n^{2}$ itérations.

Pour deux couplages parfaits stables $A$ et $A^{'}$ , $x$ préfère $A$ à $A^{'}$ s'il a deux partenaires différents et préfère celui de $A$ .
Q22. Si $v$ préfère $A$ , son partenaire $u$ dans $A$ préfère $A^{'}$ .

$u$ est réalisable pour $v$ si un couplage parfait stable contient $(v, u)$ . $M (v)$ est le réalisable préféré de $v$ , et $A^{*} = {(v, M (v)), v \in V}$ .
Q23. Au cours de l'algorithme 3, $v$ n'est rejeté que par des $u$ non réalisables pour $v$ .
Q24. Pendant l'exécution : 1) un $v$ apparié l'est à un $u ⩾^{v} M (v)$ ; 2) un $v$ libre n'a proposé qu'à des $u >^{v} M (v)$ .
Q25. Quel que soit le choix de $v$ à chaque tour, l'algorithme 3 rend $A^{*}$ .

Corrigé

Vocabulaire. On dit que $v$ est rejeté par $u$ quand $u$ refuse sa proposition (dernier cas de l'algorithme) ou quand $u$ , qui l'avait accepté, le quitte pour un nouveau proposant. Deux faits découlent directement de l'algorithme et servent partout : (F1) chaque $v$ propose dans l'ordre décroissant de ses préférences, et ne propose à nouveau qu'après avoir été rejeté ; (F2) un $u$ qui a reçu une proposition reste apparié jusqu'à la fin, et son partenaire ne fait que s'améliorer selon $>^{u}$ .

Q17. On numérote les tours de boucle ; « libres » liste les éléments de $V$ libres en début de tour.

tour	libres	proposition	réponse	$A$ après le tour
1	$v_{1}, v_{2}, v_{3}$	$v_{1} \to u_{2}$	$u_{2}$ libre, accepte	$(v_{1}, u_{2})$
2	$v_{2}, v_{3}$	$v_{2} \to u_{1}$	$u_{1}$ libre, accepte	$(v_{1}, u_{2}), (v_{2}, u_{1})$
3	$v_{3}$	$v_{3} \to u_{1}$	$v_{3} >^{u_{1}} v_{2}$ : $v_{2}$ rejeté	$(v_{1}, u_{2}), (v_{3}, u_{1})$
4	$v_{2}$	$v_{2} \to u_{2}$	$v_{2} >^{u_{2}} v_{1}$ : $v_{1}$ rejeté	$(v_{2}, u_{2}), (v_{3}, u_{1})$
5	$v_{1}$	$v_{1} \to u_{1}$	$v_{1} >^{u_{1}} v_{3}$ : $v_{3}$ rejeté	$(v_{1}, u_{1}), (v_{2}, u_{2})$
6	$v_{3}$	$v_{3} \to u_{2}$	$v_{2} >^{u_{2}} v_{3}$ : refus	$(v_{1}, u_{1}), (v_{2}, u_{2})$
7	$v_{3}$	$v_{3} \to u_{3}$	$u_{3}$ libre, accepte	$(v_{1}, u_{1}), (v_{2}, u_{2}), (v_{3}, u_{3})$

L'algorithme rend $A = {(v_{1}, u_{1}), (v_{2}, u_{2}), (v_{3}, u_{3})}$ après $7$ tours. Il est bien stable : $v_{1}$ préférerait $u_{2}$ , mais $u_{2}$ préfère son partenaire $v_{2}$ ; $v_{2}$ préférerait $u_{1}$ , qui préfère $v_{1}$ ; $v_{3}$ préférerait $u_{1}$ ou $u_{2}$ , qui préfèrent tous deux leur partenaire. Ce que le correcteur attend : un $v$ ne repropose jamais à un $u$ qui l'a déjà rejeté (tour 5 : $v_{1}$ passe à son deuxième choix). Une simulation exécutée de l'algorithme donne la même suite de $7$ tours, et le programme C de Q34, exécuté sur $D$ , le même couplage.

100 % gratuit

La suite du corrigé est sur Adloun

Le corrigé rédigé en entier, question par question, et le tuteur pour poser des questions sur ce sujet.

Voir le corrigé complet, gratuitement

Inscription gratuite en 30 secondes (e-mail, nom d'utilisateur, mot de passe, classe ou profil), sans carte bancaire : arrivée directe sur le corrigé.

Toutes les parties de l'épreuve

Corrigé complet gratuit →