Algoritmo di Edmonds: differenze tra le versioni

Versione delle 14:14, 15 feb 2015

Versione delle 01:40, 17 dic 2015

Riga 10:

Consideriamo la '''fase di contrazione''' che accetta in ingresso il grafo ''G'' = ''(V,A,w,a)'' :

;'''passo 1.''': Per ogni nodo si seleziona l'arco entrante di peso inferiore. Dal momento che la radice non ha archi entranti, rimangono ''card(V ) - 1'' archi. Se non ci sono cicli la fase di contrazione è terminata e si restituisce l’albero ''T₁ = (V₁, A*₁,w,a)''.

;'''passo 2'''.: Se ci sono cicli si procede a considerarli secondo un ordine qualsiasi:

:::'''a.'''  Ulteriori eventuali archi del grafo di partenza che congiungono i nodi del ciclo sono eliminati dall’insieme degli archi.

Riga 54:

|-

|[[Image:|200px]]

|Seconda manovra di contrazione: passo 2.b

|-

|[[Image:|200px]]

Riga 129:

* [[Robert Tarjan]]: ''Finding Optimum Branchings'', Networks, v.7, 1977, pp. 25–35.

* P.M. Camerini, L. Fratta, F. Maffioli: ''A note on finding optimum branching'', Networks, v.9, (1979), pp. 309–312.

* Alan Gibbons: ''Algorithmic Graph Theory,'' Cambridge University Press, (1985(), ISBN 0-521-28881-9

* 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