Algoritmo di Edmonds: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
clean up using AWB |
|||
Riga 8:
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)''.
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<sub>1</sub> = (V<sub>1</sub>, A*<sub>1</sub>,w,a)''.
;'''passo 2'''.: Se ci sono cicli si procede a considerarli secondo un ordine qualsiasi:
| |||