I Grafi / introduzione

Grafi

Grafi e rappresentazioni

I grafi sono strutture dati caratterizzate dalla presenza di vertici e archi e sono solitamente rappresentati da G(V, E), in cui G è il grafico, V è l'insieme dei vertici e E - senza troppa fantasia - l'insieme degli archi.

I grafi solitamente sono rappresentati o da matrici o da liste. Se sono rappresentati da matrici, la memoria utilizzata è Θ(V2), perché ogni possibile arco è rappresentato, e il valore all'incrocio tra i due vertici è 1 se l'arco esiste, 0 altrimenti.

V1 V2 V3 V4 V5
V1 0 1 1 0 0
V2 1 1 0 0 0
V3 1 0 0 1 1
V4 0 0 1 0 0
V5 0 0 1 0 0

In questo esempio i vertici sono (V1, V2, V3, V4, V5) e gli archi sono ((V1, V2), (V2, V2), (V1, V3), (V3, V4), (V3, V5)).

Se il grafo è semplice, la matrice deve essere trasponibile senza che il risultato cambi; in altre parole, l'informazione di un "triangolo" di dati pari a V*(V-1)/2 è ridondante, perché l'arco (V1, V2) e (V2, V1) sono la stessa cosa:

V1 V2 V3 V4 V5
V1 0 1 1 0 0
V2 1 1 0 0
V3 1 0 0 1 1
V4 0 0 1 0 0
V5 0 0 1 0 0

Se invece gli archi hanno una direzione - come ad esempio le strade a senso unico, che vanno da V1 a V2 ma non viceversa - tutti gli archi sono importanti perché rappresentano un'informazione univoca.

La rappresentazione tramite liste di adiacenza invece contengono una lista di vertici, a ciascuno dei quali corrisponde una lista di altri vertici a cui sono collegati.
Il grafo riportato sopra sarebbe:

  • V1 → V2 → V3
  • V2 → V1 → V2
  • V3 → V1 → V4 → V5
  • V4 → V3
  • V5 → V3

Anche in questo caso, se il grafo non è orientato, alcune informazioni sono ridondanti (es. il collegamento tra V1 e V2 è rappresentato sia nella lista V1 sia nella V2), mentre nel caso di grafi orientati i due collegamenti rappresenterebbero entità diverse e non ci sarebbe ridondanza.

Visita del grafo

La visita del grafo permette, partendo da un vertice, di "toccare" tutti gli altri vertici collegati direttamente o indirettamente.

Si comincia da una sorgente, come nel problema dei flussi di Ricerca Operativa, e si visitano tutti i nodi collegati. Per fare questo, si colorano i nodi dapprima di bianco, poi in grigio, se sono stati visitati, e in nero se tutti i nodi adiacenti sono a loro volta stati visitati (sono in grigio o in nero).

Il seguito nel post Visita di un grafo.