Grafi

Definizioni

Grafo orientato

Un grafo orientato (directed) è una coppia dove è un insieme di nodi (node) o vertici (vertex) ed è un insieme di coppie ordinate di nodi dette archi (edge).

Grafo non orientato

Un grafo non orientato (undirected) è una coppia dove è un insieme di nodi o vertici ed è un insieme di coppie non ordinate di nodi dette archi.

Terminologia

• Un vertice è detto adiacente a se esiste un arco ;
• Un arco è detto incidente da a ;
• In un grafo non orientato, la relazione di adiacenza è simmetrica;
• è incidente da a ;
• è incidente da a ;
• è incidente da ad ;
• e sono adiacenti ad .

Un grafo con un arco fra tutte le coppie di nodi è detto completo; informalmente si dice sparso se ha pochi archi o denso se ne ha tanti.

Nei grafi non orientati il grado (degree) di un nodo è il numero di archi incidenti su di esso.

Nei grafi orientati distinguiamo il grado entrante (in-degree), ossia gli archi incidenti su un nodo, e il grado uscente (out-degree), ossia gli archi incidenti da un nodo.

Dimensioni del grafo

• Numero di nodi: ;
• Numero di archi: .

La complessità degli algoritmi sui grafi è espressa sia in termini di sia di , ad esempio .

Cammino (path)

In un grafo , un cammino di lunghezza è una sequenza di nodi , , …, tale che per . Un cammino è detto semplice se tutti i suoi nodi sono distinti.

> $a,b,c,e,d$ è un cammino semplice nel grafo di lunghezza 4.

Memorizzazione dei grafi

Matrici di adiacenza

Grafi orientati

Grafi non orientati

Liste di adiacenza

Grafi orientati

Grafi non orientati

Iterazione sui grafi

Iterazione su tutti i nodi del grafo

Il costo computazionale è per iterare sui nodi, ma il costo effettivo dipende anche dall’operazione che eseguiamo su ogni nodo (se anche quella è , complessivamente è ).

Iterazione su tutti i nodi e archi del grafo

Il costo computazionale è con le liste di adiacenza (ci sono archi e la lista di contiene solo gli archi che partono da ), con le matrici di adiacenza.

Riassunto

Matrici di adiacenza	Liste di adiacenza
Complessità	Complessità
Verificare se è adiacente a richiede tempo	Verificare se è adiacente a richiede tempo
Iterare su tutti gli archi richiede tempo	Iterare su tutti gli archi richiede tempo
Ideale per grafi densi	Ideale per grafi sparsi

• Se non specificato diversamente, l’implementazione è basata su liste di adiacenza;
• L’accesso alle informazioni su un nodo avrà costo costo , ad esempio usando un vettore (nodi con valori int) o un dizionario (nodi con altri tipi);
• Le operazioni per aggiungere nodi e archi hanno costo , ossia il caricamento in memoria del grafo non influisce sull’algoritmo in sé;
• Dopo l’inizializzazione il grafo è statico.

Visite dei grafi

Visita in profondità (DFS)

È una visita ricorsiva: per ogni nodo adiacente alla radice, si visita tale nodo, visitando ricorsivamente i suoi nodi adiacenti; come per gli alberi, la visita può essere in pre-ordine o post-ordine. Alcune applicazioni: ordinamento topologico, componenti connesse, componenti fortemente connesse.

Visita in ampiezza (BFS)

È una visita dei nodi per livelli: prima si visita la radice, poi i nodi a distanza 1 dalla radice, poi a distanza 2, ecc. Esempio di applicazione: calcolare i cammini più brevi da una singola sorgente.

Ogni volta che si attraversa un nodo, si segna che esso è già stato attraversato, per evitare ripetizioni.

Componenti connesse

• Un grafo non orientato è connesso se e solo se ogni suo nodo è raggiungibile da ogni altro suo nodo;
• Un grafo è una componente connessa di se e solo se è un sottografo connesso e massimale di ;
• è un sottografo di () se e solo se e ;
• G’ è massimale se e solo se non esiste un altro sottografo di tale che è connesso e più grande di ().

Cicli

In un grafo non orientato , un ciclo di lunghezza è una sequenza di nodi , , …, tale che per e .

Un grafo che non contiene cicli è detto aciclico. Ci serve un algoritmo che, dato un grafo non orientato , restituisca true se contiene un ciclo, false altrimenti.

1. Parto da un nodo , segnandolo come visitato;
2. Effettuo una DFS a partire da , controllando se, scendendo in profondità, incontro nodi già marcati come visitati.
3. Se sì, esiste un ciclo (return true)
4. Se no? Non c’è un ciclo in questa componente, ma potrebbe esistere in un’altra, quindi devo ricominciare a cercare tra i nodi non visitati.
5. Se non ho mai restituito true prima, alla fine restituisco false.