1. Che cos'è un grafo
Un grafo è una coppia (V, E) formata da un insieme di nodi V e da un insieme di archi E che collegano alcune coppie di nodi. È un'astrazione molto semplice, ma capace di descrivere una grande varietà di situazioni.
- nodi = persone, archi = relazioni di amicizia (social network);
- nodi = città, archi = strade o tratte ferroviarie (rete di trasporto);
- nodi = moduli o pacchetti software, archi = dipendenze (chi usa cosa).
Possiamo avere grafi orientati (gli archi hanno una direzione) o non orientati, con pesi sugli archi (costi, distanze, capacità) o senza pesi.
2. Modellare una rete reale
Il primo passo pratico è sempre scegliere come mappare un problema reale in nodi e archi. Ad esempio, per una piccola rete di città possiamo definire un nodo per ogni città e un arco per ogni collegamento diretto.
- V = {Milano, Torino, Genova, Bologna};
- E = {(Milano, Torino), (Milano, Genova), (Genova, Bologna)};
- ai lati possiamo associare una distanza in km come peso dell'arco.
Una volta che il problema è in forma di grafo, possiamo applicare algoritmi standard di teoria dei grafi, senza più preoccuparci del contesto specifico (trasporti, software, reti sociali...).
3. Cammini minimi e pesi
Uno dei problemi più classici sui grafi è quello del cammino minimo: trovare il percorso di costo totale minimo tra due nodi, dato un peso su ciascun arco (distanza, tempo di viaggio, costo economico...).
- supponiamo che la distanza Milano–Torino sia 140 km, Milano–Genova 150 km, Genova–Bologna 190 km;
- per andare da Torino a Bologna possiamo passare via Milano o via Genova;
- se c'è un arco Torino–Milano di 140 km e non c'è un collegamento diretto Torino–Bologna, un algoritmo di cammino minimo confronterà automaticamente i percorsi possibili.
Algoritmi come Dijkstra o Bellman-Ford permettono di trovare cammini minimi in grafi con pesi non negativi o, in alcune varianti, anche con pesi negativi (ma senza cicli negativi).
4. Centralità e importanza dei nodi
In molte applicazioni non ci interessa solo se due nodi sono collegati, ma anche quali nodi sono "centrali" o particolarmente importanti nella rete.
- grado di un nodo: quanti archi incidono su di esso (molto connesso o periferico?);
- centralità di intermediazione: quante volte un nodo cade su cammini minimi tra altre coppie di nodi;
- centralità basata su autovalori (tipo PageRank): l'importanza di un nodo dipende anche dall'importanza dei nodi collegati.
Queste quantità aiutano a identificare nodi critici in una rete elettrica, utenti influenti in un social, o moduli software altamente riutilizzati che meritano particolare attenzione in fase di manutenzione.
5. Grafi in Python
In Python esistono librerie dedicate alla teoria dei grafi (come NetworkX) che permettono di creare nodi e archi, assegnare pesi, e calcolare cammini minimi, centralità, componenti connesse e molto altro.
- definire il grafo a partire da dati (file CSV, database, log di dipendenze);
- calcolare alcune misure (gradi, cammini minimi, centralità);
- visualizzare la rete o esportare i risultati per analisi successive.
Una pagina dedicata potrà mostrare un piccolo esempio di rete software o di città, implementato in Python, con grafico dei cammini minimi e identificazione dei nodi più centrali.