Alberi di copertura

Posted by On Filed under Algoritmi e strutture dati

Definizioni

Taglio

Un taglio è una suddivisione dell'insieme dei vertici V in due sottoinsiemi tali che V1∈G1 e V2∈G2, inoltre V1∩V2 = ∅ e V1∪V2 = V.

Attraversamento

Un arco E attraversa un taglio se E(u, v) con u∈G1 e v∈G2 cioè se i due vertici appartengono ciascuno a uno dei due insiemi determinati dal taglio.

Rispetto

Dato un sottoinsieme di vertici A ⊆ G si dice che un taglio rispetta l'insieme se nessuno dei suoi archi lo attraversa.

Arco leggero

Si dice leggero l'arco (o gli archi) che, dato un insieme di archi con una proprietà, ha il valore minimo per quella proprietà. Tipicamente si usa chiamare arco leggero quello con valore più basso tra quelli che attraversano un taglio.

Arco sicuro

Dato un grafo G con un taglio (S, V-S), un insieme A che sia rispettato dal taglio, un arco leggero che attraversa (S, V-S) è detto sicuro.

MST

Sta per Minimum Spanning Tree, o albero di copertura minimo. Rappresenta l'albero i cui archi sono quelli meno pesanti possibile.

Teorema fondamentale dei MTS

SIa G = (V, E) un grafo non orientato e connesso e sia w: E → R. Siano inoltre date le seguenti ipotesi:

  • A è un insieme di archi tale che A ⊆ E e che A ⊆ MST (che chiameremo T)
  • sia (S, V\S) un taglio che rispetta A, ovvero il taglio non attraversa alcun arco di A o viceversa;
  • sia (u,v) ∈ E, tale che sia leggero e che attraversa il taglio (S, V\S), ovvero che sia quello di peso minimo tra gli archi che attraversano il taglio

Allora l'arco (u,v) è sicuro per A.

Kruskal

L'algoritmo di Kruskal crea tanti alberi quanti sono i vertici, poi li unisce se non fanno parte della stessa foresta. L'unione avviene ordinando gli archi per peso dal più piccolo, così quando (se) avviene l'unione si memorizza l'arco sicuro di volta in volta.

  1. A = ∅; inizializza un insieme vuoto
  2. for each v in V, MAKE_SET(v); per ogni vertice nell'insieme dei vertici crea un albero (qui chiamato set)
  3. for E order by w; ordina gli elementi di E per peso (w = weight)
  4. for each e(u, v) in E
    1. if FIND_SET(u) ≠ FIND_SET(v); se non appartengono allo stesso albero
      1. A ← A ∪ {(u,v)}; si aggiunge l'arco all'insieme degli archi
      2. UNION(u, v); ora u e v fanno parte dello stesso albero
    2. ; se u e v appartengono allo stesso set non fa niente, perché appartengono già allo stesso albero

Domande

L'algoritmo converge? Sì, perché è composto solo da due cicli for, che per definizione convergono.

L'algoritmo è corretto? Sì, perché rispecchia quello che prescrive il teorema master degli MST.

Qual è la complessità dell'algoritmo?

1: O(1)

2: Θ(v) // inizializzazione

3: O(a log a) // ordinamento

4: O(a) // ciclo for

4.1: O(log a) // find set

4.2: O(1) // union

O(1) + O(v) + O(a log a) + O(a log a) + O(1) ⇒ O(a log a), dato che a domina su n e 1 è costante

Prim

L'algoritmo di Prim utilizza due strutture dati aggiuntive: per ogni vertice aggiunge un'informazione sul vertice "padre" π(v) e inserisce ogni vertice in un min-heap binario.

Inizializza tutti i vertici in modo che il loro peso sia ∞ e che i padri siano tutti NIL.
Poi estrae il vertice "root" e assegna 0 come peso.

A questo punto il vertice root non è più presente nell'heap (l'estrazione da un heap binario ha costo di Θ(n)).
A ogni vertice adiacente viene assegnato un peso pari all'arco che lo congiunge al nodo corrente, a meno che il vertice non abbia già un peso e che questo sia minore dell'arco.
Si estrae dall'heap l'elemento minore o - a parità di peso - uno a caso tra gli elementi minori.
Potrebbe succedere che lo stesso vertice sia visitato più volte, e che in una visita successiva l'arco abbia un peso minore di quello già attribuito al vertice. In questo caso, il vertice "cambia di padre" e gli viene assegnato il nuovo peso.
L'algoritmo di Prim è quindi

  1. Q ← V(G) // assegno all'heap i vertici di G
  2. foreach u ∈ Q, key(u) = ∞
  3. key(r) = 0