Algorithme d'Edmonds pour les couplages
# Algorithme d'Edmonds pour les couplages

En informatique, plus précisément en théorie des graphes, l'algorithme d'Edmonds pour les couplages (blossom algorithm en anglais), aussi connu sous le nom d'algorithme des fleurs et des pétales est un algorithme pour construire des couplages maximaux sur les graphes. L'algorithme a été développé par Jack Edmonds en 1961, et publié en 1965. Étant donné un graphe quelconque G = (V, E), l'algorithme trouve un couplage M tel que chaque sommet de V est incident à au plus une arête dans E et M est de cardinal maximal. Le couplage est construit en améliorant itérativement un couplage vide initial le long de chemins augmentant dans le graphe. Contrairement au couplage biparti, ce couplage se base sur l'idée qu'un cycle de longueur impaire dans le graphe (fleur) est contracté en un seul sommet, la recherche se poursuivant de manière itérative dans le graphe contracté.

L'algorithme a une complexité temporelle en $O(|E||V|^{2})$, où $|E|$ est le nombre d'arêtes du graphe et $|V|$ est son nombre de sommets. L'algorithme de Micali et Vazirani permet de résoudre le même problème en $O(|E||V|^{1/2})$, cependant il est beaucoup plus compliqué.

Le blossom algorithm est historiquement important car il a donné la première preuve qu'un couplage maximal pouvait être trouvé en un temps polynomial, ce qui prouve que le problème de couplage maximal est dans la classe de complexité P.

## Chemins augmentant

Étant donné G = (V, E) et un couplage M de G, un sommet v est couplé, apparié, ou couvert par M s'il existe une arête de M incidente à v.

Un chemin en G est un chemin alternant, s'il passe alternativement par des arêtes de M et des arêtes de E \ M.

Un chemin augmentant P est un chemin alternant qui commence et se termine par deux sommets non couverts par M distincts. Notez que le nombre d'arêtes de E \ M dans un chemin augmentant est supérieur de un au nombre d'arêtes de M, et par conséquent, le nombre total d'arêtes dans un chemin augmentant est impair.

Une augmentation de couplage le long d'un chemin augmentant P est l'opération consistant à remplacer M par un nouveau couplage ?$M_{1}=M\oplus P=(M\setminus P)\cup (P\setminus M)$ .

D'après le lemme de Berge, le couplage M est maximal si et seulement s'il n'y a pas de chemin augmentant de M dans $G.^,$ Par conséquent, soit un couplage est maximal, soit il peut être augmenté. Ainsi, à partir d'un couplage initial, nous pouvons calculer un couplage maximal en augmentant le couplage actuel avec des chemins augmentant tant que nous pouvons en trouver, et renvoyer le résultat obtenu s'il ne reste plus de chemins augmentant. Nous pouvons formaliser l'algorithme comme suit :

Nous devons encore décrire comment trouver efficacement des chemins augmentant. Le sous-programme qui réalise cette tâche utilise des fleurs et des contractions.

## Fleurs et contractions

Étant donné un graphe G = (V, E) et un couplage M de G, une fleur B est un cycle dans G constitué de 2k + 1 arêtes dont exactement k appartiennent à M. En outre, une fleur comporte un sommet v (sa base) tel qu'il existe un chemin alternant de longueur paire (la tige ) de v à un sommet w non couvert par M.

Trouver des fleurs:

* Parcourez le graphe à partir d'un sommet non couvert par M.
* Étiquetez ce sommet comme un sommet externe "e".
* En commençant par ce sommet, alternez l'étiquetage entre les sommets intérieurs "i" et extérieurs "e" de sorte qu'aucun sommet adjacent ne possède le même libellé.
* Si nous nous retrouvons avec deux sommets adjacents étiquetés comme "e" externes, alors nous avons un cycle de longueur impaire et donc une fleur.

Définissons le graphe contracté' G' comme le graphe obtenu à partir de G en contractant chaque arête de B, et définissons le couplage contracté M' comme le couplage de G correspondant à M, c'est-à-dire le couplage obtenu en retirant à M toutes les arêtes de B.

Montrons que G' a un chemin augmentant de M' si et seulement si G a un chemin augmentant de M, et que tout chemin augmentant P' de M dans G peut être étendu en un chemin augmentant de M dans G.

Le chemin étendu est obtenu en annulant la contraction par B du graphe G, et en intercalant dans P' les arêtes qui doivent l'être.

