Grafo

Grafo

Grafo

Un grafo G è una coppia di elementi G = (V, E) dove

V è un insieme finito di vertici
E è un insieme finito di coppie di vertici, detto insieme degli archi

Un arco è una coppia (v, u) di vertici in V

Tipi di grafi

grafo orientato G
È una coppia (V, E) dove:

V è l'insieme finito dei vertici
E è una relazione binaria tra vertici su V

grafo non orientato G
È una coppia (V, E) dove:

V è l'insieme finito dei vertici
E è un insieme di coppie non ordinate di vertici, detto insieme degli archi.

In un grafo orientato, un arco (u, v) si dice incidente da u a v
Un vertice u si dice adiacente a v <=> (u, v) appartiene a E
In un grafo non orientato la relazione di adiacenza tra vertici è simmetrica

Grado di un vertice

grafo non orientato G
Il grado di un vertice è il numero di archi che da esso si dipartono.
grafo orientato G
Il grado entrante (uscente) di un vertice è il numero di archi incidenti in (uscenti da) esso.
Il grado di un vertice per un grafo orientato è la somma del suo grado entrante e del suo grado uscente

Cammino e cicli

Il cammino (o percorso) da un vertice v₀ ad un vertice v_k in un grafo G = (V, E) è una sequenza di vertici (v₀, v₁, ..., v_k) tale che (v_i, v_i+1) appartiene E per 0 <= i <= k-1. k è la lunghezza del cammino.
Se esiste un cammino da v₀ a v_k si dice che v_k è raggiungibile da v₀.
Un cammino si dice semplice se tutti i suoi vertici sono distinti (eccetto al più il primo e l'ultimo che possono coincidere).
Un ciclo in un grafo è un cammino (v₀, v₁, ..., v_k) di lunghezza almeno 1, tale che v₀ = v_k. Se la lunghezza è 1, è detto cappio.
Un grafo senza cicli è detto aciclico.

Connessione in un grafo

Un grafo non orientato è connesso se per ogni coppia di vertici esiste un cammino che li collega.
Un grafo orientato è fortemente connesso se per ogni coppia ordinata di vertici (u, v) esiste un cammino che collega v a u.
Un grafo orientato è debolmente connesso se il grafo non orientato sottostante (cioè senza la direzione degli archi) è connesso.
I grafi connessi di dimensione massima si dicono componenti connesse.
Un grafo connesso è composto da una sola componente connessa.
Un grafo non orientato aciclico e connesso è detto albero.¹
Un grafo non orientato aciclico non connesso è detto foresta.

Grafo completo e densità

Un grafo si dice completo se ha un arco tra ogni coppia di vertici (data una qualsiasi coppia di vertici, questi sono adiacenti).
In un grafo completo composto da n vertici, il numero di archi è pari a:

n(n-1) se il grafo è orientato
n(n-1)/2 se il grafo è non orientato

La densità di un grafo è il rapporto tra il numero di archi |E| ed il numero totale di possibili archi.

Grafi pesati

Nei grafi pesati ad ogni arco è associato un peso (o costo).
Il costo può essere rappresentato da una funzione di costo w: E --> R
Quando tra due vertici non esiste un arco, si dice che il costo è infinito.

Tipi di rappresentazione standard per grafi

a. rappresentazione a matrice di adiacenza.

| 1 se (u,v) appartiene E
M(u,v) = <
| 0 altrimenti

Nel caso di grafi non orientati la matrice è simmetrica.
Nel caso di grafi pesati l'elemento m_v,u qualora non sia nullo assumo il valore del peso dell'arco.
Spazio richiesto: O( |V|² )
Verificare se i vertici u, v sono adiacenti richiede tempo O( 1 )
Molti zero nel caso di grafi sparsi (poso densi)

b. rappresentazione a lista di adiacenza

L(v) = lista di u, tale che (u,v) appartiene E per v appartente V

Algoritmi di visita

L'operazione corrispondente ad esplorare un grafo a partire da un vertice dato (sorgente) toccando tutti i vertici da questo raggiungibili si definisce visita.
Esistono due tipo di visita:

Visita in ampiezza: Breadth-First-Search
Consiste nel visitare i vertici del grafo per livelli.
Visita in profondità: Depth-First-Search
Ad ogni passo i si visita un vertice adiacente all'ultimo vertici visitato esplorando il grafo in profondità. Quando non ne esistono, si torna indietro all'ultimo vertice visitato che abbia vertici adiacenti non visitati, e li si visita.

BFS: Visita in ampiezza

Consiste nel visitare i vertici del grafo per livelli.
Viene normalmente implementata utilizzando una coda FIFO.

un vertice è stato visitato se è apparso nella coda: gray
un vertice non è stato visitato se non è ancora stato visitato: white
un vertice è stato processato se tutti i vertici ad esso adiacenti sono stati visitati: black

L'algoritmo BFS eseguito su un grafo G = (V, E) costruisce nell'array pred[] il sottografo dei predecessori.
Cammini minimi: dati due vertici s e v in un grafo non pesato, il numero minimo di archi su un cammino da s a v si definisce distanza sul cammini minimo. L'algoritmo BFS calcola le distanze sul cammini minimo per ogni vertice v di V (rispetto ad un vertice sorgente).

BFS(G, s)

for each vertice u appartente V[G] -{s}
    color[u] <-- White
    path[u] <-- Inf
    pred[u] <-- NULL
color[s] <-- Gray
path[s] <-- 0
pred[s] <-- NULL
ENQUEUE(Q, s)

while ( Q != vuota )
    u <-- DESQUEUE(Q)

    for each vertice v adiacente a u
        if ( color[v] == White )
                color[v] <-- Gray
                path[v] <-- path[u] +1
                pred[v] <-- u
                ENQUEUE(Q, v)

    color[u] <-- Black

Inizializzazione        O( |V| )

Per ogni vertice, si tenta di passare sui suoi archi, complessivamente quindi   O( |E| )

Complessità totale: O( |V| + |E| )

DFS: Visita in profondità

Ad ogni passo i si visita un vertice adiacente all'ultimo vertici visitato esplorando il grafo in profondità. Quando non ne esistono, si torna indietro all'ultimo vertice visitato che abbia vertici adiacenti non visitati, e li si visita.
Viene normalmente implementata tramite una procedura ricorsiva.

Il grafo è connesso <==> una chiamata di DFS raggiunge tutti i vertici (se al termine della DFS c'è più di un vertice u con pred[u] = NULL il grafo non può essere connesso, equivalentemente si guarda lo stato di visitato)

DFS(G)



for each vertice u appartente V[G]

    color[u] <-- White

    pred[u] <-- NULL
time <-- 0

for each vertice u appartenente V[G]
    if ( color[u] = White )
        DFS-Visit(u)


DFS-Visit(u)

color[u] <-- Gray
path[u] <--time <-- time + 1

for each vertice v adiacente a u
    if ( colour[v] == White )
        pred[v] <-- u
        DFS-Visit(v)

color[u] <-- Black
f[u] <-- time <-- time + 1

Inizializzazione        Theta( |V| )

Theta( |V| )

DFB chiamata V volte, check su ogni vertice adiacente -->  theta ( |E| )

Complessità totale: Theta( |V| + |E| )

Alberi di copertura minimi Minimum Spanning Tree

Sia G = (V, E) un grafo non orientato, connesso e pesato con una funzione peso w: E --> R.
L'albero di copertura minimo (MST) è il grafo G' avente le seguenti proprietà:

è composto dagli stessi vertici di G e da un sottoinsieme T degli archi E (T contenuto E)
è connesso e aciclico
minimizza la quantità w(T) = sum( w(u,v) )
(Minimizzare la lunghezza dei collegamenti da realizzare)

L'albero di copertura minimo per un grafo in generale non è unico.

Gli algoritmi greedy (ingordo) sono algoritmi basati sull'idea di fare sempre scelte che sembrano ottime al momento della scelta.
Non è sempre garantita la correttezza, ma, se lo è, sono in genere molto semplici ed efficienti.

Geniric-MST(G, w)

A <-- Ø
while ( A non forma un albero di copertura )
trova un arco (u,v) che sia sicuro per A
A <-- Union( A, {(u, v)} )

return A

Si definisce sicuro un arco che aggiunto ad un sottoinsieme di arco di copertura minimo produce ancora un sottoinsieme di un albero di copertura minimo.

Dato un grafo non orientato G = (V, E), un taglio è una partizione di V in due sottoinsiemi.
Un arco attraversa il taglio se uno dei suoi estremi è in una partizione e l'altro nell'altra.
Un taglio rispetta un insieme di archi A se nessun arco di A attraversa il taglio.
Un arco si dice leggero se ha preso minimo tra gli archi che attraversano l'arco.

Teorema
Sia G = (V, E) un grafo non orientato, connesso e pesato da una funzione peso w: E --> R.
Sia A un sottoinsieme di archi E contenuto in uno degli alberi di copertura minimi per G.
Sia (S, V-S) un qualunque taglio che rispetta A.
Sia (u,v) un arco leggero che attraversa (S, V-S)
Allora l'arco (u, v) è sicuro per A.

Corollario
Sia G = (V, E) un grafo non orientato, connesso e pesato da una funzione peso w: E --> R.
Sia A un sottoinsieme di archi E contenuto in uno degli alberi di copertura minimi per G.
Sia C una componente connessa (ossia un albero) della foresta G_A = (V, A)
Sia (u,v) un arco leggero che connette C ad un'altra componente in G_A
Allora l'arco (u, v) è sicuro per A.

Se abbiamo un grafo G e abbiamo un parziale albero di copertura, se facciamo un taglio che rispetta questo, allora l'arco leggero che attraversa il taglio è un arco sicuro.

Algoritmo di Kruscal

MST-Kruscal(G, w)

// Inizializzazione: crea un insieme per ogni vertice
A <-- Ø
for each vertice di G
    Make-Set(V)

// Ordinamento
Ordina gli archi di E per peso w non decrescente

// Costruzione MST
for each arco (u,v), in ordine di peso w non decrescente
    // verifica se l'arco (u,v) collega 2 vertici appartenenti
    // allo stesso albero (stesso insieme di vertici)
    if ( Find-Set(u) != Find-Set(v) )
        A <-- Union ( A, {(u,v)} )
        UnisciInsiemi(u, v)

return A

O( V )



O( E log E)


L'operazione di
unione costa
O( log E ) e
viene ripetuta
per ogni arco E
--> O(E log E)

Complessità: O( E log E )

Algoritmi do Prism

L'algoritmo parte da un nodo radice r ed espande ad ogni passo l'albero di copertura minimo A sino a che questo non copre tutti i vertici.
Ad ogni passo viene aggiunto all'albero un arco leggero che collega un vertici in A ad un vertice in V-A
Per la scelta dell'arco leggero si usa una coda prioritaria:

ad ogni istante contiene tutti i vertici non appartenenti all'albero A
la posizione di ogni vertici v nella coda dipende dal valore di un campo chiave corrispondente al minimo tra i pesi degli archi che collegano v ad un qualunque vertice in A. Se v non è collegato ad alcun vertice in A allora key[v] = Inf.

MST-Prim(G, w, r)



// Inizializzazione coda prioritaria

Q <-- V[G]

for each vertice u di Q

    key[u] <-- Inf
key[r] <-- 0
p[r] <-- NULL

while Q
    u <-- Extract-Min(Q)

    for each vertice v adiacente a u
        if ( v appartenente a Q  and  w(u,v) < key[v] )
            p[v] <-- u
            key[v] <-- w(u,v)

Build-Heap --> O( V )

V * O( log V )

V * adj(V) --> O( E )

O( E ) * O( log V )
aggiustamento dello heap

Complessità: O( (V+E) log(V) ～ O( E log(V) )

Cammini minimi

Sia G = (V, E) un grafo orientato e pesato con una funzione peso w: E --> R.
Il peso w(p) di un cammino p è la somma dei pesi degli archi che lo compongono.
Il peso di camminino minimo dal vertice u al vertice v è definito come il peso del cammino di peso minimo da u a v se tale cammino esiste, Inf altrimenti.

Nel caso di grafi non pesati, l'identificazione dell'albero dei cammini minimi può essere eseguita tramite la procedura di visita in ampiezza BFS.

Rappresentazione dei cammini minimi
Per rappresentare i cammini minimi si usa normalmente un vettore p[] che contiene per ogni vertice l'indice del predecessore, oppure NULL se questo non esiste.
Il sottografo G_p(V_p, E_p) indotto da p è noto come sottografo dei predecessori.

Si può dimostrare che l'insieme dei cammini minimi da un vertice radice costituisce un albero.

Un albero di cammini minimi con radice s è un sottografo orientato G'=(V', E') in cui V' è un sottoinsieme di V, E' è un sottoinsieme di E tale che:

V' è l'insieme dei vertici raggiungibili da s
G' è un albero con radice in s
per ogni vertice in V' l'unico cammino semplice da s a v in G' è un cammino da s a v in G.

Cicli con pesi negativi
Il problema dell'identificazione dei cammini minimi con sorgente singola non è ben definito se il grafo contiene dei cicli con peso negativo raggiungibili dalla sorgente.
In tal caso non esiste nessun cammino minimo dalla sorgente ad un vertice del ciclo, poichè percorrendo un'ulteriore volta il ciclo il peso del cammino diminuisce.
Si usa allora assegnare al peso di cammino minimo del vertice il valore -Inf.

Algoritmi
Si basano su una fase di inizializzazione e una di rilassamento
1. Initialize-Single-Source(G, s)

for each vertice in V
d[v] <-- Inf
p[v] <-- NULL
d[s] <-- 0

Complessità: O( V )
2. Relax
Consiste nel:

mantenere una stima d[u] del peso del cammino relativo a ciascun nodo u
rilassare (ossia aggiornare) il valore d[v] (e conseguentemente di p[v]) verificando se non convenga considerare il cammino che porta a v passando attraverso un certo arco (u, v).

Avviene considerando un arco (u, v) di peso w:

Relax(u, v, w)

if ( d[v] > d[u] + w(u,v) )
d[v] <-- d[u] + w(u,v)
p[v] <-- u

Complessità: O( 1 )

Algoritmo di Dijkstra

Permette di trovare i shortest paths con sorgente singola su un grafo orientato (anche ciclico) e pesato nel caso in cui tutti i pesi degli archi siano non negativi.
L'algoritmo usa una strategia di tipo Greedy

L'algoritmo mantiene un insieme S contenente i vertici il cui peso di cammino minimo da s è già stato determinato.

Ad ogni passo l'agoritmo:

seleziona il vertice u in V-S con la minima distanza di cammino minimo
inserisce u in S
rilassa tutti gli archi uscenti da u

I vertici V-S sono mantenuti in una coda prioritaria Q avente come chiave per ogni vertice u il valore d[u].

Dijkstra(G, w, s)

Initialize-Single-Source(G, s)
S <-- Ø
Q <-- V[G]

while ( Q != Ø )
    u <-- Extract-Min (Q)
    S <-- Union(S, {u})

    for each vertice v adiacente a u
        Relax(u, v, w)

O( V )

O ( V )
V * O( logV)

tot --> O(E)
E * O (log V)

Complessità: O( (V+E) * logV ) ～ O( E log(V) )

Algoritmo di Bellman-Ford

Permette di trovare i shortest paths con sorgente singola su un grafo orientato (anche ciclico) e pesato nel caso più generale in cui i pesi degli archi possono essere negativi.

L'algortimo restituisce:

FALSE: se trova un ciclo di peso negativo raggiungibile dalla radice
TRUE e l'albero dei cammini minimi in caso contrario.

Bellman-Ford(G, w, s)

Initialize-Single-Source(G, s)

for i <-- 1 to |V[G] -1|
    for each arco (u,v) appartentente a E[G]
        relax(u, v, w)

for each arco (u, v) appartenente a E[G]
    // se riesco ancora a rilassare
    // esistono cicli negativi
    if ( d[v] > d[u] + w(u,v) )
        return FALSE
return TRUE

O( V )

O ( V * E)

O ( E)

Complessità: O( V*E )

notes

¹Vedi BST per riflessioni sugli aleri