Algoritmo di Edmonds: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
Nessun oggetto della modifica |
Funzionalità collegamenti suggeriti: 2 collegamenti inseriti. Etichette: Modifica visuale Modifica da mobile Modifica da web per mobile Attività per i nuovi utenti Suggerito: aggiungi collegamenti |
||
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<sup>+</sup>'' una funzione dall'insieme degli archi all'insieme dei [[Numero reale|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<sub>i</sub> = (V,A<sub>i</sub>,w,a)'' e su alberi intermedi ''T<sub>j</sub> = (V<sub>j</sub>, A*<sub>j</sub>,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<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)''.
Riga 15:
:::'''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<sub>i,j</sub>''; sia inoltre ''(k,j)'' l'arco del ciclo che termina in ''j'' (avente peso ''w<sub>k,j</sub>''); allora il peso rietichettato associato all'arco ''(i,j)'' sarà:
::::::::''w<sub>i,j</sub>'' = ''w<sub>i,j</sub> - w<sub>k,j</sub>''
:::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.
| |||