11. Le tabelle di hash | Algoritmi e programmazione | 13. Gli algoritmi di visita dei grafi |
---|
Gli appunti che seguono sono contenuti nella sottopagina /sub (modifica · cronologia · aggiorna) |
Matrice di adiacenza[]
12 La matrice di adiacenza è una matrice quadrata , in cui ogni cella di indice contiene 1 o 0 a seconda se l'elemento è connesso o no all'elemento .
- 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 è: → vantaggioso per grafi densi;
- vantaggio: per verificare una connessione basta accedere ad una cella della matrice → costo unitario.
Lista di adiacenza[]
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 ;
- → è vantaggioso per i grafi sparsi;
- svantaggio: l'accesso topologico è meno efficiente perché non ha costo unitario;
Generazione di grafi casuali[]
- 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 archi del grafo completo, si considerano solo gli archi di probabilità inferiore a un valore soglia di probabilità specificato:
Vantaggioso perché non si considerano duplicati e cappi, e se vengono richiesti archi si ottengono in media archi.
Applicazioni[]
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[]
Problema della colorabilità[]
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[]
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[]
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 . 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[]
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.
11. Le tabelle di hash | Algoritmi e programmazione | 13. Gli algoritmi di visita dei grafi |
---|