# Algoritmi/L'ADT grafo non orientato

Algoritmi
Copertina Tutti i moduli · Sviluppo
    CopertinaAlgoritmi/Copertina
* Gli algoritmiAlgoritmi/Gli algoritmi
* L'analisi di complessità degli algoritmiAlgoritmi/L'analisi di complessità degli algoritmi
* Gli algoritmi di ordinamentoAlgoritmi/Gli algoritmi di ordinamento
* Grafi e alberiAlgoritmi/Grafi e alberi
* La ricorsioneAlgoritmi/La ricorsione
* Il paradigma "divide et impera"Algoritmi/Il paradigma "divide et impera"
* Gli heapAlgoritmi/Gli heap
* Le tabelle di simboliAlgoritmi/Le tabelle di simboli
* Alberi binari di ricerca (BST)Algoritmi/Alberi binari di ricerca (BST)
* Tipologie di problemiAlgoritmi/Tipologie di problemi
* Le tabelle di hashAlgoritmi/Le tabelle di hash
* L'ADT grafo non orientatoAlgoritmi/L'ADT grafo non orientato
* Gli algoritmi di visita dei grafiAlgoritmi/Gli algoritmi di visita dei grafi
* Le applicazioni degli algoritmi di visita dei grafiAlgoritmi/Le applicazioni degli algoritmi di visita dei grafi
* Gli alberi ricoprenti minimiAlgoritmi/Gli alberi ricoprenti minimi
* I cammini minimiAlgoritmi/I cammini minimi
Modifica il sommario

## 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

* Il grafo non è modello della realtà, ma viene generato da casuali coppie di vertici → eventuali archi duplicati e cappi da eliminare.
* 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.