Vai al contenuto

Algoritmi/L'ADT grafo non orientato

Wikibooks, manuali e libri di testo liberi.
Indice del libro

Matrice di adiacenza

[modifica | modifica sorgente]

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
  • 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 è: → vantaggioso per grafi densi;
  • vantaggio: per verificare una connessione basta accedere ad una cella della matrice → costo unitario.

Lista di adiacenza

[modifica | modifica sorgente]

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 ;
  • → è vantaggioso per i grafi sparsi;
  • svantaggio: l'accesso topologico è meno efficiente perché non ha costo unitario.

Generazione di grafi casuali

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

[modifica | modifica sorgente]

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

[modifica | modifica sorgente]

Problema della colorabilità

[modifica | modifica sorgente]

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]

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]

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

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.