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
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.
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.
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 :
|
1 |
type graphe = (int * (int list)) list |
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

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 :

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 :


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\}\}}.
- avoir une souscription active sur mathprepa
- et être connecté au site
- revenir à la page d'accueil
- ou tester la page d'extraits libres
