Algoritmo di Edmonds: differenze tra le versioni

Versione delle 18:14, 6 feb 2010

Versione attuale delle 12:56, 3 dic 2024

(28 versioni intermedie di 19 utenti non mostrate)

Riga 1:

{{tmp|Algoritmo}}

InNella [[teoria dei grafi]] l''''algoritmo di Edmonds''', chiamato anche '''algoritmo di Chu-Liu-Edmonds''', è utilizzato per determinare, a partire da un dato [[Digrafo (matematica)|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 orientato e tale che 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’insiemedall'insieme degli archi all’insiemeall'insieme dei [[Numero reale|numeri reali]] e ''a'' il nodo che si richiede siaessere 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 un grafografi intermediointermedi ''HG_i = (V^#, A<supsub>#i</supsub>,w)'' che viene man mano modificato. Dopo aver eliminato gli archi entranti nella radice l'algoritmo opera in due fasi, dette rispettivamente di contrazione e di espansione: durante la prima fase si contrae il grafo originario ''G = (V,A,w,a)'' pere eliminaresu glialberi eventuali cicli; durante la seconda fase si espande l’alberointermedi ''HT_j = (V<supsub>#j</supsub>, A*<supsub>#j</supsub>,w,a)'' ottenutoche comevengono risultatoman dellamano prima fase per liberare i nodi dei cicli che erano stati contrattimodificati. Sia durante la contrazione che durante l’espansione avviene la scelta degli archi presenti nella soluzione finale ''T = (V,A*,w)''.

Consideriamo i passi della contrazione:

;passo 1.:Per ogni nodo del grafo in ingresso ''G = (V,A,w,a)'' 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.'''&nbsp;&nbsp;&nbsp;&nbsp; Ulteriori eventuali archi del grafo di partenza che congiungono i nodi del ciclo sono eliminati dall’insieme degli archi.

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

::::::::::''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.'''&nbsp;&nbsp;&nbsp;&nbsp; Si fanno collassare i nodi del ciclo in un super-nodo.

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

;passo 3.:Torniamo al passo 1 e applichiamo la contrazione sul grafo ridotto che abbiamo ottenuto. Quando non ci sono più cicli la contrazione termina.

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'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 ora i passi dell'espansione che accetta in ingresso l’albero ''H = (V^#, A^#,w)'' ottenuto al termine della 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.

Consideriamo la '''fase di contrazione''' che accetta in ingresso il grafo ''G'' = ''(V,A,w,a)'' :

;'''passo 1.''': Per ogni nodo del grafo in ingresso ''G = (V,A,w,a)'' 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 termina la fase di contrazione è terminata e si restituisce l’alberol'albero ''HT₁ = (V<supsub>#1</supsub>, A*<supsub>#1</supsub>,w,a)'' ottenuto.

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

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

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

::::::::::''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.'''&nbsp;&nbsp;&nbsp;&nbsp; Si fanno collassare i nodi del ciclo in un super-nodo.

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

;'''passo 3.''': Torniamo al passo 1 e applichiamo la manovra di contrazione sul grafo ridotto che abbiamo''G_i+1'' ottenuto. Quando non ci sono più cicli la contrazione termina.

Consideriamo ora ila passi dell'''fase di espansione''' che accetta in ingresso l’alberol'albero ''HT₁ = (V<supsub>#1</supsub>, A*<supsub>#1</supsub>,w,a)'' ottenuto al termine della precedente fase di contrazione:

Alla contrazione di ogni ciclo in un supernodo durante la prima fase corrisponde l’espansione del supernodo nel ciclo di partenza durante la seconda fase.

;'''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 la primauna fase C, corrisponde l’espansionel'espansione deldi tale supernodo nel ciclo di partenza durante la seconda fase E.

== Esempio 1 ==

Riga 33 ⟶ 32:

! Immagine !! Descrizione

|-

|

|[[Image:]]

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

|-

|[[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)''.

|}

== Esempio 2 ==

Riga 82:

! Immagine !! Descrizione

|-

|

|[[Image:]]

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

|-

|[[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)''.

|}

== Bibliografia ==

* Y. J. Chu. T. H. Liu: ''On the Shortest Arborescence of a Directed Graph'', Science Sinica, v. 14, (1965), pp. 1396-1400&nbsp;1396–1400.

* J. Edmonds: ''Optimum Branchings'', J. Res. Nat. Bur. Standards, v. 71B, 1967, pp. 233-240&nbsp;233–240.

* [[Robert Tarjan]]: ''Finding Optimum Branchings'', Networks, v.7, 1977, pp.25-35&nbsp;25–35.

* P.M. Camerini, L. Fratta, F. Maffioli: ''A note on finding optimum branching'', Networks, v.9, (1979), pp.309-312&nbsp;309–312.

* Alan Gibbons: ''Algorithmic Graph Theory,'' Cambridge University Press, (1985(), ISBN 0-521-28881-9

* H. N. Gabow, Z. Galil, T. Spencer, R. E. Tarjan: ''Efficient algorithms for finding minimum spanning trees in undirected and directed graphs'', Combinatorica 6 (1986), 109-122.

* Y. Zhang: ''Parallel algorithms for minimal spanning trees of directed graphs'', Int. J. Parallel Program., 3 (June 1990), pp. 109-122&nbsp;109–122

* T. Magnanti, L. Wolsey: ''Handbooks in Operational ResearhResearch and Management Science: Optimal Trees'' (1995) <!--???-->

== Collegamenti esterni ==

*[https://web.archive.org/web/20100109052208/http://www.ce.rit.edu/~sjyeec/dmst.html The Directed Minimum Spanning Tree Problem] Description of the algorithm summarized by Shanchieh Jay Yang, May 2000.

*[http://edmonds-alg.sourceforge.net/ Edmonds's algorithm (edmonds-alg)] - An [[open source]] implementation of Edmonds's algorithm written in [[C++]] and licensed under the [[MIT License]]. This source is using Tarjan's implementation for the dense graph.

*[https://web.archive.org/web/20090511193102/http://edmonds-alg.sourceforgealgowiki.net/wiki/index.php/Edmonds's_algorithm AlgoWiki - Edmonds's algorithm] ( edmonds-alg )]A public- An [[open source]]___domain implementation of Edmonds's algorithm written in [[C++]]Java and(linguaggio licenseddi under the [[MIT Licenseprogrammazione)|Java]]. This source is using Tarjan's implementation for the dense graph.

*[http://algowiki.net/wiki/index.php/Edmonds%27s_algorithm AlgoWiki - Edmonds's algorithm] - A public-___domain implementation of Edmonds's algorithm written in [[Java (programming language)|Java]].

{{portale|informatica|matematica}}

[[Categoria:Teoria dei grafi]]

[[Categoria:TeoriaAlgoritmi deisui grafi|Edmonds]]

[[en:Edmonds's algorithm]]