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ù est le nombre d'arêtes du graphe et est son nombre de sommets. L'algorithme de Micali et Vazirani permet de résoudre le même problème en , 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. É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 ? .