Algoritmo di Edmonds: differenze tra le versioni

Versione delle 16:55, 7 feb 2010

Versione delle 11:33, 9 feb 2010

Riga 1:

Nella [[teoria dei grafi]] l''''algoritmo di Edmonds''', chiamato anche '''algoritmo di Chu-Liu-Edmonds''', è utilizzato per determinare, a partire da un dato [[digrafo]] pesato e fortemente connesso, un suo sottoalbero orientato di peso minimo e avente assegnata radice. L'algoritmo individua cioè un sottoinsieme degli archi del dato digrafo che costituisca un albero tale che ogni coppia dei nodi presi in considerazione sia connessa attraverso un camminicammino e il peso totale degli archi individuati risulti minimo. Una prevedibile variante dell'algoritmo ricerca il sottoalbero orientato di peso massimo.

Questo algoritmo è stato sviluppato in modo indipendente da Chu e Liu nel 1965 e da [[Jack Edmonds]] nel 1967. Edmonds ha fornito una prova della sua correttezza utilizzando procedimenti della [[programmazione lineare]]. Si tratta di una dimostrazione piuttosto macchinosa e complessa.

Questo algoritmo è stato sviluppato in modo indipendente da Chu e Liu nel 1965 e da [[Jack Edmonds]] nel 1967. Edmonds ha fornito una provadimostrazione della sua correttezza, piuttosto macchinosa e complessa, utilizzando procedimenti della [[programmazione lineare]]. Si tratta di una dimostrazione piuttosto macchinosa e complessa.

== 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'' &rarr; ''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 ungrafi grafointermedi intermedio''G_i = (V,A_i,w,a)'' e su alberi intermedi ''H_i = (V<supsub>#i</supsub>, AB<supsub>#i</supsub>,w,a)'' che vienevengono man mano modificatomodificati.

All'inizio Dopo avervengono eliminatoeliminati gli archi entranti nella radice ''a'', levidentemente estranei all'algoritmoalbero operarichiesto. inSuccessivamente dueviene eseguita una sequenza di coppie di fasi eseguite alternatamente, dette rispettivamente di contrazione, o fase C, e di espansione, o fase E: durante la primauna fase C si contrae il grafo originarioprecedente ''G_i = (V,A_i,w,a)'' per eliminare glii suoi eventuali cicli; durante la seconda fase E si espande l’albero ''H = (V<supsub>#i</supsub>, A^#,w)'', ottenuto come risultato della primafase faseprecedente, per liberarefar riemergere 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,a)''.

Consideriamo ila '''passigenerica dellafase contrazione'''C 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, abbiamorimangono ''card(V ) - 1'' archi. Se non ci sono cicli terminail laprocedimento è contrazioneterminato e si restituisce l’albero ''H = (V<supsub>#i</supsub>, A^#,w)'' ottenuto.

;'''passo 2'''.: Se ci sono cicli sesi procede a considerarli nesecondo consideraun unoordine qualsiasi:

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

:::'''b.'''&nbsp; 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à:

Riga 17 ⟶ 18:

:::'''c.'''&nbsp; Si fanno collassare i nodi del ciclo in un super-nodo.

:::'''d.'''&nbsp; 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.'''&nbsp; RipetiamoSi ripete questo procedimento per ogni ciclo.

;'''passo 3.''': Torniamo al passo 1 e applichiamo la contrazione sul grafo ridotto ''H = (VG<supsub>#</sup>, A<sup>#i+1</supsub>,w)'' cheottenuto abbiamooperando ottenutosul precedente ciclo.

Consideriamo ora ila generica '''passifase di dell'espansione''' che accetta in ingresso l’albero ''H_i = (V<supsub>#i</supsub>, AB<supsub>#i</supsub>,w,a)'' ottenuto al termine della precedente 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.

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