Algoritmo di Edmonds: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
m Bot: spazi attorno alle parentesi |
Funzionalità collegamenti suggeriti: 2 collegamenti inseriti. Etichette: Modifica visuale Modifica da mobile Modifica da web per mobile Attività per i nuovi utenti Suggerito: aggiungi collegamenti |
||
| (2 versioni intermedie di 2 utenti non mostrate) | |||
Riga 5:
== Descrizione ==
L'algoritmo accetta in ingresso un grafo orientato e pesato ''G'' = ''(V,A,w,a)'', dove ''V'' è l'insieme dei nodi, ''A'' l'insieme degli archi, ''w: A'' → ''R<sup>+</sup>'' una funzione dall'insieme degli archi all'insieme dei [[Numero reale|numeri reali]] e ''a'' il nodo che si richiede essere radice dell'albero. In uscita restituisce l'albero orientato di supporto a costo minimo ''T* = (V,A*,w,a)'', dove ''A*'' è un sottoinsieme di ''A'' formato da ''card(V ) - 1'' archi. Durante l'esecuzione l'algoritmo opera su grafi intermedi ''G<sub>i</sub> = (V,A<sub>i</sub>,w,a)'' e su alberi intermedi ''T<sub>j</sub> = (V<sub>j</sub>, A*<sub>j</sub>,w,a)'' che vengono man mano modificati.
All'inizio vengono eliminati gli archi entranti nella radice ''a'', evidentemente estranei all'albero richiesto. Successivamente l'algoritmo opera in due fasi, dette rispettivamente di contrazione, o fase C, e di espansione, o fase E: durante una fase C si contrae il grafo ''G<sub>i</sub> = (V,A<sub>i</sub>,w,a)'' per eliminare i suoi eventuali cicli; durante la fase E si espande l'albero ''T<sub>j</sub> = (V<sub>j</sub>, A*<sub>j</sub>,w,a)'' per far riemergere i nodi dei cicli che erano stati contratti. Sia durante la fase di contrazione che durante la fase di espansione avviene la scelta degli archi presenti nella soluzione finale ''T* = (V,A*,w,a)''.
Riga 15:
:::'''b.''' Tutti gli archi che entrano in uno dei nodi del ciclo vanno rietichettati secondo il seguente criterio: siano ''j'' ed ''i'' rispettivamente un nodo del ciclo e un nodo che non vi appartiene tali che esista l'arco ''(i,j)'' con peso ''w<sub>i,j</sub>''; sia inoltre ''(k,j)'' l'arco del ciclo che termina in ''j'' (avente peso ''w<sub>k,j</sub>''); allora il peso rietichettato associato all'arco ''(i,j)'' sarà:
::::::::''w<sub>i,j</sub>'' = ''w<sub>i,j</sub> - w<sub>k,j</sub>''
:::cioè dal peso di ogni arco entrante nel ciclo si sottrae il peso dell'arco del [[ciclo diretto]] allo stesso nodo in cui entra l'arco che si sta rietichettando.
:::'''c.''' Si fanno collassare i nodi del ciclo in un super-nodo.
:::'''d.''' Tra tutti gli archi rietichettati e paralleli che entrano in un super-nodo si conserva quello di peso inferiore e si eliminano tutti gli altri.
Riga 132:
* H. N. Gabow, Z. Galil, T. Spencer, R. E. Tarjan: ''Efficient algorithms for finding minimum spanning trees in undirected and directed graphs'', Combinatorica 6 (1986), 109-122.
* Y. Zhang: ''Parallel algorithms for minimal spanning trees of directed graphs'', Int. J. Parallel Program., 3 (June 1990), pp. 109–122
* T. Magnanti, L. Wolsey: ''Handbooks in Operational Research and Management Science: Optimal Trees'' (1995)
== Collegamenti esterni ==
*[https://web.archive.org/web/20100109052208/http://www.ce.rit.edu/~sjyeec/dmst.html The Directed Minimum Spanning Tree Problem] Description of the algorithm summarized by Shanchieh Jay Yang, May 2000.
*[http://edmonds-alg.sourceforge.net/ Edmonds's algorithm (edmonds-alg)] - An [[open source]] implementation of Edmonds's algorithm written in [[C++]] and licensed under the [[MIT License]]. This source is using Tarjan's implementation for the dense graph.
*[https://web.archive.org/web/20090511193102/http://algowiki.net/wiki/index.php/Edmonds
{{portale|informatica|matematica}}
| |||