Per prima cosa diamo la definizione di grafo.
Definizione 13 Un grafo G ´e costituito da una coppia di insiemi (V, A) dove V ´e detto insieme dei nodi e A ´e detto insieme di archi ed ´e un sottinsieme di tutte le possibili coppie di nodi in V . Se le coppie di nodi sono ordinate, il grafo ´e detto orientato, se non sono ordinate ´e detto non orientato.
Esempio 18 Consideriamo un grafo G con insieme di nodi V ={a, b, c, d, e},
mentre l’insieme di archi ´e il seguente sottinsieme di coppie di nodi in V A ={(a, b); (a, c); (b, c); (b, e); (c, d); (d, b)}
Se tali coppie sono ordinate (e quindi, ad esempio, la coppia (a, b) ´e diversa dalla coppia (b, a)) il grafo ´e orientato, altrimenti (e quindi, ad esempio, la coppia (a, b) e la coppia (b, a) sono equivalenti tra loro) il grafo ´e non orientato.
Diamo ora un’altra definizione.
Definizione 14 Dato un grafo orientato G = (V, A) e un arco (i, j)∈ A diremo che il nodo i ´e predecessore del nodo j e che il nodo j ´e successore del nodo i. Nel caso di un grafo non orientato G = (V, A), dato un arco (i, j)∈ A diremo che il nodo i e il nodo j sono tra loro adiacenti.
Nel grafo dell’esempio, supposto orientato, il nodo a ´e predecessore del nodo b, mentre b ´e successore di a. Se il grafo fosse non orientato diremmo
semplicemente che i nodi a e b sono adiacenti. Abbiamo definito un grafo G attraverso la coppia di insiemi V e A. ´E possibile per´o rappresentare un grafo anche nei modi seguenti.
Rappresentazione grafica Ad ogni nodo corrisponde un pallino sul pia-no e ogni arco (i, j) corrisponde ad una linea che congiunge il pallipia-no che rappresenta il nodo i con il pallino che rappresenta il nodo j. Se il grafo ´e orientato sulla linea si aggiunge anche una freccia da i verso j (per grafi non orientati la freccia si omette). Nella figura sottostante ´e mostrata la rappresentazione grafica del grafo dell’esempio, supposto orientato (nel caso non orientato si devono solo omettere le frecce).
a
b
c d
e
Liste di adiacenza Ad ogni nodo si affianca una lista (eventualmente vuota) contenente tutti i suoi successori nel caso di grafo orientato, o tutti i nodi adiacenti nel caso di grafo non orientato. Per il nostro esempio, supposto orientato, le liste di adiacenza sono le seguenti:
a : (b, c) b : (c, e) c : (d) d : (b) e : ∅
mentre se lo si suppone non orientato le liste di adiacenza sono le seguenti:
a : (b, c) b : (a, c, d, e) c : (a, b, d) d : (b, c) e : (b) Matrice incidenza nodo-arco Si costruisce una matrice con una riga
per ogni nodo e una colonna per ogni arco. Per grafi orientati nella colonna relativa all’arco (i, j) si mette +1 in corrispondenza della riga i, -1 in corrispondenza della riga j e 0 in corrispondenza di tutte le altre righe. Per il nostro esempio, supposto orientato, la matrice di incidenza nodo-arco ´e data in Tabella 7.1 Per grafi non orientati nella colonna relativa all’arco (i, j) si mette +1 in corrispondenza della riga i e della riga j e 0 in corrispondenza di tutte le altre righe. Per il nostro esempio, supposto non orientato, la matrice di incidenza nodo-arco ´e data in Tabella 7.2
Tabella 7.1: (a, b) (a, c) (b, c) (b, e) (c, d) (d, b) a 1 1 0 0 0 0 b -1 0 1 1 0 -1 c 0 -1 -1 0 1 0 d 0 0 0 0 -1 1 e 0 0 0 -1 0 0 Tabella 7.2: (a, b) (a, c) (b, c) (b, e) (c, d) (d, b) a 1 1 0 0 0 0 b 1 0 1 1 0 1 c 0 1 1 0 1 0 d 0 0 0 0 1 1 e 0 0 0 1 0 0
Introduciamo ora alcune definizioni.
Definizione 15 Due archi che hanno un nodo in comune sono detti adia-centi.
Nell’esempio gli archi (a, b) e (a, c) sono adiacenti.
Definizione 16 Sia dato un grafo G = (V, A). Una sequenza di m+1 nodi s0→ s1→ s2→ · · · → sm
tali che per ogni i = 1, . . . , m si ha:
(si−1, si)∈ A oppure (si, si−1)∈ A
(l’alternativa ´e superflua nel caso non orientato) ´e detto cammino nel gra-fo. Il numero m di archi del cammino ´e detto lunghezza del cammino. Possiamo vedere anche un cammino di lunghezza m come una sequenza di archi a due a due adiacenti. Un cammino ´e detto semplice se nessun arco ´e percorso pi´u di una volta, elementare se nessun nodo viene toccato pi´u di una volta.
Nell’esempio, il cammino a → b → d → c ´e un cammino elementare di lunghezza 3; il cammino a → b → c → d → b → e ´e semplice ma non elementare (il nodo b ´e toccato pi´u di una volta); il cammino a→ b → c → d→ b → a → c non ´e n´e semplice n´e elementare (l’arco (a, b) ´e attraversato due volte).
Definizione 17 Un cammino semplice
s0→ s1→ s2→ · · · → sm
in cui primo e ultimo nodo coincidono (cio´e sm = s0) viene detto ciclo di lunghezza m. Se omettendo l’ultimo nodo sm si ottiene un cammino elementare, si parla di ciclo elementare.
Nell’esempio a→ b → c → a ´e un ciclo elementare di lunghezza 3. Definizione 18 In un grafo orientato un cammino o un ciclo
s0→ s1→ s2→ · · · → sm
(sm= s0 nel caso di un ciclo) in cui tutti gli archi sono percorsi secondo il loro orientamento, ovvero si ha che per ogni i = 1, . . . , m:
(si−1, si)∈ A
viene detto orientato, altrimenti si dice non orientato.
Nell’esempio il cammino a → b → c ´e orientato mentre il cammino b → a→ c ´e non orientato. il ciclo a → b → c → a `e non orientato, mentre il ciclo b→ c → d → b `e orientato.
Definizione 19 Dati due nodi i e j di un grafo G, se esiste un cammino da i a j allora si dice che j ´e accessibile da i.
La relazione tra i nodi ”´e accessibile da” ´e una relazione di equivalenza, ov-vero soddisfa le tre propriet´a riflessiva, simmetrica e transitiva. Come tale, induce classi di equivalenza nell’insieme dei nodi. Tali classi di equivalenza vengono dette componenti connesse del grafo. Ogni componente connessa ´e formata da nodi tutti accessibili tra loro ma non accessibili da nodi in altre componenti.
Definizione 20 Se il grafo contiene una sola componente connessa viene detto connesso.
La seguente procedura consente di individuare le componenti connesse di un grafo e quindi anche di stabilire se un grafo ´e connesso.
Inizializzazione Si ponga W = V e r = 1.
Passo 2 Si selezioni un nodo j∈ S. Si rimuova j da S e si aggiungano in S tutti i nodi che non siano gi´a contenuti in Trdi cui j ´e predecessore o successore, cio´e
S = (S\ {j}) ∪ {k 6∈ Tr: (k, j)∈ A o (j, k) ∈ A}. Si ponga Tr= Tr∪ {j}.
Passo 3 Se S = ∅, allora si vada al Passo 4. Se Tr∪ S = W , si ponga Tr= Tr∪ S e si vada al Passo 4. Altrimenti si ritorni al Passo 2. Passo 4 Si ponga W = W\ Tr. Se W =∅, allora T1, T2, . . . , Tr sono gli
insiemi di nodi delle componenti connesse del grafo. Altrimenti si ponga r = r + 1 e si ritorni al Passo 1.
Come esercizio si applichi la procedura per verificare che il grafo dell’esem-pio ´e connesso.
Definizione 21 Un nodo j ´e detto fortemente accessibile da i se esiste un cammino orientato da i a j.
Si noti che la relazione tra nodi ”´e fortemente accessibile da” non ´e una relazione di equivalenza. In particolare non vale per essa la propriet´a di simmetria (nell’esempio e ´e fortemente accessibile da b ma il viceversa non ´e vero).
Definizione 22 Un grafo in cui ogni nodo ´e fortemente accessibile da tutti gli altri ´e detto fortemente connesso.
Si noti che l’esistenza in un grafo di un ciclo orientato che tocca tutti i nodi del grafo garantisce che il grafo sia fortemente connesso. Il grafo del nostro esempio non ´e fortemente connesso (come gi´a osservato b e anche tutti gli altri nodi del grafo non sono fortemente accessibili da e).
Definizione 23 Un grafo si dice completo se esiste un arco tra ogni coppia di nodi distinti.
Il nostro grafo non ´e completo. Ad esempio, non c’´e alcun arco tra a ed e. Lo ´e invece il grafo G = (V, A) con
V ={a, b, c, d} e
Definizione 24 Dato un grafo G = (V, A) e un sottinsieme A′ ⊆ A, un grafo G′ = (V, A′) ´e detto grafo parziale di G. Dati V′′⊆ V e
A′′
⊆ A(V′′) ={(i, j) ∈ A : i ∈ V′′, j∈ V′′
}
il grafo G′′ = (V′′, A′′) viene detto sottografo di G. In particolare, se A′′= A(V′′) il sottografo viene detto sottografo indotto da V′′.
Nell’esempio G′= (V, A′) con
A′={(a, b); (b, c); (b, e); (c, d); (d, b)}
´e un grafo parziale di G, mentre G′′= (V′′, A′′) con V′′={a, b, d} e A′′={(a, b)}
´e un sottografo di G. Se invece si considera G′′ = (V′′, A′′) con V′′ = {a, b, d} e
A′′={(a, b); (d, b)} questo ´e il sottografo di G indotto da V′′.
Definizione 25 Un grafo G = (V, A) si dice bipartito se l’insieme V pu´o essere partizionato in due sottinsieme V1 e V2 (quindi V1∪ V2= V e V1∩ V2=∅) tali che
∀ (i, j) ∈ A : i ∈ V1, j∈ V2 oppure i∈ V2, j∈ V1.
Un grafo bipartito si dice completo se per ogni coppia di nodi in V1 e V2
esiste un arco che li congiunge. Vale la seguente osservazione.
Osservazione 18 Un grafo ´e bipartito se e solo se non contiene cicli di lunghezza dispari.
La seguente procedura consente di stabilire se un grafo ´e bipartito. Passo 0 Si ponga W = V , C1= C2=∅.
Passo 1 Si selezioni un nodo i∈ W e si ponga T1={i}, C1= C1∪ T1. Passo 2 Si ponga
T2={k ∈ V \ C2 : ∃ i ∈ T1 tale che (i, k)∈ A oppure (k, i) ∈ A} Sia C2= C2∪ T2.
Passo 3 Si ponga
T1={k ∈ V \ C1 : ∃ i ∈ T2 tale che (i, k)∈ A oppure (k, i) ∈ A} Sia C1= C1∪ T1.
Passo 4 Se C1∩ C26= ∅, allora il grafo non ´e bipartito. Altrimenti si vada al Passo 5.
Passo 5 Si ponga W = W\ (C1∪ C2). Se W =∅ e T1=∅, allora il grafo ´e bipartito con V1 = C1 e V2 = C2. Altrimenti, se T1 =∅, si ritorni al Passo 1, se T16= ∅ si ritorni al Passo 2.
Nel nostro esempio selezionando inizialmente il nodo a e ponendolo in T1e C1avremo
C1a C2
con T1={a}. Al Passo 2 avremo C1a C2b c
con T2={b, c} e C2={b, c}. Al Passo 3 avremo C1 a e d c
C2b c
con T1={e, d, c, b} e C1={a, e, d, c, b}. Al Passo 4 notiamo che C1∩ C2= {b, c} 6= ∅ e quindi possiamo concludere che il grafo non ´e bipartito. Definizione 26 Sia dato un grafo G = (V, A) con card(V ) = n dove card(V ) denota la cardinalit´a (il numero di elementi) dell’insieme V . Si dice che G ´e un albero se soddisfa le seguenti condizioni (equivalenti tra loro)
1. G ´e privo di cicli e connesso; 2. G ´e privo di cicli e card(A) = n− 1; 3. G ´e connesso e card(A) = n− 1;
4. esiste un unico cammino elementare che congiunge ogni coppia di nodi.
Ad esempio, il grafo G = (V, A) con
V ={a, b, c, d, e} A = {(a, b); (b, c); (c, e); (e, d)} illustrato nella figura sottostante ´e un albero.
a
b
c
d
e
Definizione 27 Sia dato un grafo generico G = (V, A). Si definisce albero di supporto o spanning tree di G un grafo parziale T = (V, AT) di G (quindi con AT ⊆ A) che ´e un albero.
Si noti che un albero di supporto di G deve contenere tutti i nodi di G e che in virt´u del punto 2. (o del punto 3.) della Definizione 26, si dovr´a avere card(AT) = card(V )− 1.
Esempio 19 Sia dato il grafo G = (V, A) con
V ={a, b, c, d} A = {(a, b); (b, c); (b, d); (a, d); (c, d)}
illustrato in Figura 7.1. Un albero di supporto di G ´e il sottografo T1 = (V, AT1) con
AT1 ={(b, c); (b, d); (a, d)} un altro ´e il sottografo T2= (V, AT2) con
AT2={(a, b); (b, c); (c, d)}
I due alberi di supporto di G sono illustrati in Figura 7.1. Vale la seguente osservazione.
Osservazione 19 Dato un albero, l’aggiunta di un solo arco crea esatta-mente un ciclo.
Definiamo ora una funzione
w : A→ R
che ad ogni arco e∈ A del grafo associa un peso w(e) (in Figura 7.1 tale valore ´e riportato sopra ciascun arco). Nel problema dell’albero di supporto
E E E E E E ,,, ,, ,, , Z Z Z Z Z Z Z Z Z Z Z Z Z Z ,, ,, ,, ,, , E E E E E E ## ## ## ## ##£ £ £ £ £ £ £ a b c d a b c d a b d c 3 5 3 2 2 4 4 3 3 4 5 G T1 T2
Figura 7.1: Un grafo G e due suoi alberi di supporto T1 e T2. a peso minimo vogliamo trovare tra tutti i possibili alberi di supporto del grafo G, quello con peso totale minimo, dove il peso di un albero di supporto T = (V, AT) ´e definito dalla somma dei pesi dei suoi archi, ovvero:
X
e∈AT
w(e).
Nella Figura 7.1 i due alberi di supporto hanno pesi rispettivamente pari a 9 e 12. Abbiamo il seguente algoritmo greedy (goloso) per il problema di albero di supporto a peso minimo.
Passo 1 Si ordinino tutti gli m = card(A) archi del grafo in ordine non decrescente rispetto al peso, cio´e
w(e1)≤ w(e2)≤ · · · ≤ w(em−1)≤ w(em).
Si parta con un insieme AT di archi vuoto, cio´e AT =∅. Sia k = 1 Passo 2 Se card(AT) = card(V )− 1 ci si arresta e si restituisce l’albero
Passo 3 Se ek non forma cicli con gli archi in AT, lo si aggiunga ad AT, cio´e si ponga AT = AT ∪ {ek}. Altrimenti si lasci AT invariato. Passo 4 Si ponga k = k + 1 e si ritorni al Passo 2.
Come esercizio si pu´o applicare tale algoritmo all’esempio in Figura 7.1. La strategia greedy appare al Passo 3. Infatti, tra tutti gli archi non ancora considerati si va a considerare quello che tra essi ha peso minimo e lo si aggiunge se non forma cicli con quelli gi´a inseriti in AT. Faccio dunque una scelta greedy che ´e la migliore possibile per la particolare situazione in cui mi trovo (ovvero per il particolare insieme di archi AT che ho gi´a inserito nell’albero). Non sempre questo tipo di scelta ´e opportuna (pu´o accadere che la scelta migliore in un dato momento non lo sia in generale) ma nel caso particolare del problema dell’albero di supporto a peso minimo si pu´o dimostrare che ´e una scelta vincente, cio´e che conduce effetivamente ad individuare un albero di supporto a peso minimo.
Ma l’algoritmo greedy non ´e l’unico possibile per risolvere il problema del-l’albero di supporto a peso minimo. Vogliamo ora proporre un algoritmo alternativo e ”migliore” rispetto a quello greedy, in particolare per grafi densi, ovvero con un numero elevato di archi. Per ”migliore” si intende un algoritmo che richiede in generale un numero di operazioni (e quindi un tempo di esecuzione) inferiore rispetto all’algritmo greedy. L’algoritmo ´e il seguente.
Inizializzazione Fissato un nodo v1∈ V , si ponga U ={v1} AT =∅. Inoltre, per ogni v∈ V \ U si ponga:
ev= ½
(v, v1) se w(v, v1)≤ w(v1, v) (v1, v) altrimenti
Passo 1 Se U = V , allora STOP: l’albero di supporto (V, AT) ´e quello a peso minimo. Altrimenti si consideri un nodo v tale che:
w(ev) = min
v∈V \Uw(ev)
(si noti che nel caso ev 6∈ A il suo peso w(ev) viene considerato pari a +∞).
Passo 2 Si ponga:
Passo 3 Per ogni v∈ V \ U, si lasci invariato ev se w(v, v), w(v, v)≥ w(ev), altrimenti si ponga: ev= ½ (v, v) se w(v, v)≤ w(v, v) (v, v) altrimenti Si ritorni al Passo 1.
Ma vediamo ora di applicare l’algoritmo al nostro esempio. Inizializziamo U con il nodo a. Quindi avremo inizialmente:
U ={a} AT =∅ V \ U = {b, c, d}. Inoltre avremo:
eb= (a, b) ec= (a, c) ed = (a, d).
Non abbiamo U = V , quindi al Passo 1 scegliamo il nodo d in quanto: w(ed) = min{w(eb), w(ec), w(ed)}.
Si noti che avremmo potuto scegliere anche il nodo b in quanto w(eb) = w(ed). Si noti inoltre che, essendo ec = (a, c)6∈ A, avremo w(ec) = +∞. Al Passo 2 avremo:
U ={a, d} AT ={(a, d)} V \ U = {b, c}.
Al Passo 3 abbiamo w(ec) > w(c, d) e quindi avremo il seguente aggiorna-mento:
ec= (c, d);
inoltre, abbiamo w(eb) > w(b, d) e quindi avremo anche il seguente aggior-namento:
eb= (b, d).
A questo punto ritorniamo al Passo 1. Non abbiamo U = V , quindi al Passo 1 scegliamo il nodo b in quanto:
w(eb) = min{w(eb), w(ec)}. Al Passo 2 avremo:
Al Passo 3 abbiamo w(ec) > w(b, c) e quindi avremo il seguente aggiorna-mento:
ec= (b, c).
A questo punto ritorniamo al Passo 1. Non abbiamo U = V , quindi al Passo 1 scegliamo il nodo c in quanto:
w(ec) = min{w(ec)}. Al Passo 2 avremo:
U ={a, b, c, d} AT ={(a, d); (b, d); (b, c)} V \ U = ∅.
Al Passo 3 non abbiamo aggiornamenti da eseguire e possiamo ritornare al Passo 1. Ora si ha U = V e quindi l’albero di supporto (V, AT) con:
AT ={(a, d); (b, d); (b, c)} ´e quello a peso minimo (con peso pari a 9).