Algoritmo Generico per la creazione di un MST
Da Wikipedia, l'enciclopedia libera.
Indice |
[modifica] Cos'è un MST?
Dato un grafo G=(N,A) connesso e non orientato, il problema (MST), o Minimum Spanning Tree, consiste nel trovare l'albero di copertura del grafo con costo totale degli archi utilizzati minimo.
[modifica] L'algoritmo generico: Greedy MST
[modifica] L'idea dell'algoritmo
Consideriamo un grafo connesso non orientato G=(N,A) pesato. L'algoritmo Greedy MST ad ogni passo mantiene due insiemi di archi, sottoinsiemi di A:
- l'insieme S mantiene i nodi che fanno parte dell'albero di copetura
- l'insieme R mantiene i nodi che non fanno parte dell'albero di copertura
Ovviamente, se S ∪ R = A l'albero è formato da tutti e soli gli archi in S.
Vediamo ora come costruire incrementalmente gli insiemi S e R: utilizzeremo due funzioni, chiamate Inserisci e Cancella.
- Inserisci individuerà un taglio (N', N") del grafo, cioè una suddivisione in due sottoinsiemi dei suoi nodi, tale che non esista nessun arco inserito in S che attraversi il grafo (tale cioè da avere un estremo in N' e uno in N"), poi sceglierà fra gli archi in A che attraversano il grafo quello di costo minore e lo inserirà in S
- Cancella individuerà un ciclo C del grafo del quale nessun arco è stato già inserito in R, e aggiungerà l'arco di costo maggiore all'insieme R.
Si puo' notare che:
- Se in S ci sono (N-1) archi, esso definisce per forza un albero di copertura.
- Se il grafo è connesso, è dimostrato che preso un qualunque taglio ci sarà sempre almeno un arco che lo attraversa
Definiamo quindi l'algoritmo, utilizzando uno pseduo-codice (definisce solo un modello di procedura):
Greedy MST (G, c, AT):
begin
S := ∅;
R := ∅
repeat
Applica_Inserzione() or Applica_Cancellazione();
until S ∪ R = A or |S| = n - 1;
AT := S;
end
Come si puo' vedere, all'inizio i due insiemi sono vuoti: l'algoritmo li "riempie" via via durante l'esecuzione, fino a che i due insiemi uniti non danno l'insieme di nodi dell'arco o non si raggiunge n-1 archi inseriti.
[modifica] Correttezza della procedura
Dimostriamo ora la correttezza della procedura con il seguente lemma:
LM: Se la coppia di insiemi (S,R) è tale per cui esiste in G un albero di copertura di costo minimo T = (N, AT), con S ⊆ AT e R ∩ AT = ∅, allora l'applicazione di una qualsiasi delle operazioni di inserzione o cancellazione produce una nuova coppia (S',R') che gode della stessa proprietà.
Per dimostarlo, analizziamo separatamente l'effetto delle due funzioni:
- Se applichiamo Inserzione, l'operazione selezionerà un taglio (N',N") e un arco (u,v) che lo attraversa. Facciamo finta ora di conoscere un albero T', che sappiamo essere albero di copertura di costo minimo per G (non vale necessariamente T=T', in quanto l'albero di copertura di costo minimo non è unico). Ci sono due possibilità:
- (u.v) appartiene a T': in questo caso, la proprietà è verificata per T = T' in quanto R' = R e S' = S ∪ {(u.v)}
- (u,v) non appartiene a T': in questo caso, esisterà in T' un cammino fra u e v che attraversa il taglio, in quanto i due nodi devono essere connessi. Chiamiamo l'arco del cammino che attraversa il taglio (k,l): avremo che sicuramente ckl ≤ cuv (dove cij è il costo dell'arco (i,j)), perché altrimenti T' non sarebbe di costo minimo: in particolare ckl = cuv, perché se valesse ckl < cuv l'operazione di inserzione non avrebbe selezionato l'arco (u,v)
L'applicazione di Inserzione produce dunque una coppia di insiemi (S,R) che mantiene la proprietà.
- Se applichiamo Cancellazione, l'operazione selezionerà un ciclo C e un arco (u,v)∈ C con costo maggiore o uguale agli altri archi del ciclo. Come sopra, facciamo finta di conoscere T' albero di copertura di costo minimo per G. Ancora due possibilità:
- (u,v) non appartiene a T': in questo caso la proprietà ovviamente si mantiene per T = T'
- (u,v) appartiene a T': se lo togliamo, dividiamo T' in due sottoalberi. Si creerà quindi un taglio del grafo, sicuramente attraversato da un altro nodo (k,l) con ckl ≤ cuv. Per la stessa ragione di prima, abbiamo che ckl = cuv.
Abbiamo quindi visto che l'applicazione di Inserzione o Cancellazione mantiene la proprietà. Ne segue che
TH: L'algoritmo Greedy MST termina fornendo un albero di copertura di costo minimo
Si dimostra banalmente per induzione: all'inizio S = R = ∅, e ovviamente valgono S = ∅ ⊆ AT e R = ∅ ∩ AT = ∅. Nei passi successivi continua a valere la proprietà per il lemma precedente, e l'algoritmo termina sicuramente in quanto ad ogni passo viene aggiunto un arco a S o R e prima o poi si giungerà alla condizione di terminazione S ∪ R = AT.
[modifica] Applicazioni
Sono numerose le implementazioni dell'algoritmo Greedy MST: le due più conosciute sono l'Algoritmo di Kruskal e l'Algoritmo di Prim.
