Algoritmo di Edmonds: differenze tra le versioni

Versione delle 10:34, 12 feb 2013

Versione delle 14:14, 15 feb 2015

Riga 1:

{{tmp|Algoritmo}}

Nella [[teoria dei grafi]] l''''algoritmo di Edmonds''', chiamato anche '''algoritmo di Chu-Liu-Edmonds''', è utilizzato per determinare, a partire da un dato [[Digrafo (matematica)|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]].