Sesta puntata: grafi

Un grafo è un'entità matematica molto semplice, ma sorprendentemente utile. Si tratta di un insieme di oggetti (chiamati "nodi" o "vertici") che sono collegati fra loro da "archi".

Un esempio di grafo è costituito dalla mappa di una metropolitana: in questo caso i nodi sono le stazioni e gli archi sono i tratti che le collegano; ogni arco ha due estremità (le due stazioni che l'arco collega). Nel caso della metropolitana, un passeggero può spostarsi lungo gli archi in qualunque direzione e può effettuare percorsi che lo portano da una stazione all'altra attraversando uno o più archi. Ci sono anche situazioni in cui gli archi sono orientati, cioè possono essere percorsi in un solo verso: è ciò che accade, ad esempio, nelle mappe stradali cittadine quando si incontrano strade a senso unico.

I grafi rappresentano un formalismo di grandissima potenza espressiva, molto utilizzato in matematica e in informatica: è questo l'argomento della puntata di lunedì. Prenderemo in esame molti esempi di grafo (dalle amicizie su Facebook al World Wide Web) e spiegheremo quanto avere un formalismo così generale possa essere utile nella pratica. Anche, ad esempio, per organizzare una cena...

Chi si è perso la diretta può scaricare la puntata in formato MP3 e OGG.

Commenti