* Si P' traverse un chemin u → $v_B$ → w dans G', alors ce chemin est remplacé par le chemin u → (u'→ ... → w') → w dans G, où les sommets u' et w' de la fleur ainsi que le chemin (u'→ ... → w') dans B sont choisis pour s'assurer que le nouveau chemin est toujours alternant (u' n'est pas couvert par $M\cap B$, $\{w',w\}\in E\setminus M$ ).
* si P ' a une extrémité $v_B,$ alors le chemin u → $v_B$ dans G' est remplacé par le segment u → (u '→ ... → v') dans G, où les sommets u' et v' de la fleur ainsi que le chemin (u'→ ... → v') dans B sont choisis pour s'assurer que le nouveau chemin est toujours alternant (v' n'est pas couvert par M,$\{u',u\}\in E\setminus M$ $\{u',u\}\in E\setminus M$$\{u',u\}\in E\setminus M$$\{u',u\}\in E\setminus M$).

Ainsi, la recherche peut être effectuée à partir du graphe obtenu en contractant les fleurs. Cette réduction est au cœur de l'algorithme d'Edmonds.

## Trouver un chemin augmentant

La recherche d'un chemin augmentant utilise une structure de données auxiliaire constituée d'une forêt F dont les arbres correspondent à des portions spécifiques du graphe G. Cette forêt F est la même que celle utilisée pour trouver un couplage maximal dans un graphe biparti (sans avoir besoin de réduire les fleurs). A chaque itération, l'algorithme soit (1) trouve un chemin augmentant, (2) trouve une fleur et s'appelle récursivement sur le graphe contracté correspondant, ou (3) conclut qu'il n'y a pas de chemin augmentant. La structure auxiliaire est construite par la procédure incrémentale décrite ci-dessous.

La procédure de construction considère les sommets v et les arêtes e de G et met à jour F de manière incrémentale si nécessaire. Si v est dans un arbre T de la forêt, nous noterons root(v) la racine de T. Si u et v sont tous les deux dans le même arbre T dans F, nous noterons distance(u, v) la longueur du chemin unique de u à v dans T.

### Exemples

Les quatre figures suivantes illustrent l'exécution de l'algorithme. Les lignes en pointillées indiquent des arêtes qui ne sont actuellement pas présentes dans la forêt.

Tout d'abord, l'algorithme traite une arête hors forêt pour provoquer l'expansion de la forêt actuelle (lignes B10 – B12).

Ensuite, il détecte une fleur et contracte le graphe au niveau de cette fleur (lignes B20 – B21).

Enfin, il localise un chemin augmentant P' dans le graphe contracté (ligne B22) et le ramène au graphe d'origine (ligne B23). Notez qu'il est ici crucial que l'algorithme puisse contracter des fleurs; en effet, il ne peut pas trouver P directement dans le graphe de départ car la ligne B17 de l'algorithme ne considère que des arêtes qui n'appartiennent pas à la forêt et qui relient des sommets à distance paire des racines.

### Analyse

La forêt F construite par la fonction find_augmenting_path est une forêt alternée:

* un arbre T dans G est un arbre alterné par rapport à M, si
   * T contient exactement un sommet r non couvert par M appelé racine de l'arbre
   * chaque sommet à une distance impaire de la racine a exactement deux arêtes incidentes dans T,
   * tous les chemins de r aux feuilles de T sont de longueur paire, leurs arêtes impaires ne sont pas dans M et leurs arêtes paires sont dans M.
* une forêt F dans G est une forêt alternée par rapport à M, si
   * ses composants connexes(?) sont des arbres alternés
   * chaque sommet non couvert par M dans G est une racine d'arbre alterné dans F.

Chaque itération de la boucle commençant à la ligne B09 ajoute un arbre T à F (ligne B10), ou trouve un chemin augmentant (ligne B17), ou trouve une fleur (ligne B20). Il est facile de voir que la complexité temporelle de cet algorithme est en $O(|E||V|^{2})$ .

### Couplage biparti

Lorsque G est biparti, il n'y a pas de cycles impairs dans G. Dans ce cas, aucune fleur n'est jamais trouvée, et on peut simplement supprimer les lignes B20 – B24 de l'algorithme. L'algorithme se réduit ainsi à l'algorithme standard pour construire un couplage maximum dans un graphe biparti où l'on recherche un chemin augmentant par un simple parcours de graphe : c'est par exemple le cas de l'algorithme de Ford-Fulkerson.

### Couplage pondérée

Le problème du couplage maximal peut être généralisé en attribuant des poids aux arêtes dans G et en recherchant un ensemble M qui produit un couplage du poids total maximal (minimal) : c'est le problème de couplage de poids maximal. Ce problème peut être résolu par un algorithme combinatoire qui utilise l'algorithme d'Edmonds non pondéré comme sous-programme. Kolmogorov en fournit une implémentation en C++ efficace.

