Algoritmo di Edmonds: differenze tra le versioni

Versione delle 23:06, 6 feb 2010

Versione delle 23:20, 6 feb 2010

Riga 11:

;'''passo 1.''':Per ogni nodo 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.

:::'''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 ''H = (V^#, A^#,w)'' che abbiamo ottenuto.

Riga 147:

[[en:Edmonds's algorithm]]

--[[Utente:Daniela Mevi|Daniela Mevi]] ([[Discussioni utente:Daniela Mevi|msg]]) 22:0620, 6 feb 2010 (CET)