Algoritmo di Edmonds: differenze tra le versioni

Versione delle 01:40, 17 dic 2015

Versione delle 23:34, 25 gen 2016

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’insiemedall'insieme degli archi all’insiemeall'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’esecuzionel'esecuzione l’algoritmol'algoritmo opera su grafi intermedi ''G_i = (V,A_i,w,a)'' e su alberi intermedi ''T_j = (V_j, A*_j,w,a)'' che vengono man mano modificati.

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_i = (V,A_i,w,a)'' per eliminare i suoi eventuali cicli; durante la fase E si espande l’alberol'albero ''T_j = (V_j, A*_j,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’alberol'albero ''T₁ = (V₁, A*₁,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’insiemedall'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''

Riga 21:

;'''passo 3.''': Torniamo al passo 1 e applichiamo la manovra di contrazione sul grafo ridotto ''G_i+1'' ottenuto.

Consideriamo ora la '''fase di espansione''' che accetta in ingresso l’alberol'albero ''T₁ = (V₁, A*₁,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.

Alla contrazione di ogni ciclo in un supernodo durante una fase C, corrisponde l’espansionel'espansione di tale supernodo nel ciclo di partenza durante la fase E.

== Esempio 1 ==

Riga 33:

|-

|

|Grafo d’ingressod'ingresso ''G = (V,A,w,a)''

|-

|[[Image:|200px]]

Riga 83:

|-

|

|Grafo d’ingressod'ingresso ''G = (V,A,w,a)''

|-

|[[Image:|200px]]