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 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
  • 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 è: 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[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 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[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 \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[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 \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[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