Corrigé X-ENS 2025 Informatique C MPI — Partie I (2) (Q11 à Q21) : Bourgeons, forêts et algorithme d'Edmonds

Notations de la première moitié. Un bourgeon est un cycle de longueur $2m+1$ ayant $m$ arêtes dans $C$ ; sa base ($b$ ci-dessous, arêtes de $C$ épaisses) est le sommet dont les deux arêtes du cycle sont hors de $C$. On le code par la liste de ses sommets, sans répétition.

Pour $L\subseteq V$ et $w\notin V$, $G/L$ a pour sommets $(V\setminus L)\cup \{w\}$, pour arêtes celles de $G$ hors de $L$ et les $\{u,w\}$, $u\notin L$ voisin d'un sommet de $L$. renomme lst rnm w remplace dans lst les éléments de rnm par w, sans doublons. $C/B$ contient les $\{a,b\}\in C$ disjointes de $B$ et les $\{a,w\}$, $a\notin B$, $\{a,b\}\in C$, $b\in B$. Admis : $C/B$ a un chemin d'augmentation dans $G/B$ si et seulement si $C$ en a un dans $G$.

type arbre = N of int * foret
and foret = arbre list

Recherche. (1) $F$ : une racine (profondeur $0$) par sommet non couvert ; (2) $T=\varnothing$ ; (3) tant qu'un $u\notin T$ est à profondeur paire, l'ajouter à $T$ et, pour chaque voisin $v\notin T$ : (a) si $v\notin F$, ajouter à $F$ $\{u,v\}$ et $\{v,z\}\in C$ ; (b) si $u$, $v$ sont à profondeur paire : (i) arbres distincts : renvoyer les sommets de $r_u$ à $u$ puis de $v$ à $r_v$ ; (ii) même arbre : contracter le bourgeon et chercher dans $G/B$. Admis : l'algorithme réussit si et seulement s'il existe un chemin d'augmentation. Fournies : frais (entier neuf), prochain (sommet de profondeur paire non traité), apparie, gonfle (relève un chemin de $G/B$ dans $G$). Figure 1 :

let rec recherche graphe couplage =
    let nc = del (keys graphe) (couverts couplage) in
    let foret = ref (List.map (fun x -> N(x,[])) nc) in
    let rec aux_voisins u liste_voisins =
        let cu = Option.get (find !foret u) in
        match liste_voisins with
        | [] -> None
        | v :: tl ->
                  match find !foret v with
                  | None -> let z = apparie couplage v in
                            foret := extend (extend !foret u v) v z;
                            aux_voisins u tl
                  | Some cv when (List.length cv) mod 2 = 0
                  (* nombre de sommets pair = profondeur impaire *)
                         -> ...
                  | Some cv when (List.hd cu) <> (List.hd cv)
                         -> ...
                            ...
                  | Some cv
                         -> let bourgeon = extrait cu cv in
                            let nv = frais (keys graphe) in
                            let ng = contracteG graphe bourgeon nv in
                            let nc = contracteC couplage bourgeon nv in
                            ...
                            ...
                            ...
    in
    let rec aux_sommets traites =
        match prochain !foret traites with
        | None -> None
        | Some u -> let liste_voisins = del (List.assoc u graphe) traites in
                    match aux_voisins u liste_voisins with
                    | None -> aux_sommets (u::traites)
                    | Some ch -> Some ch
    in
    aux_sommets []

Q11. Écrire contracteG : graphe -> int list -> int -> graphe.
Q12. Montrer que $C/B$ est un couplage de $G/B$.
Q13. Écrire contracteC : couplage -> int list -> int -> couplage.
Q14. Écrire find : foret -> int -> (int list) option (chemin d'une racine à v), en $O(n)$.
Q15. Écrire extend : foret -> int -> int -> foret (nouvel enfant v sous chaque u), en $O(n)$.
Q16. Montrer que la suite renvoyée au cas (3)(b)(i) est un chemin d'augmentation.
Q17. Code de la ligne 15.
Q18. Code des lignes 17--18.
Q19. Écrire extrait : int list -> int list -> int list (bourgeon de la ligne 20).
Q20. Code des lignes 24--26.
Q21. Écrire edmonds : graphe -> couplage, qui renvoie un couplage maximal.