GRAFI - prof.Claudio Maccherani - Perugia - 2009 pag. 4 prof. Claudio Maccherani - Perugia – 2009 .
Un Grafo è un ADT (Abstract Data Type) definito da un insieme di elementi o nodi posti in relazione tra loro mediante archi. I grafi servono per rappresentare graficamente, semplificandole, realtà complesse.
Ad esempio la cartina stradale è un grafo con le città come nodi e le strade come archi.
Definizione: "un grafo G = (V,E) è un insieme di vertici (nodi) V e di spigoli (archi) E ciascuno dei quali connette due vertici".
Il grafo è orientato se i vertici (archi) hanno direzione; in caso contrario è non orientato.
In un grafo non orientato due nodi sono adiacenti se esiste un arco che li unisce.
Un cammino è una sequenza di nodi adiacenti. Esso è un percorso quando gli archi sono distinti ed un circuito o ciclo quando nodo iniziale e nodo finale coincidono.
La distanza tra due archi è la lunghezza (numero di archi) del cammino più breve che li unisce.
Un grafo è pesato quando ad ogni arco è associato un "peso" (ad esempio, ogni strada della cartina ha associata la propria lunghezza).
Per rappresentare i grafi si usa il Vettore di Liste di Adiacenza o la Matrice di Adiacenza.
Grafo Vettore di Liste di Adiacenza (VLA) Matrice di Adiacenza
M 1 2 3 4 5
1 0 1 1 0 0
2 1 0 1 1 0
3 1 1 0 0 1
4 0 1 0 0 1
5 0 0 1 1 0
M 1 2 3 4 5
1 0 1 1 0 0
2 0 0 1 1 1
3 0 0 0 0 0
4 0 0 0 0 0
5 0 0 0 1 1
Il Vettore delle Liste di Adiacenza è un vettore (di tanti elementi quanti sono i nodi del grafo) ogni cui elemento contiene il puntatore alla lista dei nodi collegati a quello associato all’elemento.
La Matrice delle Adiacenze è una matrice quadrata N x N (dove N sono i nodi del grafo) contenente in ogni elemento 1 se esiste il collegamento, 0 altrimenti. Se il grafo è "pesato" (cioè ogni arco ha un valore, un "peso"), al posto di 1 ci sarà il "peso" dell’arco.
1
2 3
4 5
A
1
2 3
4 5
B
1 2 3
2 1 3 4
3 1 2 5
4 2 5
5 3 4
2
1 2 3
3 4 5
3 4
5 5 4
GRAFI - prof.Claudio Maccherani - Perugia - 2009 pag. 4
Per analizzare il contenuto dei grafi si usano le VISITE (in ampiezza BFS e in profondità DFS).
Gli obiettivi fondamentali delle visite sono:
o visitare tutti i nodi senza passare due volte per lo stesso [problema del "commesso viaggiatore"]
o individuare il cammino più breve tra due nodi (se esiste) [problema del "GPS"]
Visita in Ampiezza – BFS (Breadth First Search)
I nodi vengono visitati in ordine di distanza crescente dal nodo di partenza. Si esplorano tutti i vertici che hanno distanza k dal vertice di partenza, poi tutti quelli che hanno distanza k+1, e così via, a "macchia d’olio". Si tiene traccia dello stato del nodo toccato (da scoprire, scoperto, trattato) marcando opportunamente il nodo, ad esempio con colori diversi. È inoltre possibile memorizzare in ogni nodo la sua distanza k dal nodo di partenza, costruendo in tal modo un albero che ha il nodo di partenza come radice (albero BFS) e gli altri nodi al livello della propria distanza da esso.
Visita in Profondità – DFS (Depth First Search)
I nodi vengono visitati andando ad ogni passaggio il più possibile "in profondità", cioè cercando ogni volta di raggiungere il vertice più lontano da quello sorgente.
Si prosegue fino a che è possibile andare avanti senza ritornare su un nodo già visitato e si marcano i nodi, magari colorandoli, mano a mano che si visitano, registrando anche il numero progressivo di visita.Arrivati al vertice più lontano si torna indietro "a ritroso", riapplicando l’algoritmo di visita per ogni nodo e rimarcando i nodi con un altro numero di visita. E così via fino a che non si torna al nodo sorgente.
Quindi si verifica se ci sono dei vertici non visitati, nel qual caso se ne sceglie uno come nuovo vertice sorgente e si riparte con la visita del sottografo.
Ad esempio [ D 2 / 7 ] significa che il nodo D ha avuto il progressivo di visita 2 all’andata e il progressivo di visita 7 al ritorno.
A/0 B/1
C/1 sorgente
D/2
E/2
F/3
A/1/8 B/3/6
D/2/7 C/4/5
E/10/11
F/9/12
GRAFI - prof.Claudio Maccherani - Perugia - 2009 pag. 4 Determinazione del cammino di lunghezza minima
Problema del "GPS", trovare il percorso minimo tra due punti della mappa. Dato il nodo A di partenza, individuare il percorso ottimo per giungere al nodo B in base a un dato criterio (il criterio, ad esempio, potrebbe essere la distanza minima).
Possibili strategie di determinazione del cammino minimo sono:
1) esaminare tutti i possibili percorsi e confrontare i valori ottenuti 2) algoritmo di Dijkstra
3) algoritmo di Bellam & Ford
Individuazione del minimo albero ricoprente (MST)
È una "estremizzazione" della ricerca del cammino minimo. Si cerca all’interno del grafo un sottografo che mantenga la connettività tra i nodi e tale che ogni connessione abbia il minor costo possibile.
Il risultato è una struttura ad albero (non possono esserci cicli in un cammino che tocca i nodi una sola volta) che prende il nome di Minimo Albero Ricoprente (Minimum Spanning Tree) che è l’albero di connessione con "peso" minimo [qui il "peso" è la somma dei pesi di tutti gli archi dell’albero].
Tipica applicazione è la selezione del sottoinsieme delle tratte aeree che permettono di raggiungere le relative destinazioni con costo minimo.
Albero MST
Tre famosi algoritmi di individuazione dell’albero minimo ricoprente (MST) sono:
1) algoritmo di Kruskal 2) algoritmo di Prim 3) algoritmo di Boruskva
Sono tutti algoritmi di tipo "greedy" (golosi), basati sulla scelta dell’alternativa più conveniente al momento.
Grafi eleuriani
Grafo particolare è quello "euleriano", dal matematico Eulero, che nel 1736 lo utilizzò per risolvere il problema dei ponti di Königsberg: un cammino o percorso è detto di Eulero se passa per tutti i nodi percorrendo ogni arco una sola volta; un grafo che contiene almeno un percorso di Eulero è definito "grafo di Eulero". Un esempio classico è disegnare una busta senza staccare la penna dal foglio:
Teorema del circuito euleriano: un grafo ha un circuito di Eulero se e solo se ogni suo vertice è pari (ha un numero pari di archi collegati)
Teorema del percorso euleriano: un grafo ha un percorso di Eulero se e solo se ha esattamente due vertici dispari (tale percorso parte da uno di questi e termina nell’altro)
G A
B C
4
H I
D
F
E
8
2
1
4
2
9
10 7
A
B C
4
H G
I
D
F
11 E
8
8
2
8 7
1
4
2
14 9
10 7
GRAFI - prof.Claudio Maccherani - Perugia - 2009 pag. 4 Grafi hamiltoniani e problemi intrattabili
Eulero non offre una soluzione al problema noto come il problema del commesso viaggiatore (TSP, Travelling Salesman’s Problem). In questo problema i vertici debbono essere attraversati una sola volta:
se in un grafo è possibile individuare un tale ciclo, allora il grafo si dice hamiltoniano. Un ciclo hamiltoniano è un ciclo che visita ogni vertice una sola volta.
Hamilton, però, non ha detto come trovare cicli hamiltoniani, li ha solo definiti. Trovare tali cicli è molto complicato e questo problema, nella teoria della computabilità, viene catalogato come intrattabile (per il quale non è possibile trovare una soluzione immediata, ma occorre esplorare tutte le possibili combinazioni di un insieme di dati in ingresso).
Questi problemi, la cui soluzione potrebbe richiedere tempi di elaborazione molto elevati - anni o millenni - non si debbono confondere con quelli che non hanno soluzione, indecidibili o insolubili, per i quali non esiste alcun algoritmo risolutivo.
Il problema del commesso viaggiatore ["il commesso viaggiatore deve visitare tutte le città di una regione passando per ciascuna di esse una sola volta"] è un problema intrattabile, mentre il problema del barbiere o paradosso di Russel ["il barbiere fa la barba a tutti gli uomini che non se la fanno da soli. Chi fa la barba al barbiere?"] è indecidibile.
Problemi classici
o Ponti di Königsberg è il primo esempio conosciuto di grafo, disegnato da Eulero nel 1736 per risolvere un quesito: era possibile attraversare tutti e 7 i ponti di Königsberg una sola volta e ritornare al punto di partenza?. Eulero dimostrò che ciò non è possibile perché nel grafo non esiste un percorso euleriano, i nodi non sono tutti pari.
o Quattro colori è il problema determinare quanti colori servono per colorare le regioni di una qualsiasi carta geografica in modo tale che due regioni adiacenti abbiano colori diversi. La risposta è "quattro", trovata avvalendosi di un grafo in cui ogni regione è un nodo e gli archi collegano regioni adiacenti. Per risolvere questo problema, apparentemente banale, i matematici hanno impiegato 130 anni, e la soluzione è stata trovata, utilizzando computer, dopo oltre 1.200 ore di tempo di elaborazione parallela. Questo è un problema intrattabile.
Bibliografia:
- "Strutture, Linguaggi, Sintassi", F.Luccio, Boringhieri
- "Algoritmi, strutture dati, programmazione ad oggetti", P.Camagni, Hoepli - appunti personali …
