Il concetto di grafo

Consideriamo il problema di rappresentare i collegamento tra gli utenti iscritti ad un social network. Ogni iscritto avrà come contatto diversi altri iscritti i quali, a loro volta, saranno collegati ad altri iscritti.

Definizione di grafo

Vediamo ora una definizione formale di grafo.

Grado

Come visto nell’esempio sopra, ogni nodo può essere connesso a quanti altri nodi si vuole, anche a zero (Zoe, nell’esempio sopra, non ha lati incidenti). Inoltre, in un grafo orientato un nodo A può avere un arco uscente verso B, ma potrebbe non avere l’arco entrante in A e uscente da B. Vediamo nella seguente definizione come rendere precisi questi concetti.

Esempio: grafo orientato

Infine notiamo come un qualsiasi cammino che termini in E, ad esempio A, B, D, E, può unicamente rimanere in attraverso l’unico arco uscente da E che riporta d E stesso (tale arco è un loop).

Cammino e connettività

In un grafo è possibile “muoversi” da un nod ad un altro percorrendo i lati o gli archi. Ad esempio nel grafo sopra posso “spostarmi” da Alice ad Eric, ad esempio, attraverso Carol oppure attraverso Fred. È possibile raggiungere Eric da Alice attraverso Bob, Fred, David e Carol. Ognuno di questa sequenza di nodi che sono tra loro vicini, viene detta cammino, vediamo meglio la definizione di cammino in un grafo.

Esempio: grafo non orientato

Grafi pesati

I grafi visti finora non differenziano tra i vari lati/archi nel senso che non hanno alcun valore associato ad essi. I grafi pesati, per contro, associano ad ogni lato/arco del grafo un peso (tipicamente un valore numerico).

Rappresentazione di grafi

Quanto visto sopra è una rappresentazione matematica (utilizzando formule e simboli matematici) dei grafi, vediamo ora come traduciamo questo in un linguaggio di programmazione (Java negli esempi sotto).

Ci sono due modi principali per rappresentare grafi:

• attraverso liste di adiacenza in cui dei nodi sono collegati tra di loro (simile a quanto abbiamo visto per alberi e liste);
• attraverso una matrice che indica i collegamenti, ci sono due possibili tecniche di questo tipo chiamate matrice di adiacenza e matrice di incidenza.

Nelle prossime sezioni andremo a discutere queste due metodologie di rappresentazione di grafi.

Rappresentazione mediante liste di adiacenza

Per rappresentare i grafi mediante liste di adiacenza (adjacency list), si parte con il definire un nodo del grafo che contiene:

• un valore (value), di tipo Object nel nostro esempio,
• ed una lista di nodi adiacenti, un ArrayList nel nostro esempio.

public class GraphNode {
    public Object value;
    public ArrayList<GraphNode> neighbors;
}

Ogni arco tra nodi, ad esempio tra Alice e Bob, deve prevedere l’inserimento nella lista di un nodo di tutti i suoi vicini. Ad esempio il codice sotto inserisce come vicini del nodo eric i nodi carol e fred (nel codice si assume che le istanze siano già state create).

eric.neighbors.add(carol);
eric.neighbors.add(fred);

Nel caso di grafi non direzionati, se Carol è vicino di Eric allora anche Eric è vicino di Carol, per questo motivo il grafo sarà correttamente rappresentato se, oltre al codice sopra, viene eseguito anche il seguente

carol.neighbors.add(eric);
fred.neighbors.add(carol);

Rappresentazione mediante matrici

Una matrice è una tabella di numeri, in una matrice abbiamo righe e colonne che indichiamo con interi 0,1,2,... (come gli indici di un array bidimensionale in Java). Per indicare una cella di una matrice domanda, quindi, dire quale indice di riga i e quale indice di colonna j. Consideriamo la seguente matrice (in matematica le matrici si includono tra quadre o tra tonde, qui scegliamo di usare le quadre). $$ \mathbf{M} = \begin{bmatrix} 1 & -2 & 1 & 0 & 3\\ 0 & 0 & 1 & 0 & 1\\ 1 & 1 & 1 & 1 & 1\\ \end{bmatrix} $$

La matrice indicata con \(\mathbf{M}\):

• ha 3 righe di indice 0,1,2,
• ha 5 colonne di indice 0,1,2,3,4,
• si dice una matrice \(3 \times 5 \) (si legge tre per cinque),
• non è una matrice \(5 \times 3\),
• ha un totale di \(15\)(\(=3\times 5\)) elementi,
• ha il valore -2 nella cella di indici \(i=0, j=1\),
• ha il valore 1 nella cella di indici \( i=1, j=2 \)
• ha l’ultima riga tutta di valori uguali (1 in questo caso).

Matrice di adiacenza

Dato un grafo con \( n\ \) nodi, la sua matrice di adiacenza è una matrice con \(n\) righe e \(n\) colonne. Ognuno degli \(n\) nodi è associato ad un indice 0,1,...,n-1 (attenzione al meno 1!), in questo modo ogni riga è associata ad un nodo ed ogni colonna è associata ad un nodo. Quindi possiamo indicare con un numero ogni nodo del grafo.

Alice -> 0
Bob   -> 1
Carol -> 2
David -> 3
Eric  -> 4
Fred  -> 5
Zoe   -> 6

Passiamo ora a definire formalmente il contenuto di una matrice di adiacenza.

Matrice di incidenza

Nella matrice di incidenza anziché memorizzare nodi sia sulle righe che sulle colonne, si memorizzano sulle righe i nodi e sulle colonne gli archi. I valori presenti nella matrice dipendono dal fatto che il grafo sia orientato o non orientato:

• nei grafi non orientati ogni colonna ha esattamente due valori ad 1, precisamente nelle righe dei nodi collegati da tale arco, tutti gli altri valori sono 0;
• nei grafi non orientati ogni colonna ha esattamente un valore ad 1 ed un volare -1, il valore 1 nella riga associata al nodo in cui l’arco entra, il valore -1 nella riga associata al nodo da cui l’arco esce, tutti gli altri valori sono 0.