Algoritmo di Edmonds: differenze tra le versioni

Versione delle 18:36, 6 feb 2010

Versione delle 22:56, 6 feb 2010

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⁺'' una funzione dall’insieme degli archi all’insieme dei numeri reali e ''a'' il nodo che si richiede siaessere radice dell'albero. In uscita restituisce l'albero orientato di supporto a costo minimo ''T = (V,A*,w)'', dove ''A*'' è un sottoinsieme di ''A'' formato da ''card(V ) - 1'' archi. Durante l’esecuzione l’algoritmo opera su un grafo intermedio ''H = (V^#, A^#,w)'' che viene man mano modificato. Dopo aver eliminato gli archi entranti nella radice ''a'' l'algoritmo opera in due fasi, dette rispettivamente di contrazione e di espansione: durante la prima fase si contrae il grafo originario ''G = (V,A,w,a)'' per eliminare gli eventuali cicli; durante la seconda fase si espande l’albero ''H = (V^#, A^#,w)'', ottenuto come risultato della prima fase, per liberare i nodi dei cicli che erano stati contratti. Sia durante la contrazione che durante l’espansione avviene la scelta degli archi presenti nella soluzione finale ''T = (V,A*,w)''.

Consideriamo i '''passi della contrazione''' che accetta in ingresso il grafo ''G = (V,A,w,a)'' :

;'''passo 1.''':Per ogni nodo del grafo in ingresso ''G = (V,A,w,a)'' si seleziona l'arco entrante di peso inferiore. Dal momento che la radice non ha archi entranti abbiamo ''card(V ) - 1'' archi. Se non ci sono cicli termina la contrazione e si restituisce l’albero ''H = (V^#, A^#,w)'' ottenuto.

;'''passo 2'''.:Se ci sono cicli se ne considera uno qualsiasi:

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

:::'''ba.'''    Ulteriori eventuali archi del grafo di partenza che congiungono i nodi del ciclo sono eliminati dall’insieme degli archi.
:::'''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_i,j''; sia inoltre ''(k,j)'' l'arco del ciclo che termina in ''j'' (avente peso ''w_k,j''); allora il peso rietichettato associato all'arco ''(i,j)'' sarà:

::::::::::''w_i,j'' = ''w_i,j - w_k,j''

:::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.

:::'''e.'''     Ripetiamo questo procedimento per ogni ciclo.

;'''passo 3.''':Torniamo al passo 1 e applichiamo la contrazione sul grafo ridotto che''H abbiamo= ottenuto.(V^#, QuandoA^#,w)'' nonche ciabbiamo sono più cicli la contrazione terminaottenuto.

Consideriamo ora i '''passi dell'espansione''' che accetta in ingresso l’albero ''H = (V^#, A^#,w)'' ottenuto al termine della contrazione:

;'''passo 1.''':Consideriamo un super-nodo e l'arco entrante, l'arco entrante appartiene alla soluzione finale ''T = (V,A*,w)'' e viene etichettato come era in origine.

;'''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.