Corrigé Centrale 2025 Informatique MPI — Partie B, I (couplages) (Q22 à Q29) : Couplage maximum : chemins augmentants, Hopcroft-Karp (OCaml)

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

Énoncé

$G = (S, A)$ , graphe des cases d'un terrain (arêtes entre cases adjacentes), est biparti : noires $N = [[0, p [[$ , blanches $B = [[p, r [[$ . Il est donné par g : int list array (listes d'adjacence) et p. Un couplage $C \subseteq A$ est représenté par conjoint : int option array : None si $x$ est libre, Some y (et Some x en $y$ ) si $x$ , $y$ sont conjoints. Un chemin $x_{0} - \dots - x_{k}$ est la liste [x0; ...; xk] ; il est élémentaire si ses sommets sont distincts, alternant s'il est élémentaire et que ses arêtes alternent entre $C$ et $A ∖ C$ , augmentant s'il est alternant à extrémités libres. $X Δ Y = (X \cup Y) ∖ (X \cap Y)$ .
Q22. Si $w$ est augmentant pour $C$ , $C Δ w$ est un couplage.
Q23. delta (conjoint : int option array) (w : int list) : unit remplace $C$ par $C Δ w$ ( $w$ augmentant).

$G_{C}$ : mêmes sommets ; pour chaque arête $n - b$ ( $n \in N$ , $b \in B$ ), l'arc $b \to n$ si $n - b \in C$ , l'arc $n \to b$ sinon. $N_{ℓ}$ , $B_{ℓ}$ : sommets libres de $N$ , de $B$ .


type couplage = {
  graphe : int list array;
  p : int;
  conjoint : int option array;
}

Q24. Un chemin $x_{0} - \dots - x_{k}$ de $G$ avec $x_{0} \in N_{ℓ}$ , $x_{k} \in B_{ℓ}$ est augmentant si et seulement si $x_{0} \to \dots \to x_{k}$ est un chemin de $G_{C}$ .
Q25. oriente (c : couplage) : int list array renvoie $G_{C}$ .

$d (x)$ : plus petite longueur d'un chemin alternant d'un $n \in N_{ℓ}$ à $x$ ( $+ \infty$ , codé max_int, s'il n'y en a pas) ; $d_{m i n}$ : longueur d'un plus court chemin augmentant (max_int s'il n'y en a pas).


type distance = {
  d : int array;
  dmin : int;
}

Q26. distance (c : couplage) : distance, avec le module Queue (create, push, pop, is_empty).

On cherche des chemins augmentants de longueur $d_{m i n}$ sans sommet commun : $G_{H K}$ garde les arcs $x \to y$ de $G_{C}$ tels que $d (y) = d (x) + 1 ⩽ d_{m i n}$ ; depuis chaque $x \in N_{ℓ}$ , un parcours en profondeur de $G_{H K}$ cherche un chemin vers $B_{ℓ}$ , dont on retire les sommets. On ne construit pas $G_{H K}$ .


exception Chemin of int list

let ensemble_hc (c : couplage) (dist : distance) : int list list =
  let r = Array.length c.graphe in
  let visite = Array.make r false in
  let go = oriente c in
  let ensemble = ref [] in
  let rec chemin (x : int) (w : int list) : unit =
    <code1>
  in
  <code2>
  !ensemble

Q27. <code1> : parcours en profondeur dans $G_{H K}$ depuis $x$ , le chemin déjà parcouru étant $w$ à l'envers ; lever Chemin w quand un chemin augmentant $w$ est trouvé.
Q28. <code2>.
Q29. Avec le lemme de Berge (admis), écrire couplage_maximum (g : int list array) (p : int) : int option array.

Corrigé

