Appunti di informatica sui Grafi

GRAFI - DEFINIZIONI

Grafo orientato o diretto

• Un grafo orientato (o diretto o di-grafo) G è una coppia (V,E), dove
  • V è l'insieme (finito) dei vertici
  • E = {(v_i, v_j); v_i, v_j ∈ V} è l'insieme (finito) degli archi, che corrisponde ad una relazione binaria su V.
  (v_i, v_j) ≠ (v_j, v_i)
• I grafi orientati si rappresentano spesso disegnando
  • I vertici sotto forma di cerchi
  • Gli archi sotto forma di frecce.

Grafo non orientato

• Un grafo non orientato è ancora una coppia G=(V,E), ma l'insieme E è costituito in questo caso da coppie non ordinate di vertici.
• Nei grafi non orientati gli archi sono usualmente rappresentati con linee.
  • (v_i, v_j)≡(v_j, v_i): Grafo semplice

Grado

• In un grafo non orientato il grado di un vertice è il numero di archi incidenti.
• In un grafo orientato:
  • Il grado entrante è il numero di archi entranti
  • Il grado uscente è il numero di archi uscenti
  • Il grado è la somma del grado entrante e del grado uscente.
• Un vertice con grado 0 si dice isolato.

GRAFI - DEFINIZIONI

Grafo orientato o diretto

• Un grafo orientato (o diretto o di-grafo) G è una coppia (V,E), dove
  • V è l'insieme (finito) dei vertici
  • E = {(v_i, v_j); v_i, v_j ɛ V} è l'insieme (finito) degli archi, che corrisponde ad una relazione binaria su V.
  • (v_i, v_j) ≠ (v_j, v_i)
• I grafi orientati si rappresentano spesso disegnando
  • I vertici sotto forma di cerchi
  • Gli archi sotto forma di frecce.

Grafo non orientato

• Un grafo non orientato è ancora una coppia G=(V,E), ma l'insieme E è costituito in questo caso da coppie non ordinate di vertici.
• Nei grafi non orientati gli archi sono usualmente rappresentati con linee.
  • (v_i, v_j)=(v_j, v_i): Grafo semplice

Grado

• In un grafo non orientato il grado di un vertice è il numero di archi incidenti.
• In un grafo orientato:
  • Il grado entrante è il numero di archi entranti
  • Il grado uscente è il numero di archi uscenti
• Il grado è la somma del grado entrante e del grado uscente.
• Un vertice con grado 0 si dice isolato.

Foresta e albero

• Un grafo non orientato aciclico si dice foresta.
• Un grafo non orientato aciclico connesso si dice albero.

• Multigrafo: E è un multinsieme (gli archi possono essere di "tipo" diverso, ad es. relazioni di parentela e di amicizia nello stesso grafo)
• Pseudografo: E contiene anche coppie (v_i, v_i) → cappi
• Circuito in un grafo: v₁,v₂,...,v_k(v_i, v_i+1) ∈ E, v₁= v_k
• Ciclo in un grafo: circuito con v₁≠ v₂ ≠ .... ≠ v_k

Grafo pesato:

• Ad ogni arco e_k è associato un valore reale w_k

RAPPRESENTAZIONE DEI GRAFI

Rappresentazioni

Esistono due modi principali per rappresentare un grafo G=(V,E):

1. Tramite liste di adiacenza
   • ogni vertice è associato con la lista dei vertici adiacenti.
   • Lista di adiacenza può essere una tabella o una lista concatenata
2. Tramite matrici di adiacenza.
   • Matrice di adiacenza:a_h=1 se (v_i, v_j) ∈ E,a_h=0 altrimenti
   • Matrice di incidenza:a_h=1 se v_i ∈ e_h, cioè se l'arco e_h incide sul nodo v_ia_h=0 altrimenti

Liste di adiacenza

• Dato un grafo G=(V,E), esso può essere rappresentato tramite un vettore A, il cui elemento A[i] contiene il puntatore alla lista dei vertici adiacenti al vertice i.

Limiti

• Il principale limite della rappresentazione tramite liste di adiacenza consiste nella difficoltà nel verificare se esiste un arco tra il vertice u ed il vertice u'.
• In tal caso è infatti necessario scandire l'intera lista dei vertici adiacenti a u (o a u').

Matrice di adiacenza

• Consiste in una matrice di dimensione |V| * |V|.
• L'elemento a_ij vale 1 se (i,j)∈E, 0 altrimenti.
• Nel caso di grafi non orientati la matrice è simmetrica.
• Nel caso di grafi pesati l'elemento a_ij, qualora non sia nullo, assume il valore del peso dell'arco anziché essere “solo” 1.

Esempi

Confronto

• Rispetto alla rappresentazione tramite liste di adiacenza, quella tramite matrice di adiacenza:
• Richiede più memoria (a meno che il grafo non sia particolarmente denso)
• Permette un accesso più efficiente alla topologia del grafo.

Vantaggi e Svantaggi

• Lista di adiacenza: O(m)
  • Vantaggi: permette di scorrere i nodi adiacenti a v in O(grado(v))
  • Svantaggi: inserimenti e cancellazioni su liste concatenate in O(grado(v))
• Matrice di adiacenza: O(n²)
  • Vantaggi: Inserimenti e cancellazioni in O(1)
  • Svantaggi: permette di scorrere i nodi adiacenti a v in O(n)

ALGORITMI DI VISITA

Visita di un Grafo

• L'operazione corrispondente ad esplorare un grafo a partire da un vertice dato (denominato sorgente) toccando tutti i vertici da questo raggiungibili si definisce visita.
• Esistono due principali algoritmi di visita:
  • Visita in ampiezza
  • Visita in profondità
• Difficoltà:
  • Presenza di cicli
  • Presenza di nodi isolati

Visita in ampiezza

La visita in ampiezza (o breadth-first search, BFS) consiste nel visitare i vertici del grafo per livelli:

1. l=0, SI={sorgente}
2. Si visitano tutti i vertici SI+1 non ancora visitati e adiacenti ad almeno un vertice in SI
3. l=l+1
4. Si ripete da 2 sino a che SI è vuoto.

Visita in profondità

• La visita in profondità (Depth-First Search, o DFS) segue un approccio opposto a BFS.
• Ad ogni passo si visita un vertice adiacente all'ultimo vertice visitato.
• Quando non ne esistono, si ritorna indietro all'ultimo vertice visitato che abbia vertici adiacenti non visitati, e li si visita.
• La procedura di DFS è normalmente implementata attraverso una procedura ricorsiva.

• La visita procede di tutti gli archi uscenti da un nodo.
• Se tutti i nodi adiacenti sono stati visitati allora si torna al nodo “predecessore”.
• Una volta tornati al nodo di partenza si prosegue da un nodo qualsiasi non visitato.
• I nodi vengono rinumerati secondo l'ordine di visita.