Algoritmo di Edmonds: differenze tra le versioni

Versione delle 20:28, 10 feb 2010

Versione delle 18:17, 5 lug 2010

Riga 4:

== 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⁺'' una funzione dall’insieme degli archi all’insieme dei 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_i = (V,A_i,w,a)'' e su alberi intermedi ''T_j = (V_j, A*_j,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_i = (V,A_i,w,a)'' per eliminare i suoi eventuali cicli; durante la fase E si espande l’albero ''T_j = (V_j, A*_j,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)''.

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

Riga 20 ⟶ 19:

:::'''e.'''  Si ripete questo procedimento per ogni ciclo.

;'''passo 3.''': Torniamo al passo 1 e applichiamo la manovra di contrazione sul grafo ridotto ''G_i+1'' ottenuto.

Consideriamo ora la '''fase di espansione''' che accetta in ingresso l’albero ''T₁ = (V₁, A*₁,w,a)'' ottenuto al termine della precedente fase di contrazione:

Riga 26 ⟶ 24:

;'''passo 2.''': Il super-nodo viene espanso nei nodi originali e tra gli archi del ciclo bisogna eliminarne uno; tra i nodi del ciclo uno ha due archi entranti: l'arco appena aggiunto alla soluzione e l'arco del ciclo, quest'ultimo viene eliminato, gli altri archi del ciclo vengono aggiunti alla soluzione.

;'''passo 3.''': Si torna al passo 1 finché abbiamo espanso tutti i super-nodi.

Alla contrazione di ogni ciclo in un supernodo durante una fase C, corrisponde l’espansione di tale supernodo nel ciclo di partenza durante la fase E.

== Esempio 1 ==

Riga 35 ⟶ 31:

! Immagine !! Descrizione

|-

|

|[[Image:]]

|Grafo d’ingresso ''G = (V,A,w,a)''

|-

Riga 80 ⟶ 76:

Si ottiene ''T* = (V,A*,w,a)''.

|}

== Esempio 2 ==

Riga 86 ⟶ 81:

! Immagine !! Descrizione

|-

|

|[[Image:]]

|Grafo d’ingresso ''G = (V,A,w,a)''

|-

Riga 129 ⟶ 124:

== Bibliografia ==

* Y. J. Chu. T. H. Liu: ''On the Shortest Arborescence of a Directed Graph'', Science Sinica, v. 14, (1965), pp. 1396-1400 1396–1400.

* J. Edmonds: ''Optimum Branchings'', J. Res. Nat. Bur. Standards, v. 71B, 1967, pp. 233-240 233–240.

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

* P.M. Camerini, L. Fratta, F. Maffioli: ''A note on finding optimum branching'', Networks, v.9, (1979), pp.309-312 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 109–122

* T. Magnanti, L. Wolsey: ''Handbooks in Operational Researh and Management Science: Optimal Trees (1995) <!--???-->

== Collegamenti esterni ==

*[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.

*[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]].