Algoritmi e programmazione/L'ADT grafo non orientato

Il titolo di questa pagina non è corretto per via delle caratteristiche del software MediaWiki. Il titolo corretto è 12. L'ADT grafo non orientato.

[[{{#ifcategory:Traduzioni\|\|Algoritmi e programmazione\|/L'ADT grafo non orientato}}/Le tabelle di hash{{#ifcategory:Traduzioni\|/L'ADT grafo non orientato\|\|/L'ADT grafo non orientato}}\|11. Le tabelle di hash]]	[[{{#ifcategory:Traduzioni\|/L'ADT grafo non orientato\|Algoritmi e programmazione\|/L'ADT grafo non orientato}}\|{{#ifcategory:Traduzioni\|\|Algoritmi e programmazione\|/L'ADT grafo non orientato}}]]	[[{{#ifcategory:Traduzioni\|\|Algoritmi e programmazione\|/L'ADT grafo non orientato}}/Gli algoritmi di visita dei grafi{{#ifcategory:Traduzioni\|/L'ADT grafo non orientato\|\|/L'ADT grafo non orientato}}\|13. Gli algoritmi di visita dei grafi]]

Matrice di adiacenza[modifica | modifica sorgente]

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

Vantaggi/svantaggi

13 svantaggio: se il grafo non è orientato, la matrice risulta simmetrica rispetto alla diagonale principale;
15 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;
16 la complessità spaziale è: <math>S \left( n \right) = \Theta \left( {\left| V \right|}^2 \right)</math> → vantaggioso per grafi densi;
vantaggio: per verificare una connessione basta accedere ad una cella della matrice → costo unitario.

Lista di adiacenza[modifica | modifica sorgente]

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

Vantaggi/svantaggi

20 svantaggio: in un grafo pesato, si deve memorizzare anche il peso sotto forma di denominatore;
21 svantaggio: gli elementi complessivi nelle liste sono <math>2 \left| E \right|</math>;
<math>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)</math> → è vantaggioso per i grafi sparsi;
svantaggio: l'accesso topologico è meno efficiente perché non ha costo unitario.

Generazione di grafi casuali[modifica | modifica sorgente]

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

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

Vantaggioso perché non si considerano duplicati e cappi, e se vengono richiesti <math>E</math> archi si ottengono in media <math>E</math> archi.

Applicazioni[modifica | modifica sorgente]

2 I grafi si possono usare per:

mappe: ricerca del cammino minimo tra due città;
ipertesti: documenti = nodi, collegamenti = archi;
circuiti.
3 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.

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

Problemi non trattabili[modifica | modifica sorgente]

Problema della colorabilità[modifica | modifica sorgente]

8 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[modifica | modifica sorgente]

25 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[modifica | modifica sorgente]

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

34 L'algoritmo di ricerca opera in maniera analoga al cammino semplice, aggiungendo il vincolo che il cammino da ricercare deve avere lunghezza <math>\left| V \right| -1</math>. 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[modifica | modifica sorgente]

36 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.

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

38 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.