Vorrei sapere in quale campo informatico e in che modo trovano applicazione i grafi (e gli alberi), e più in generale la teoria dei grafi.

Alcune definizioni:

Un grafo è formato da un insieme di nodi collegati mediante archi. Non
esiste una gerarchia tra i nodi e non ci sono restrizioni sui loro
collegamenti e
rappresentazione grafica.

Un cammino in un grafo è un attraversamento dei nodi attraverso gli archi,
il costo è dato dal numero di archi attraversati. Se il primo e il secondo
nodo
coincidono il cammino si chiama ciclo. Se gli archi hanno un orientamento
allora il grafo si dice orientato, altrimenti il grafo si dice non
orientato.

Un grafo non orientato si dice connesso se esiste un percorso che unisce
ogni coppia di nodi, altrimenti si dice non connesso.
Il nodo X è un nodo successore di Y se c’è un arco entrante in X e
proveniente da Y, che si dice predecessore di X.

Il problema dei ponti di Koenigsberg proposto da Eulero nel 1736 ha dato
l’avvio alla teoria dei grafi. Un’altra interessante applicazione dei grafi
consiste
nel colorare una qualsiasi carta geografica utilizzando soltanto quattro
colori in modo tale che due nazioni confinanti non abbiano mai lo stesso
colore.

Allo stesso modo trovano applicazione per modellare tanti problemi di
ricerca operativa. Per esempio, la teoria dei grafi viene impiegata per
calcolare il
cammino minimo per raggiungere ogni nodo a partire da un nodo sorgente,
oppure per calcolare il massimo flusso su un grafo. Il problema del commesso
viaggiatore viene studiato con la teoria dei grafi. In un grafo ogni nodo
corrisponde ad una città e l’insieme degli archi corrisponde alle strade che
collegano coppie di città. Ad ogni strada è associato un costo derivante
dalla distanza, dal tempo di percorrenza, dal pedaggio. Il problema consiste
nel
trovare un cammino che passa per tutte le città una sola volta in modo che
il suo costo sia minimo.

Un albero è un grafo connesso orientato senza cicli. La radice è il nodo
senza alcun predecessore, i nodi successori si chiamano figli, mentre il
nodo
predecessore si dice padre. Due nodi che abbiano lo stesso padre vengono
detti fratelli. Un nodo senza successori viene detto foglia. La
rappresentazione grafica dell’albero, quindi, ha un ruolo importante e
prevede che i nodi siano collocati secondo vari livelli.

Nell’albero esiste sempre un cammino unico che unisce un qualsiasi nodo
foglia con il nodo radice: tale cammino si dice ramo.

Nell’albero binario ogni nodo può avere al massimo 2 figli.
L’albero ha molte applicazioni in informatica: memorizza informazioni
secondo un certo ordine gerarchico per farne una ricerca rapida tramite
algoritmi di
visita dei nodi, rappresenta un’espressione aritmetica con nodi che indicano
le operazioni e foglie che indicano gli operandi, rappresenta la struttura
dei processi in esecuzione nel sistema operativo, ecc.

Per approfondimenti sulla teoria dei grafi si veda:


http://www.matematicamente.it/approfondimenti/grafi.htm

Per approfondimenti sul problema posto da Eulero:


http://www.matematicamente.it/libri/euler.htm


http://www.matematicamente.it/storia/Eulero_ponti.pdf

Un esempio di applicazione e


http://www.vialattea.net/esperti/php/risposta.php?num=2288

Altre informazioni sono presenti in tutti i libri di informatica generale o
sulle strutture dati.