X ENS Informatique C MPI 2025Sujet, corrigé et rapport du jury

ECOLE POLYTECHNIQUE ECOLES NORMALES SUPERIEURES

CONCOURS D'ADMISSION 2025

JEUDI 17 AVRIL 2025 08h00-12h00

FILIERE MPI - Epreuve n^∘7

INFORMATIQUE C (XULSR)

Couplages maximaux et parfaits

• Option.get: 'a option -> 'a renvoie v si l'argument de type 'a option est égal à Some v , et lève une exception sinon. La complexité est en O(1).
• List.length: 'a list -> int renvoie la taille de la liste donnée en argument. La complexité est en O(n), où n est la longueur de la liste donnée en argument.
• List.hd: 'a list -> 'a renvoie le premier élément de la liste donnée en argument si celle-ci n'est pas vide, et lève une exception sinon. La complexité est en O(1).
• List.tl: 'a list -> 'a list renvoie la liste donnée en argument privée de son premier élément si la liste donnée en argument n'est pas vide, et lève une exception sinon. La complexité est en O(1).
• List.rev: 'a list -> 'a list renvoie la liste donnée en argument dans l'ordre inverse. La complexité est en O(n), où n est la longueur de la liste donnée en argument.
• List.map: ('a -> 'b) -> 'a list -> 'b list renvoie la liste de type 'b list obtenue en appliquant la fonction de type ' a -> ' b donnée en premier argument à chaque élément de la liste de type 'a list donnée en second argument. Si la complexité de f est en O(1), alors la complexité de List.map f lst est en O(n), où n est la longueur de lst.
• List.mem: 'a -> 'a list -> bool renvoie true si la valeur donnée en premier argument est un élément de la liste donnée en second argument, et renvoie false sinon. La complexité est en O(n), où n est la longueur de la liste donnée en second argument.
• List.assoc: 'a -> ('a * 'b) list -> 'b: cette fonction spécifique aux listes d'association est décrite en page 4.

• Un chemin est une suite finie de sommets v_0, v_1, …, v_n avec n ⩾ 0 et telle que pour tout i = 0, …, n − 1, on a {v_i, v_(i + 1)} ∈ E. La longueur du chemin v_0, v_1, …, v_n est n.
• Un chemin est élémentaire si ses sommets sont deux-à-deux distincts.
• Un cycle est un chemin v_0, v_1, …, v_n de longueur ⩾ 3, avec v_0 = v_n et tel que le chemin v_1, …, v_n est élémentaire. Autrement dit, le seul sommet autorisé à apparaître plusieurs fois dans un cylce v_0, v_1, …, v_n est le sommet v_0 = v_n, qui apparaît exactement deux fois (une fois au début et une fois à la fin).

Partie I : Algorithme d'Edmonds

• les sommets du graphe sont exactement les clefs de la liste d'association;
• chaque clé de la liste d'association est unique.

Couplages

Considérons par exemple le graphe :

Les arêtes d'un couplage sont représentées par des traits plus épais. Par exemple, les trois couplages ci-dessus sont représentés comme suit :

Question 3. On considère le graphe suivant :

Couplages maximaux

Considérons le graphe suivant :

Chemins d'augmentation

• v_0 et v_n ne sont pas couverts par C;
• c'est un chemin alternant : pour tout i = 0, …, n − 2, on a {v_i, v_(i + 1)} ∈ C si et seulement si {v_(i + 1), v_(i + 2)} ∉ C.
  Un chemin d'augmentation P pour C permet de construire un nouveau couplage C(P) constitué des arêtes de C qui ne sont pas dans P et des arêtes de P qui ne sont pas dans C.

Par exemple, dans le graphe

le chemin suivant est un chemin d'augmentation :

Le nouveau couplage obtenu à partir de ce chemin d'augmentation est le suivant :

Question 7. On considère le graphe et le couplage suivants :

Bourgeons

L'algorithme d'Edmonds va de plus effectuer des opérations de contraction de bourgeons. Soit C un couplage dans un graphe G. Un bourgeon est un cycle dans G de longueur impaire 2m + 1 dont exactement m arêtes sont dans C. La base b d'un bourgeon B est le seul sommet
de B dont les deux arêtes adjacentes dans B ne sont pas dans C :

• L'ensemble des sommets du graphe G/L est (V∖L) ∪ {w} où w, le nouveau sommet de G/L, est un entier qui n'est pas un sommet de G.
• Les arêtes de G/L sont les arêtes de G entre sommets n'étant pas dans L, ainsi que les arêtes de la forme {u, w} où u n'appartient pas à L mais est adjacent dans G à un sommet de L. L'ensemble des arêtes de G/L est donc défini comme
  {{u, v} ∈ E|u ∉ L et v ∉ L} ∪ {{u, w}|u ∉ L et u adjacent dans G à un sommet de L}

• les arêtes {a, b} ∈ C telles que a ∉ B et b ∉ B;
• les arêtes {a, w} telles que a ∉ B et telles qu'il existe un b ∈ B avec {a, b} ∈ C.

