Algoritmo di Edmonds: differenze tra le versioni

Versione delle 23:22, 6 feb 2010

Versione delle 16:55, 7 feb 2010

Riga 1:

InNella [[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 cammini e 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 prova della sua correttezza utilizzando procedimenti della [[programmazione lineare]]. Si tratta di una dimostrazione piuttosto macchinosa e complessa.

Riga 141:

*[http://algowiki.net/wiki/index.php/Edmonds%27s_algorithm AlgoWiki - Edmonds's algorithm] - A public-___domain implementation of Edmonds's algorithm written in [[Java (programming language)|Java]].

[[Categoria:Teoria dei grafi]]

[[en:Edmonds's algorithm]]

--[[Utente:Daniela Mevi|Daniela Mevi]] ([[Discussioni utente:Daniela Mevi|msg]]) 22:20, 6 feb 2010 (CET)