Algoritmo di Edmonds: differenze tra le versioni

Versione delle 18:28, 10 feb 2010

Versione delle 20:28, 10 feb 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 ''HT_ij = (V_ij, BA*_ij,w,a)'' che vengono man mano modificati.

All'inizio vengono eliminati gli archi entranti nella radice ''a'', evidentemente estranei all'albero richiesto. Successivamente vienel'algoritmo eseguitaopera unain sequenza di coppie didue fasi eseguite alternatamente, dette rispettivamente di contrazione, o fase C, e di espansione, o fase E: durante una fase C si contrae il grafo precedente ''G_i = (V,A_i,w,a)'' per eliminare i suoi eventuali cicli; durante la fase E si espande l’albero ''HT_ij ottenuto= come(V_j, risultato della fase precedenteA*_j,w,a)'' per far riemergere i nodi dei cicli che erano stati contratti. Sia durante la fase di contrazione che durante l’espansionela fase di espansione avviene la scelta degli archi presenti nella soluzione finale ''T* = (V,A*,w,a)''.

Consideriamo la generica fase Cdi contrazione che accetta in ingresso il grafo ''G_i'' = ''(V,A_i,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 illa procedimentofase di contrazione è terminatoterminata e si restituisce l’albero ''HT₁ = (V₁, A*_i1,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 19:

:::'''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.'''  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 operando sul precedente ciclo.

Consideriamo ora la generica '''fase di espansione''' che accetta in ingresso l’albero ''HT_i1 = (V_i1, BA*_i1,w,a)'' ottenuto al termine della precedente fase di contrazione:

;'''passo 1.''': Consideriamo un super-nodo e l'arco entrante, l'arco entrante appartiene alla soluzione finale ''T* = (V,A*,w,a)'' 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.

Riga 38 ⟶ 39:

|-

|[[Image:|200px]]

|Prima manovra di contrazione: passo 1

|-

|[[Image:|200px]]

|Prima manovra di contrazione: passo 2.a

|-

|[[Image:Kruskal Algorithm 3.svg|200px]]

|Prima manovra di contrazione: passo 2.b

|-

|[[Image:|200px]]

|Prima manovra di contrazione: passo 2.c

|-

|[[Image:|200px]]

|Seconda manovra di contrazione: passo 1

|-

|[[Image:|200px]]

|Seconda manovra di contrazione: passo 2.a

|-

|[[Image:|200px]]

|Seconda manovra di contrazione: passo 2.b

|-

|[[Image:|200px]]

|Seconda manovra di contrazione: passo 2.c

|-

|[[Image:|200px]]

|Seconda manovra di contrazione: passo 2.d

Fine fase di contrazione

|-

|[[Image:|200px]]

|Prima manovra di espansione: passo 1

|-

|[[Image:|200px]]

|Prima manovra di espansione: passo 2

|-

|[[Image:|200px]]

|Seconda manovra di espansione: passo 2

Fine

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

|}

Riga 87 ⟶ 90:

|-

|[[Image:|200px]]

|Prima manovra di contrazione: passo 1

|-

|[[Image:|200px]]

|Prima manovra di contrazione: passo 2.a

|-

|[[Image:|200px]]

|Prima manovra di contrazione: passo 2.b

|-

|[[Image:|200px]]

|Prima manovra di contrazione: passo 2.c

|-

|[[Image:|200px]]

|Prima manovra di contrazione: passo 2.d

|-

|[[Image:|200px]]

|Seconda manovra di contrazione: passo 1

Gli archi selezionati non formano cicli: abbiamo trovato un albero.

Fine fase di contrazione

|-

|[[Image:|200px]]

|Prima manovra di espansione: passo 1

|-

|[[Image:|200px]]

|Prima manovra di espansione: passo 2

|-

|[[Image:|200px]]

|Seconda manovra di espansione: passo 1

|-

|[[Image:|200px]]

|Seconda manovra di espansione: passo 2

|-

|[[Image:|200px]]

|Fine

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

|}