La magia dei Grafi.

Messa la teoria degli insiemi al sicuro della nostra borsa del matematico, non possiamo non introdurre un nuovo, potentissimo strumento: i grafi.

Un grafo è un oggetto matematico piuttosto semplice, ma che consente di modellare problemi complessi. La branca della matematica che studia i grafi è parte della matematica combinatoria, e va sotto il nome di Teoria dei Grafi. I grafi rappresentano uno strumento potentissimo per rappresentare modelli applicabili nei contesti più disparati, come la topologia, la teoria degli automi alla base dell’informatica moderna, problemi di organizzazione aziendale e tanto altro.

Ad esempio il vostro navigatore satellitare funziona proprio grazie alla teoria dei grafi. Anche il linguaggio umano è rappresentabile mediante grafi, così come i circuiti alla base di tutta la componentistica elettronica. Fare un elenco esaustivo degli oggetti della tecnologia moderna funzionanti grazie alla teoria dei grafi è davvero impossibile.

Informalmente, il grafo è costituito da una serie di nodi connessi da archi. Ogni nodo può rappresentare una qualsiasi entità del mondo reale. Gli archi, invece, legando due nodi possono essere visti in diversi modi.

Ecco un esempio notevole di grafo, la Metropolitana di Parigi (clicca per ingrandire):

Grafi e teoria degli insiemi vanno, ovviamente, a braccetto. Il sistema più semplice per modellare i nodi di un grafo è proprio l’insieme. Gli archi, invece, che legano due nodi, possono essere efficacemente rappresentati da relazioni.

Ricordate il diagramma della relazione genitori-figli ? Anche quello è un grafo, il cui insieme dei nodi è definito come segue:

NODI = {Paolo, Maria, Francesco, Marco, Mirko, Sara}

e quello degli archi:

ARCHI = {(Paolo, Marco), (Paolo,Mirko), (Maria, Marco), (Maria, Mirko), (Francesco,Sara)}

il grafo della relazione genitori figli ha una particolarità: gli archi possono essere letti in una sola direzione, cioé l’arco tra Paolo e Marco può andare solamente nella “direzione” di Marco. Grafi di questo genere sono detti grafi orientati.

Il grafo della metropolitana di Parigi non è, invece, orientato perché l’utente si può muovere da e verso una qualsiasi coppia di nodi attraverso lo stesso arco che li connette.

In teoria dei grafi, la sequenza di archi che connettono due nodi generici è detta cammino. Esempi di cammino nel grafo della metro parigina sono le singole linee del metro. La linea 1, ad esempio, è modellabile mediante un cammino che va dal nodo  “La Defense” al nodo “Château de Vincennes”, i due capolinea, appunto.

In post successivi, vedremo quali magie si possono fare usando un grafo come modello …