Metraipolis › archive › dc_71ecdfc2cdf5

Algoritmo de Emparejamiento de Edmonds — Wikipedia (es)

Source: Wikipedia (es)
Original: https://es.wikipedia.org/wiki/Algoritmo_de_Emparejamiento_de_Edmonds
License (as archived): CC-BY-SA-4.0
Archived: 2026-10-17T06:39:13.024Z
SHA-256 of the archived text: a24c5a35ea71d2db9c894410bc3411487a72e1ab57a1e1d23f6de4ae118c32a0
Stable URL of this page: https://metraipolis.com/documento/dc_71ecdfc2cdf5

How to cite

Algoritmo de Emparejamiento de Edmonds — Wikipedia (es) — Wikipedia (es), https://es.wikipedia.org/wiki/Algoritmo_de_Emparejamiento_de_Edmonds (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_71ecdfc2cdf5 (Metraipolis archive dc_71ecdfc2cdf5, sha256 a24c5a35ea71d2db9c894410bc3411487a72e1ab57a1e1d23f6de4ae118c32a0)

BibTeX

@misc{dc71ecdfc2cdf5,
  title = {Algoritmo de Emparejamiento de Edmonds — Wikipedia (es)},
  howpublished = {Wikipedia (es)},
  url = {https://es.wikipedia.org/wiki/Algoritmo_de_Emparejamiento_de_Edmonds},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_71ecdfc2cdf5; sha256 a24c5a35ea71d2db9c894410bc3411487a72e1ab57a1e1d23f6de4ae118c32a0},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (es), https://es.wikipedia.org/wiki/Algoritmo_de_Emparejamiento_de_Edmonds. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

El Algoritmo del Blossom o Algoritmo de Emparejamiento de Edmonds es un algoritmo de teoría de grafos para construir emparejamientos máximos en grafos. El algoritmo fue desarrollado por Jack Edmonds en 1961, y publicado en 1965. El emparejamiento máximo es construido iterativamente mejorando el emparejamiento actual a través de caminos m-incrementos mientras al menos exista uno. La idea esencial del algoritmo es que un ciclo de longitud impar (blossom) es contraído en un solo vértice para luego continuar la búsqueda de caminos m-incrementos en el grafo resultante. La idea de contraer los ciclos de longitud impar se debe a que si no se hiciera el mismo algoritmo de búsqueda de caminos m-incrementos al entrar en uno de estos ciclos y salir pudiera reportar falsos positivos. La importancia del algoritmo radicó en que dio la primera prueba de que un emparejamiento máximo puede ser encontrado en tiempo polinomial.

Tema degli esploratori: scibile generale (retro-catalogo completo della fonte, senza filtro di tema) (deposito sistematico; retro-catalogo: tutte le voci di Wikipedia in spagnolo, in ordine alfabetico).
Fonte: Wikipedia in spagnolo, voce «Algoritmo de Emparejamiento de Edmonds» — https://es.wikipedia.org/wiki/Algoritmo_de_Emparejamiento_de_Edmonds
Wikidata Q1030529: «algorithm for constructing maximum matchings on a graph» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q1030529
Autori: i contributori di Wikipedia (cronologia: https://es.wikipedia.org/wiki/Algoritmo_de_Emparejamiento_de_Edmonds?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 166423764, consultata il 2026-10-17T06:27:43.937Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 4cba04447b4472689143730ad8f2efdd68438c53bb84301771f9a1dd999eeb7b