Corrigé CCINP 2025 Informatique MPI — Partie III (III.2) (Q26 à Q31) : Couplages Pareto-optimaux par circuits du graphe des premiers choix

Q26. Dans $\mathcal{G}$, tout sommet a exactement un successeur : un $v\in V$ a un unique premier choix dans $U$, un $u\in U$ un unique premier choix dans $V$ (les ordres sont totaux et l'autre groupe est non vide, $n⩾1$). Partons d'un sommet $x_0$ et suivons les arcs : $x_0\to x_1\to x_2\to \cdots$, où $x_{i+1}$ est l'unique successeur de $x_i$. Cette suite est infinie et prend ses valeurs dans l'ensemble fini $S$, de cardinal $2n$ : il existe $i<j$ avec $x_i=x_j$ (principe des tiroirs, dès les indices $0$ à $2n$). Le chemin $x_i\to x_{i+1}\to \cdots \to x_j$ a ses deux extrémités égales : c'est un circuit. Il n'y a pas de boucle (un arc relie toujours $V$ à $U$), donc un circuit alterne entre $V$ et $U$ et a une longueur paire $⩾2$.

Q27. On parle de circuits élémentaires (aucun sommet répété, sauf l'extrémité) ; un chemin fermé non élémentaire passant par $x$ ne fait que répéter le même tour, comme on va le voir. Supposons par l'absurde que $x$ appartienne à deux circuits distincts $C$ et $C^{\prime }$. Écrivons-les en partant de $x$ : $C=(x=y_0,y_1,\dots ,y_p=x)$ et $C^{\prime }=(x=z_0,z_1,\dots ,z_q=x)$, où $p$ (resp. $q$) est le premier retour en $x$. Chaque sommet n'ayant qu'un successeur, $y_1=z_1$ (successeur de $x$), puis par récurrence $y_i=z_i$ pour tout $i⩽\min (p,q)$. Si l'on avait $p<q$, on aurait $z_p=y_p=x$ avec $0<p<q$, contredisant le fait que $q$ est le premier retour en $x$ ; de même $q<p$ est exclu. Donc $p=q$ et $C=C^{\prime }$ : contradiction. Tout sommet est donc dans au plus un circuit. Conséquence utile : les circuits sont deux à deux disjoints, et sur un circuit chaque $v$ a un seul arc sortant $(v,u)$ et chaque $u$ un seul arc entrant : les arcs $(v,u)$ des circuits forment un couplage.