Recherche de chemins d'augmentation

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

• La fonction frais: int list -> int renvoie un entier n'appartenant pas à la liste donnée en argument.
• La fonction prochain: foret -> int list -> int option prend en arguments une forêt f et une liste de sommets lst. Un appel prochain f lst renvoie Some d où d est un entier apparaissant dans f à profondeur paire et n'appartenant pas à lst si un tel entier d existe. Sinon, prochain f lst revoie None.
• La fonction apparie: couplage -> int -> int prend en arguments un couplage cpl et un sommet u couvert par le couplage, et renvoie le sommet apparié, c'est-à-dire l'unique v tel que (min uv, maxuv ) appartient à cpl .
• La fonction gonfle: graphe -> int list -> int list -> int -> int list prend en arguments un graphe grph, un bourgeon brg, un chemin d'augmentation dans le graphe contracté grph/brg, et le nom du nouveau sommet nv, et renvoie le chemin d'augmentation correspondant dans grph.

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

Partie II : Calculs de déterminants

Préliminaires : matrices linéarisées

int read_sqmatrix (int n, int *A, int i, int j)
void write_sqmatrix (int n, int *A, int i, int j, int val)

• read_sqmatrix ( n, A, i, j ) renvoie la valeur du coefficient A_(i, j) où A est la matrice n × n représentée par A ;
• write_sqmatrix( n, A, i, j, val) modifie la valeur du coefficient A_(i, j) pour qu'il soit égal à val.
  On supposera que A est un tableau avec n^2 éléments et que i, j ∈ {0, …, n − 1}.
  On attend une complexité en O(1) pour ces fonctions, sans la justifier.

Algorithme de Mahajan-Vinay

• les sommets de G(A) sont les entiers de 0 à n − 1,
• les arcs sont les paires ordonnées e = (i, j) telles que A_(i, j) ≠ 0,
• le poids ω(e) d'un arc e = (i, j) est égal à A_(i, j).

• pour tout i = 0, …, m − 1, il existe un arc ( v_i, v_(i + 1) ) dans G(A);
• le sommet v_0 = v_m est le plus petit entier de la suite, appelé la tête de C, notée t(C);
• le sommet v_0 n'apparaît qu'au début et à la fin de la suite : pour tout i = 1, …, m − 1, on a v_i ≠ v_0.
  La longueur |C| de la marche fermée C est le nombre d'arcs qui la composent. La longueur de C = v_0…v_m est donc égale à m. Le poids ω(C) d'une marche fermée C est le produit des poids des arcs (avec multiplicités) qui la composent :

Exemple. Considérons le graphe suivant, dont les arcs ont tous poids 1 :

• les têtes sont croissantes : t(C_1) < t(C_2) < ⋯ < t(C_k);
• le nombre total d'arcs (en comptant les multiplicités) est égal au nombre de sommets n de G(A) : ∑_(i = 1)^k|C_i| = n.
  Le poids d'une suite de marches fermées est le produit des poids des marches fermées qui la composent : ω(S) = ∏_(i = 1)^k ω(C_i). La tête de S, notée t(S), est la tête de la première marche fermée de S : t(S) = t(C_1).

Question 25. On considère le graphe suivant :

(1) Donner les marches fermées de longueur au plus 3 et leurs poids.
(2) Donner les suites de marches fermées et leurs poids.

• le signe de la suite de marches fermées C_1, …, C_k est (− 1)^p;
• h est la tête de la marche fermée en cours de construction, c'est-à-dire h = v_0;
• u est le sommet courant, c'est-à-dire u = v_m;
• i est le nombre d'arcs parcourus jusque là, c'est-à-dire i = m + ∑_(j = 1)^k|C_j|.

La figure ci-dessous représente certains sommets du graphe H_A correspondant, ainsi que certains arcs. Indiquer les arcs manquants entre les sommets représentés, ainsi que leurs poids.

Implémentation

• Un type Fourtable.
• Une fonction Fourtable *create (int n). Un appel create(n) alloue dans le tas une valeur de type Fourtable et renvoie un pointeur t vers celle-ci. La valeur ∗t ainsi créée a la taille nécessaire pour enregistrer les valeurs de F_A lorsque A est une matrice n × n. Les valeurs contenues dans *t sont toutes initialisées à 0 . On supposera que free( t ) a une complexité en O(1).
• Une fonction void write(Fourtable *t, int val, int p, int h, int v, int i) qui enregistre dans *t l'entier val comme valeur correspondant au sommet ⟨p, h, v, i⟩.
• Une fonction int read (Fourtable *t, int p, int h, int v, int i) qui renvoie la valeur correspondant au sommet ⟨p, h, v, i⟩ dans ∗t.
  On suppose de plus que les fonctions read et write ont une complexité en O(1), et que la fonction create a une complexité en O(n^3), où n est la valeur donnée en argument.

Partie III : Méthode algébrique et probabiliste pour les couplages parfaits