Algoritmi e programmazione/L'ADT grafo non orientato

Da WikiAppunti.
Nota disambigua.svg Il titolo di questa pagina non è corretto per via delle caratteristiche del software MediaWiki. Il titolo corretto è 12. L'ADT grafo non orientato.
Gtk-go-back-ltr.svg  11. Le tabelle di hashGtk-home.svg  Algoritmi e programmazione13. Gli algoritmi di visita dei grafi  Gtk-go-forward-ltr.svg

Matrice di adiacenza[modifica]

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

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

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

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]

Problema della colorabilità[modifica]

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]

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]

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

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.
Nota disambigua.svg Il titolo di questa pagina non è corretto per via delle caratteristiche del software MediaWiki. Il titolo corretto è 12. L'ADT grafo non orientato.
Gtk-go-back-ltr.svg  11. Le tabelle di hashGtk-home.svg  Algoritmi e programmazione13. Gli algoritmi di visita dei grafi  Gtk-go-forward-ltr.svg