Teoria dei Grafi

Teoria dei grafi

Definizione di grafo

Si definisce un grafo una particolare struttura dati che consiste in:

• Un insieme di nodi N;
• Un insieme di coppie di vertici detti archi, tali che essi colleghino tale coppia di vertici.

Tipi di grafi

Esistono due tipi di grafi:

• Grafi orientati;
• Grafi non orientati;

Grafo orientato (diretto)

Si definisce un grafo orientato (o diretto) un particolare tipo di grafo tale che, dato un insieme di nodi N, esso sarà definito: G = (N, E). Ciò vale a dire che ogni arco contenuto nel grafo collega un nodo n₁ ad un nodo n₂, ma non viceversa.

Grafo non orientato

Si definisce un grafo non orientato un particolare tipo di grafo tale che, dato un insieme di nodi N, esso sarà definito: G = (N, E). Ciò vale a dire che per ogni arco contenuto nel grafo che collega un nodo n₁ ad un nodo n₂, corrisponderà un altro arco che collega tali nodi nel senso inverso.

Componente del grafo

Si definisce la componente di un grafo un sottoinsieme dell'insieme dei vertici (o nodi) V.

Incidenza e adiacenza in un grafo

Dato un arco (x, y) (uscente da x ed entrante in y nel caso di grafo orientato), y è adiacente (o incidente nel caso di grafo orientato) a x se e solo se x; y ∈ E.

Grado di un nodo

Si definisce il grado di un nodo il numero di archi che incidono su di essi e viene indicato con la notazione δ(v). Nel caso del grafo orientato si distinguono:

• Grado di entrata: è il numero di archi entranti nel nodo e viene indicato come δ_in(v);
• Grado di uscita: è il numero di archi uscenti dal nodo e viene indicato come δ_out(v).

Cammino in un grafo

Si definisce cammino in un grafo una sequenza di nodi n₀, ..., n_k tali che ∀i ∈ [0, ..., k - 1] (n_i, n_i+1) ∈ E. Si definisce la lunghezza di un cammino il numero di archi descritti in tale sequenza.

Ciclo

Si definisce ciclo di un cammino (non vuoto) tale che n₀, ..., n_k = n₀. Nota: Se un ciclo ha lunghezza 1 allora tale ciclo si dice "self loop".

Cammino semplice

Un cammino si dice semplice se n₀, ..., n_k con ∃ i, j ∈ [0, ..., k] tale che i ≠ j n_i ≠ n_j.

Grafo connesso

Sia G = (V, E) un grafo non orientato, esso viene detto connesso se esiste un cammino tra ogni coppia di vertici in G.

Componente connessa

Una componente di un grafo si dice connessa se ∀x, y ∈ C esiste un cammino da x a y (e viceversa).

Componente connessa massimale

Una componente connessa si dice massimale se non esiste una componente connessa C' tale che C ⊂ C'.

Relazione grafo-albero

Sia G = (V, E) un grafo non orientato, connesso ed aciclico, esso sarà allora un albero.

Rappresentazione dei grafi

Un grafo può essere implementato attraverso varie strutture dati diverse al fine di ottenere una rappresentazione quanto più simile a quella teorizzata. In particolare si hanno le rappresentazioni:

• Con lista di archi;
• Con liste di adiacenza;
• Con liste di incidenza;
• Con matrice di incidenza.

Lista di archi

Consiste nell'associare ad ogni cella di una lista un arco contenente il puntatore ai nodi collegati dall'arco stesso. Si associa a tale struttura una struttura ausiliaria (lista o array) contenente le informazioni relativi ai vari nodi del grafo. Lo spazio totale usato per tale rappresentazione è pari a O(n + m) dove n è il numero di nodi ed m è il numero di archi. Il costo delle varie operazioni per tale rappresentazione sono:

Il punto debole di tale rappresentazione è dato dal fatto che molte operazioni (accessi agli archi) richiedono l'esame dell'intera lista degli archi, ciò vale a dire un tempo che è O(m) nel caso peggiore.

Liste di adiacenza

Consiste nel associare ad ogni vertice del grafo una lista contenente i suoi vertici adiacenti, ovvero tutti i vertici tali che l'arco (v, u) esiste. Si nota che in tale rappresentazione non compaiono esplicitamente gli archi, ma essi sono codificati nella nozione di adiacenza. Inoltre in tale rappresentazione risulta molto semplice trovare gli archi incidenti su un vertice v. La lunghezza delle liste di adiacenza è:

• 2m nel caso di grafo non orientato, in quanto ciascun arco è preso due volte;
• m nel caso di grafo orientato, in quanto ciascun arco è preso una volta sola.

La rappresentazione con lista di adiacenza è efficiente nell'esaminare l'adiacenza tra nodi, ma è inefficiente la verifica della connessione tra due generici nodi del grafo x ed y. I tempi di esecuzione delle varie operazioni sui grafi sono:

In particolare, si osserva che l'operazione di rimozione di un arco risulta meno efficiente rispetto all'implementazione con liste di archi.

Liste di incidenza

La rappresentazione con liste di incidenza rappresenta una combinazione delle rappresentazioni a liste di archi e liste di adiacenza. In particolare, in aggiunta alla rappresentazione con la lista di archi viene memorizzata per ogni vertice una lista di puntatori agli archi incidenti a v. La quantità di spazio occupata in memoria rispetto alle precedenti rappresentazioni è leggermente superiore, ma risulta essere ancora O(m + n) nel caso peggiore. Il costo temporale delle varie operazioni sui grafi in questo caso sono:

Matrici di adiacenza

La rappresentazione con matrice di adiacenza, assunto che i vertici del grafo siano numeri interi da 1 ad n, consiste nel rappresentare le relazioni di adiacenza tra i nodi del grafo in una matrice di dimensione n × n. Tale matrice di adiacenza è definita nel modo seguente:

• M[u, v] = 1 se (u, v) è un arco del grafo;
• M[u, v] = 0 altrimenti.

Si osserva che nel caso degli archi orientati la matrice di adiacenza è simmetrica, dato che M[x, y] = M[y, x]. I vantaggi principali di tale rappresentazione sono che la verifica della presenza dell'adiacenza di due nodi avviene in tempo costante a svantaggio però di un maggior costo per la ricerca di tutti i nodi adiacenti ad un dato nodo. In particolare le complessità temporali delle varie operazioni sono:

Matrici di incidenza

Nella rappresentazione a matrici di incidenza, supposto che i nodi del grafo siano indicizzati sulle righe e gli archi siano indicizzati sulle colonne di una matrice, consiste nel rappresentare in una matrice le relazioni di incidenza tra i nodi del grafo attraverso i suoi archi. Rispetto alla rappresentazione con matrici di adiacenza qui abbiamo una maggiore efficienza sulle operazioni di ricerca dei nodi adiacenti ad un dato nodo a fronte però di una meno efficiente verifica delle adiacenze tra nodi.