Summaries

Un grafo è costituito da una coppia (N, A) dove N è l'insieme dei nodi e A è l'insieme di coppie di nodi.

• Grafo orientato è un grafo in cui gli archi sono coppie di nodi ordinati:

  

• Grafo non orientato è un grafo in cui gli archi non sono rappresentati da coppie ordinate:

  

Il numero di archi possibili in un grafo sono:

• MAX: n²
• MIN: n(n-1)/2

che equivale come complessità a circa O(n²).

• Grafo denso: nel caso di grafi con n² archi si parla di grafo denso
• Grafo sparso: nel caso di grafi in cui ci sono circa n archi (circa 1 per ogni nodo) si parla di grafo sparso

Adiacenza (orientati)

Dato un arco (v, w) si dice che w è adiacente a v e che l'arco esce da v ed entra in w.

Grado (orientati)

Si possono distinguere due tipi di gradi:

• grado di entrata: numero archi entranti da un nodo
• grado di uscita: numero archi uscenti da un nodo

Cammino

Un cammino da v a w è una sequenza di archi distinti (v1, v2) (v2, v3) ... (vK-1, vK) tale che v = v1 e w = vK ed ha lunghezza K-1.

Ciclo

È un cammino attraverso cui, a partire da un nodo x, è possibile ritornare su di esso. Un grafo che contiene un ciclo viene definito ciclico sennò aciclico.

Grafo non ordinato connesso

Se esiste un cammino che collega ogni coppia di nodi, una componente connessa è un insieme massimale di nodi tale che esiste un cammino che collega ogni coppia di nodi di essa.

Grafo ordinato debolmente connesso e fortemente connesso

Si definisce fortemente connesso se per ogni coppia di nodi esiste un cammino orientato. Si definisce debolmente connesso se il grafo non orientato ottenuto da esso è connesso.

Grafi pesati

Una differenza importante tra grafo e albero è che in quest'ultimo è possibile definire un nodo di entrata. Inoltre il contenuto informativo dei grafi non è limitato solamente ai nodi ma anche gli archi.

Rappresentazione dei grafi

Il problema principale nella rappresentazione dei grafi è che ogni nodo deve essere direttamente accessibile quindi è necessario avere una qualche struttura dati che lo permetta.

Inoltre è possibile creare un'altra struttura dati che conservi il contenuto informativo del nodo indipendente dalla strategia di rappresentazione degli archi.

Le più comuni modalità di rappresentazione di quest'ultimi:

• Matrice di adiacenza: più velocità nella lettura dell'esistenza di un arco ma spreco di memoria (se non è denso)
• Liste di adiacenza: più velocità nella lettura dei nodi adiacenti ma meno velocità nella lettura dell'esistenza di un arco

Classi

class Grafo {
    protected:
        n nodi, m archi...
        matrice/lista adiacenti
    public:
        Grafo(unsigned n)
        bool operator() (unsigned i, unsigned j) // verifica se l'arco (i, j) esiste
        void operator() (unsigned i, unsigned j, bool b) // se voglio aggiungere l'arco (i, j)
        int n() // numero nodi
}

Esempio di utilizzo

Scrivere una funzione che, ricevuto un grafo non orientato, restituisca, per ciascun nodo, il suo grado.

Vector<int> numAdiacenti(const Grafo& G) {
    Vector<int> grado(G.n());
    for(int i = 0; i < G.n(); i++) {
        grado[i] = 0;
        for(int j = 0; j < G.n(); j++) {
            if(i != j && G(i, j)) // O(1) oppure O(n)
                grado[i]++;
        }
    }
    return grado;
}

La funzione ha O(n²) in caso di matrice di adiacenza sennò O(n³). Lo stesso algoritmo possiamo risolverlo in funzione dell'arco:

Arco e;
grado[i] = 0;
for(e = G.primoAd(i); !e.nullo; e = G.succAd(e)) grado[i]++;

Con questo algoritmo possiamo avere una complessità costante di O(n²).