Tout le code OCaml a été exécuté (OCaml 5.4) : sur les terrains de la figure 4 et de Q19 à Q21, sur la grille $6 \times 6$ , sur un sommet isolé, puis sur $3000$ terrains aléatoires (jusqu'à $8 \times 8$ ) et $2000$ graphes bipartis aléatoires, où le cardinal obtenu coïncide toujours avec celui de l'algorithme élémentaire du livre (chapitre 24) et où le résultat est vérifié être un couplage (conjoint symétrique, arêtes du graphe, une extrémité dans $N$ ).

Q22. Soit $w = x_{0} - x_{1} - \dots - x_{k}$ augmentant. Comme $x_{0}$ est libre, l'arête $x_{0} x_{1}$ n'est pas dans $C$ ; par alternance, les arêtes $x_{2 i} x_{2 i + 1}$ sont hors de $C$ et les arêtes $x_{2 i + 1} x_{2 i + 2}$ dans $C$ ; comme $x_{k}$ est libre, la dernière arête est hors de $C$ , et $k$ est impair. $C Δ w$ s'obtient en retirant de $C$ les arêtes $x_{2 i + 1} x_{2 i + 2}$ et en ajoutant les arêtes $x_{2 i} x_{2 i + 1}$ . Comptons, pour chaque sommet $v$ , les arêtes de $C Δ w$ dont il est extrémité.

$v$ n'est pas sur $w$ : aucune arête de $w$ ne le touche, ses arêtes dans $C Δ w$ sont celles de $C$ : au plus une.
$v = x_{i}$ avec $0 < i < k$ : le chemin étant élémentaire, $v$ apparaît une seule fois, et exactement deux arêtes de $w$ le touchent, $x_{i - 1} x_{i}$ et $x_{i} x_{i + 1}$ , l'une dans $C$ et l'autre non. Son unique arête de $C$ est donc sur $w$ et disparaît ; seule l'autre arête de $w$ en $v$ est ajoutée. Il est extrémité d'exactement une arête.
$v = x_{0}$ ou $x_{k}$ : libre dans $C$ , il gagne la seule arête de $w$ qui le touche : exactement une.

$C Δ w$ est donc un couplage, et $∣ C Δ w ∣ = ∣ C ∣ + 1$ ( $w$ a une arête de plus hors de $C$ que dans $C$ ).

Q23. D'après Q22, les nouvelles paires de conjoints sont $(x_{0}, x_{1}), (x_{2}, x_{3}), \dots, (x_{k - 1}, x_{k})$ , et chaque sommet de $w$ en fait partie : il suffit de les écrire, les anciens partenaires étant écrasés.


let rec delta (conjoint : int option array) (w : int list) : unit =
  match w with
  | x :: y :: suite ->
    conjoint.(x) <- Some y;
    conjoint.(y) <- Some x;
    delta conjoint suite
  | _ -> ()

Tout sommet de $w$ reçoit son nouveau conjoint, et ses anciennes valeurs (un conjoint pris sur $w$ , d'après Q22) sont remplacées ; les sommets hors de $w$ ne sont pas touchés, et leurs conjoints sont hors de $w$ . La liste ayant $k + 1$ éléments, nombre pair, le filtrage consomme deux sommets à chaque appel et finit sur la liste vide. Récursivité terminale, coût $O (k)$ . La liste renversée [xk; ...; x0] donnerait les mêmes paires, puisque $k - 1$ est pair. Exécuté : le couplage ${1 - 3}$ et le chemin [0; 3; 1; 4] donnent [|Some 3; Some 4; None; Some 0; Some 1|].

Q24. Ce que le correcteur attend : le rapport du jury signale une erreur d'énoncé : il faut supposer le chemin élémentaire, car un chemin de $G_{C}$ peut repasser par un sommet. Par exemple, si $n_{1} - b_{2}$ et $n_{2} - b_{1}$ sont dans $C$ , et $n_{0}$ , $b_{3}$ libres, $n_{0} \to b_{1} \to n_{2} \to b_{2} \to n_{1} \to b_{1} \to n_{2} \to b_{3}$ est un chemin de $G_{C}$ (avec les arêtes $n_{0} - b_{1}$ , $n_{2} - b_{2}$ , $n_{1} - b_{1}$ , $n_{2} - b_{3}$ hors de $C$ ) qui n'est pas augmentant. On montre donc : un chemin élémentaire de $x_{0} \in N_{ℓ}$ à $x_{k} \in B_{ℓ}$ est augmentant si et seulement si $x_{0} \to \dots \to x_{k}$ est un chemin de $G_{C}$ .

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 →