Metraipolis › archive › dc_faaf324f42d0
Algorithme d'Edmonds pour les couplages — Wikipedia (fr)
- Source
- Wikipedia (fr)
- Original
- https://fr.wikipedia.org/wiki/Algorithme_d%27Edmonds_pour_les_couplages
- License (as archived)
- CC-BY-SA-4.0
- Archived
- 2026-10-07T18:02:51.770Z
- SHA-256 of the archived text
90f06ce8f1cbb6a4013b913c44e2d5459e4545686af10715fbb0f507feca9471- Stable URL of this page
https://metraipolis.com/documento/dc_faaf324f42d0
How to cite
Algorithme d'Edmonds pour les couplages — Wikipedia (fr) — Wikipedia (fr), https://fr.wikipedia.org/wiki/Algorithme_d%27Edmonds_pour_les_couplages (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_faaf324f42d0 (Metraipolis archive dc_faaf324f42d0, sha256 90f06ce8f1cbb6a4013b913c44e2d5459e4545686af10715fbb0f507feca9471)
BibTeX
@misc{dcfaaf324f42d0,
title = {Algorithme d'Edmonds pour les couplages — Wikipedia (fr)},
howpublished = {Wikipedia (fr)},
url = {https://fr.wikipedia.org/wiki/Algorithme_d%27Edmonds_pour_les_couplages},
note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_faaf324f42d0; sha256 90f06ce8f1cbb6a4013b913c44e2d5459e4545686af10715fbb0f507feca9471},
year = {2026}
}Archived text
Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (fr), https://fr.wikipedia.org/wiki/Algorithme_d%27Edmonds_pour_les_couplages. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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 et 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 ) {\displaystyle O(|E||V|^{2})} , où | E | {\displaystyle |E|} est le nombre d'arêtes du graphe et | V | {\displaystyle |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 ) {\displaystyle 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 maximum pouvait être trouvé en un temps polynomial, ce qui prouve que le problème de couplage maximum est dans la classe de complexité P.
Tema degli esploratori: matematica e informatica teorica (deposito sistematico; ricerca «théorie des graphes»).
Fonte: Wikipedia in francese, voce «Algorithme d'Edmonds pour les couplages» — https://fr.wikipedia.org/wiki/Algorithme_d%27Edmonds_pour_les_couplages
Wikidata Q1030529 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q1030529
Autori: i contributori di Wikipedia (cronologia: https://fr.wikipedia.org/wiki/Algorithme_d%27Edmonds_pour_les_couplages?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 234281715, consultata il 2026-10-07T17:35:42.765Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: a305994b471e9f71c771bafa5ac84e23f3c5df30c1125fbc1cd8f10f69d6274f