2025 X-ENS Info MPI C — Corrigé

Couplages maximaux et parfaits

Le sujet comporte 18 pages, numérotées de 1 à 18. Début de l’épreuve. Complexité.

Par la complexité d’un algorithme, on entend le nombre d’opérations élémentaires (comparaison, addition, soustraction, multiplication, division, affectation, test, etc.) nécessaires à l’exécution de celui-ci dans le pire cas.

Lorsque la complexité dépend d’un ou plusieurs paramètres {k_{0}, \ldots , k_{r}}, on dit que l’algorithme a une complexité en {O(f(k_{0}, \ldots , k_{r}))} s’il existe une constante C > 0 telle que, pour toutes les valeurs de {k_{0}, \ldots , k_{r}} suffisamment grandes (c’est-à-dire plus grandes qu’un certain seuil), pour toute instance du problème de paramètres {k_{0}, \ldots , k_{r}} la complexité est au plus {C\times f(k_0,\ldots,k_r)}.

Fonctions utiles en OCaml.

Dans les questions de programmation en OCaml, il est interdit d’utiliser des fonctions de la bibliothèque qui ne sont pas incluses dans la liste suivante.

— 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. Fonctions utiles en C.

Dans les questions de programmation en C, on pourra supposer que les en-têtes , , , et ont été inclus. En particulier, on pourra utiliser la fonction double log2(double x) définie par l’entête , qui calcule le logarithme en base 2. Présentation du sujet.

Ce sujet concerne les couplages dans les graphes non orientés. La partie I, à composer dans le langage OCaml, concerne la recherche d’un couplage maximal dans un graphe. On étudiera et implémentera un algorithme dû à Edmonds.

Les parties II et III, à composer dans le langage C, concernent le problème de l’existence d’un couplage parfait dans un graphe. On y implémente des méthodes algébriques et probabilistes basées sur des calculs de déterminants.

La partie II concerne l’implémentation d’un algorithme pour calculer le déterminant d’une matrice carrée dû à Mahajan et Vinay. La partie III exploite cet algorithme pour implémenter un algorithme probabiliste testant l’existence d’un couplage parfait dans un graphe non orienté.

Les parties I et II sont indépendantes. La partie III dépend de la partie II et de notions introduites en partie I. Graphes non orientés. On travaillera dans les parties I et III sur des graphes non orientés et sans boucles.

Un tel graphe G est défini par une paire d’ensembles finis (V,E), où V est l’ensemble des sommets du graphe et E l’ensemble de ses arêtes. Une arête est une paire non-ordonnée {\{u,v\}} d’exactement deux sommets {u,v\in V}.

Ainsi, les arêtes sont non orientées ({\{u,v\}=\{v,u\}}) et il n’y a pas de boucles ({\{v\}=\{v,v\}} n’est jamais une arête de G). Une arête {\{u,v\}} est dite incidente aux sommets u et v. On supposera toujours que V est non vide.

Étant donné un graphe G = (V,E) :

— Un chemin est une suite finie de sommets {v_0,v_1,\ldots,v_n} avec {n\geq0} et telle que pour tout {i=0,\ldots,n-1}, on a {\{v_i,v_{i+1}\}\in E}.

La longueur du chemin {v_0,v_1,\ldots,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,\ldots,v_n} de longueur {\geq3}, avec {v_0=v_n} et tel que le chemin {v_1,\ldots,v_n} est élémentaire.

Autrement dit, le seul sommet autorisé à apparaître plusieurs fois dans un cycle {v_0,v_1,\ldots,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

Cette partie concerne l’algorithme d’Edmonds pour la recherche de couplage maximal.

Question 1. Écrire une fonction del: 'a list -> 'a list -> 'a list qui prend en entrée deux listes lst1 et lst2 et renvoie la liste des éléments de lst1 n’apparaissant pas dans lst2.

On attend une complexité en {O(m_{1}m_{2})} où {m_{1}} est la longueur de lst1 et {m_{2}} est la longueur de lst2, sans la justifier.

On suppose définie une fonction join: 'a list -> 'a list -> 'a list telle que join lst1 lst2 est une liste sans répétitions contenant l’ensemble de tous les éléments apparaissant dans lst1 et de tous les éléments apparaissant dans lst2.

Nous utilisons des listes d’association pour représenter les graphes. Les listes d’association implémentent une structure de dictionnaire ; il s’agit de listes de paires (a,b), dont le premier élément a représente la clef et le second élément b représente la valeur associée à cette clef.

Il existe des fonctions OCaml permettant de travailler avec les listes d’association.

Dans la suite, nous utiliserons seulement la fonction List.assoc: ‘a -> (‘a * ‘b) list -> ‘b qui prend en arguments une clef x et une liste d’association lst, et renvoie la valeur b associée à cette clef, c’est-à-dire l’élément b du premier couple (x,b) appartenant à lst, s’il en existe.

La fonction lève une exception si x n’est pas une clef de la liste lst. La complexité est en O(n), où n est la longueur de lst.

Question 2. Écrire une fonction keys: ('a * 'b) list -> 'a list qui prend en entrée une liste d’association lst et qui renvoie la liste de ses clefs. On attend une complexité en O(m) où m est la longueur de lst, sans la justifier.

Nous représentons les graphes en utilisant le type OCaml suivant :

Un graphe est représenté par une liste de paires (a,lst) où a est un sommet du graphe et lst est la liste d’adjacence de ce sommet.

Dans la suite, on suppose toujours que :

  • les sommets du graphe sont exactement les clefs de la liste d’association ;

  • chaque clé de la liste d’association est unique. Par exemple, le graphe
    Graphe de sommets 0, 2 et 4

    peut être représenté par la liste d’association [(0,[2;4]);(4,[0]);(2,[0])].

Couplages Un couplage C dans un graphe G est un ensemble (possiblement vide) d’arêtes de G sans intersections : un sommet de G ne peut appartenir à plus d’une arête dans C.

Considérons par exemple le graphe :

Exemple de graphe pour les couplages

Les ensembles d’arêtes suivants sont des couplages dans ce graphe : {\begin{array}{c}\{\{0,3\},\{1,8\}\}\\[4pt]\{\{0,1\},\{8,9\}\}\\[4pt]\{\{0,1\},\{5,8\},\{3,9\}\}\end{array}} 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 :

Trois couplages du même graphe

Question 3. On considère le graphe suivant :

Graphe de la question 3

Indiquer lesquels des ensembles suivants sont des couplages dans le graphe ci-dessus : (1) {\{\{1,2\},\{0,5\}\}}, (2) {\{\{1,3\},\{0,5\}\}}, (3) {\{\{0,1\},\{2,3\},\{0,5\}\}}.

Pour voir la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez :