Algoritmi/L'ADT grafo non orientato

Matrice di adiacenza

La matrice di adiacenza $A$ è una matrice quadrata $\left|V\right|\times \left|V\right|$, in cui ogni cella di indice $ij$ contiene 1 o 0 a seconda se l'elemento $i$ è connesso o no all'elemento $j$.

Vantaggi/svantaggi

• svantaggio: se il grafo non è orientato, la matrice risulta simmetrica rispetto alla diagonale principale;
• vantaggio: se il grafo è pesato, il valore di peso si può inserire direttamente nella matrice al posto di 1 → un numero diverso da 0 determina sia l'esistenza dell'arco, sia il valore di peso;
• la complessità spaziale è: $S\left(n\right)=\Theta \left({\left|V\right|}^{2}\right)$ → vantaggioso per grafi densi;
• vantaggio: per verificare una connessione basta accedere ad una cella della matrice → costo unitario.

Lista di adiacenza

Ogni cella di indice i di un vettore contiene una lista di tutti gli elementi adiacenti all'elemento i-esimo.

Vantaggi/svantaggi

• svantaggio: in un grafo pesato, si deve memorizzare anche il peso sotto forma di denominatore;
• svantaggio: gli elementi complessivi nelle liste sono $2\left|E\right|$;
• $S\left(n\right)=O\left(\max {\left(\left|V\right|,\left|E\right|\right)}\right)=O\left(\left|V\right|+\left|E\right|\right)$ → è vantaggioso per i grafi sparsi;
• svantaggio: l'accesso topologico è meno efficiente perché non ha costo unitario.

Generazione di grafi casuali

1. Il grafo non è modello della realtà, ma viene generato da casuali coppie di vertici → eventuali archi duplicati e cappi da eliminare.
2. Calcolo probabilistico che nasce da un grafo completo: Tra tutti i possibili ${\tfrac {V\left(V-1\right)}{2}}$ archi del grafo completo, si considerano solo gli archi di probabilità inferiore a un valore soglia di probabilità specificato:

$E=p{\frac {V\left(V-1\right)}{2}}\Rightarrow p=2{\frac {E}{V\left(V-1\right)}}\in \left[0,1\right]$

Vantaggioso perché non si considerano duplicati e cappi, e se vengono richiesti $E$ archi si ottengono in media $E$ archi.

Applicazioni

I grafi si possono usare per:

• mappe: ricerca del cammino minimo tra due città;
• ipertesti: documenti = nodi, collegamenti = archi;
• circuiti:.
• scheduling: ordinamento per tempi di esecuzione dei compiti vincolati (es. analisi I - analisi II - metodi matematici);
• matching: esecuzione di compiti in parallelo su più risorse;
• reti: mantenimento delle condizioni affinché una rete rimanga connessa.

Si considerano solo problemi trattabili, che abbiano cioè complessità polinomiale.

Problemi non trattabili

Problema della colorabilità

In una cartina geografica, quanti colori servono al minimo affinché ogni Stato sia colorato con colori diversi da quelli degli Stati adiacenti ad esso?

Ricerca di un cammino semplice

Esiste un cammino semplice che connette due nodi? Partendo da un nodo, passo da nodi adiacenti non ancora visitati finché non arrivo all'altro nodo. È un algoritmo di tipo ricorsivo, perché quando si arriva con insuccesso a un punto finale di un cammino semplice, si ritorna a esplorare le altre possibilità. Con un vettore si tiene conto dei nodi già visitati.

Ricerca di un cammino di Hamilton

Esiste un cammino semplice che connette due nodi e che tocca tutti i nodi del grafo una sola volta?

L'algoritmo di ricerca opera in maniera analoga al cammino semplice, aggiungendo il vincolo che il cammino da ricercare deve avere lunghezza $\left|V\right|-1$. Durante il backtrack nel caso di un cammino non nella lunghezza desiderata, bisogna resettare il vettore che tiene conto dei nodi già visitati. La verifica di un cammino di Hamilton è polinomiale, ma la ricerca è di complessità esponenziale per colpa del backtrack.

Ricerca di un cammino di Eulero

Königsberg è una città costruita lungo un fiume, in cui vi è una serie di isole collegate alle due rive da ponti. Le isole/rive sono i nodi del grafo, e i ponti sono gli archi → multigrafo: ci sono archi duplicati in un grafo non orientato, con informazioni diverse non ridondanti. Si vogliono attraversare tutti i ponti una sola volta.

Il cammino di Eulero è il cammino, non necessariamente semplice, che attraversa tutti gli archi una sola volta. chiuso → ciclo di Eulero

Lemmi

• Un grafo non orientato ha un ciclo di Eulero se e solo se è connesso e tutti i suoi vertici sono di grado pari.
• Un grafo non orientato ha un cammino di Eulero se e solo se è connesso e se esattamente due vertici hanno grado dispari.