Corrigé X-ENS 2025 Informatique C MPI — Partie I (1) (Q1 à Q10) : Listes, couplages, chemins d'augmentation

Sujet officiel du concours X-ENS, session 2025, épreuve Informatique C MPI. Corrigé rédigé par Ibrahim Alame.

Énoncé

Partie à composer en OCaml. Seules les fonctions de bibliothèque Option.get, List.length, List.hd, List.tl, List.rev, List.map, List.mem et List.assoc (première valeur associée à une clef, exception sinon, coût linéaire) sont permises. Les graphes $G = (V, E)$ sont non orientés, sans boucle, $V$ non vide. Un couplage est un ensemble d'arêtes deux à deux disjointes ; un sommet est couvert s'il est extrémité d'une arête du couplage ; un couplage est maximal (au sens du sujet) s'il a un nombre maximal d'arêtes. Une fonction join (réunion sans répétition de deux listes) est fournie.


type graphe = (int * (int list)) list   (* (sommet, voisins) *)
type couplage = (int * int) list        (* (min a b, max a b) *)

Un chemin d'augmentation pour $C$ est un chemin élémentaire $v_{0}, \dots, v_{n}$ ( $n > 0$ ) dont les extrémités ne sont pas couvertes et dont les arêtes sont alternativement hors de $C$ et dans $C$ ; $C (P)$ est formé des arêtes de $C$ hors de $P$ et des arêtes de $P$ hors de $C$ . Un chemin est codé par la liste de ses sommets.

Q1. Écrire del : 'a list -> 'a list -> 'a list (éléments de lst1 absents de lst2), en $O (m_{1} m_{2})$ .
Q2. Écrire keys : ('a * 'b) list -> 'a list, en $O (m)$ .
Q3. Dans le graphe ci-dessous à gauche, lesquels sont des couplages : (1) ${{1, 2}, {0, 5}}$ , (2) ${{1, 3}, {0, 5}}$ , (3) ${{0, 1}, {2, 3}, {0, 5}}$ ?
Q4. Écrire couverts : couplage -> int list, en $O (m)$ .
Q5. Dans le graphe (1) (au centre), où ${{0, 5}, {2, 3}, {1, 4}}$ est maximal, donner un autre couplage maximal.
Q6. Dans le graphe (1), donner un chemin d'augmentation $P$ pour $C = {{0, 5}, {2, 4}}$ tel que $C (P)$ soit maximal.
Q7. Pour le graphe et le couplage (traits épais) de droite, donner un chemin d'augmentation et le couplage augmenté.
Q8. Montrer que $C (P)$ est un couplage ayant strictement plus d'arêtes que $C$ .
Q9. Écrire separer : int list -> ((int * int) list) * ((int * int) list) qui sépare les arêtes d'un chemin d'augmentation en lstin (dans le couplage) et lstout (hors du couplage), en $O (m)$ .
Q10. Écrire augmente : couplage -> int list -> couplage qui renvoie cpl(chm).

Corrigé

Q1. On parcourt lst1 en ne gardant que les éléments absents de lst2 :


let rec del lst1 lst2 =
  match lst1 with
  | [] -> []
  | x :: reste -> if List.mem x lst2 then del reste lst2
                  else x :: del reste lst2

Chaque élément de lst1 donne un appel à List.mem en $O (m_{2})$ : $O (m_{1} m_{2})$ au total. L'ordre et les répétitions de lst1 sont conservés (List.filter, non autorisée, est à proscrire).

Q2. On garde la première composante de chaque couple :


let keys lst = List.map (fun (clef, _) -> clef) lst

Coût : $O (m)$ (fst n'étant pas dans la liste autorisée, on filtre le couple). La concaténation @ n'y figurant pas non plus, on se donne aussi, pour la suite, la concaténation (coût linéaire en la première liste) :


let rec concat lst1 lst2 =
  match lst1 with
  | [] -> lst2
  | x :: reste -> x :: concat reste lst2

Q3. Les arêtes du graphe sont ${2, 3}$ , ${1, 3}$ , ${0, 2}$ , ${0, 1}$ , ${2, 5}$ , ${0, 5}$ , ${1, 5}$ .

(1) n'est pas un couplage : ${1, 2}$ n'est pas une arête du graphe.
(2) est un couplage : ${1, 3}$ et ${0, 5}$ sont des arêtes, sans extrémité commune.
(3) n'est pas un couplage : le sommet $0$ appartient à ${0, 1}$ et à ${0, 5}$ .

Q4. Les arêtes d'un couplage sont disjointes : la liste de leurs extrémités est déjà sans répétition (inutile, et coûteux, d'appeler join).


let rec couverts cpl =
  match cpl with
  | [] -> []
  | (a, b) :: reste -> a :: b :: couverts reste

Un appel par arête, chacun en $O (1)$ : $O (m)$ .

Q5. ${{0, 5}, {1, 2}, {3, 4}}$ : ce sont trois arêtes du graphe (1), disjointes, et un couplage d'un graphe à $6$ sommets a au plus $⌊ 6/2 ⌋ = 3$ arêtes ; il est donc maximal. (C'est le seul autre : le sommet $0$ n'a que les voisins $2$ et $5$ , et $5$ que $0$ et $2$ ; un couplage à $3$ arêtes couvre $0$ et $5$ , donc contient ${0, 5}$ , puis deux arêtes disjointes couvrant $1, 2, 3, 4$ : ${2, 3}, {1, 4}$ ou ${1, 2}, {3, 4}$ .)

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 →