Metraipolis › archive › dc_be732cdb30ab
Algoritmo di Edmonds — Wikipedia
- Source
- Wikipedia (it)
- Original
- https://it.wikipedia.org/wiki/Algoritmo_di_Edmonds
- License (as archived)
- CC-BY-SA-4.0
- Archived
- 2026-10-07T21:55:11.938Z
- SHA-256 of the archived text
42ee76cc98c702d58c11cc0fef1b85ec74379989d6e992d0cb4cb046032c095a- Stable URL of this page
https://metraipolis.com/documento/dc_be732cdb30ab
How to cite
Algoritmo di Edmonds — Wikipedia — Wikipedia (it), https://it.wikipedia.org/wiki/Algoritmo_di_Edmonds (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_be732cdb30ab (Metraipolis archive dc_be732cdb30ab, sha256 42ee76cc98c702d58c11cc0fef1b85ec74379989d6e992d0cb4cb046032c095a)
BibTeX
@misc{dcbe732cdb30ab,
title = {Algoritmo di Edmonds — Wikipedia},
howpublished = {Wikipedia (it)},
url = {https://it.wikipedia.org/wiki/Algoritmo_di_Edmonds},
note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_be732cdb30ab; sha256 42ee76cc98c702d58c11cc0fef1b85ec74379989d6e992d0cb4cb046032c095a},
year = {2026}
}Archived text
Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (it), https://it.wikipedia.org/wiki/Algoritmo_di_Edmonds. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Nella teoria dei grafi l'algoritmo di Edmonds, chiamato anche algoritmo di Chu-Liu-Edmonds, è utilizzato per determinare, a partire da un dato digrafo pesato e fortemente connesso, un suo sottoalbero orientato di peso minimo e avente assegnata radice. L'algoritmo individua cioè un sottoinsieme degli archi del dato digrafo che costituisca un albero tale che ogni coppia dei nodi presi in considerazione sia connessa attraverso un cammino orientato e tale che il peso totale degli archi individuati risulti minimo. Una prevedibile variante dell'algoritmo ricerca il sottoalbero orientato di peso massimo. Questo algoritmo è stato sviluppato in modo indipendente da Chu e Liu nel 1965 e da Jack Edmonds nel 1967. Edmonds ha fornito una dimostrazione della sua correttezza, piuttosto macchinosa e complessa, utilizzando procedimenti della programmazione lineare. Tema degli esploratori: matematica e informatica teorica (deposito sistematico; ricerca «teoria dei grafi»). Fonte: Wikipedia in italiano, voce «Algoritmo di Edmonds» — https://it.wikipedia.org/wiki/Algoritmo_di_Edmonds Wikidata Q1752324 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q1752324 Autori: i contributori di Wikipedia (cronologia: https://it.wikipedia.org/wiki/Algoritmo_di_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 148424313, consultata il 2026-10-07T21:28:54.302Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 2fbbcfc967d480f6a6b3b9ca670e5474da7e6c60232d9ec91cca6087c24e73a0