Una rete stradale, gli amici su un social network, le dipendenze tra i pacchetti di un progetto software, i collegamenti tra pagine web: sono oggetti molto diversi, ma hanno la stessa struttura. Ci sono delle cose e delle relazioni tra coppie di cose. La matematica chiama questa struttura grafo, e una parte enorme dell'informatica pratica consiste nel riconoscere un grafo dentro un problema che a prima vista sembra tutt'altro.
La definizione essenziale
Un grafo G è una coppia (V, E):
- V è l'insieme dei vertici (o nodi): le città, le persone, i file;
- E è l'insieme degli archi (o spigoli): ogni arco collega due vertici.
Se le città sono Milano, Bologna e Firenze e ci sono strade Milano–Bologna e Bologna–Firenze, allora V = {Milano, Bologna, Firenze} ed E = {{Milano, Bologna}, {Bologna, Firenze}}. Niente di più: il grafo non conosce le coordinate, la lunghezza delle strade o il paesaggio. Conosce solo chi è collegato a chi. Tutto il resto, se serve, si aggiunge come informazione extra.
Di solito si indica con n il numero di vertici e con m il numero di archi. Queste due quantità compaiono in tutte le stime di costo degli algoritmi sui grafi.
Grado, vicini e cammini
Due vertici collegati da un arco si dicono adiacenti, o vicini. Il grado di un vertice è il numero di archi che lo toccano. Nell'esempio, Bologna ha grado 2, Milano e Firenze grado 1.
Un fatto semplice ma utilissimo: la somma dei gradi di tutti i vertici è uguale al doppio del numero di archi, perché ogni arco viene contato una volta per ciascuno dei suoi due estremi. Ne segue che il numero di vertici di grado dispari è sempre pari. È un controllo rapido per scoprire errori nei dati: se in una rete non orientata trovate un numero dispari di nodi con grado dispari, qualcosa nel caricamento è andato storto.
Un cammino è una sequenza di vertici in cui ogni coppia consecutiva è collegata da un arco. Un ciclo è un cammino che torna al punto di partenza senza ripetere archi. Un grafo è connesso se esiste un cammino tra ogni coppia di vertici.
I tipi di grafo che incontrerete più spesso
Orientati e non orientati
In un grafo non orientato l'arco {A, B} vale nei due sensi: se Anna è amica di Bruno, Bruno è amico di Anna. In un grafo orientato (o digrafo) gli archi hanno un verso: (A, B) va da A a B e non viceversa. «Segue» su un social, «importa» tra moduli software, «rimanda a» tra pagine web sono relazioni orientate. Nei digrafi si distinguono grado entrante e grado uscente.
Pesati
Spesso a ogni arco si associa un numero: la lunghezza di una strada, il tempo di percorrenza, il costo di un collegamento, la capacità di un tubo. Si parla allora di grafo pesato. Gran parte dei problemi di ottimizzazione sui grafi, come il cammino minimo o l'albero ricoprente di costo minimo, ha senso solo con i pesi.
Semplici e multigrafi
Un grafo semplice non ha archi multipli tra la stessa coppia di vertici né cappi (archi da un vertice a sé stesso). Un multigrafo li ammette: due linee ferroviarie distinte tra le stesse due stazioni sono un esempio naturale.
Alberi, DAG e bipartiti
- Un albero è un grafo connesso senza cicli; con n vertici ha esattamente n − 1 archi. Le cartelle di un file system ne sono l'esempio classico.
- Un DAG (grafo orientato aciclico) è un digrafo senza cicli orientati. Le dipendenze di compilazione e i fogli di calcolo con formule devono formare un DAG, altrimenti c'è un riferimento circolare.
- Un grafo bipartito ha i vertici divisi in due gruppi, con archi solo tra gruppi diversi: lavoratori e turni, studenti e corsi, utenti e prodotti acquistati.
Grafi densi e sparsi
In un grafo semplice non orientato con n vertici ci possono essere al massimo n(n − 1)/2 archi. Quando m è vicino a questo massimo il grafo è denso; quando m è dello stesso ordine di n il grafo è sparso. Quasi tutti i grafi reali sono sparsi: una persona conosce qualche centinaio di altre persone, non miliardi; un incrocio stradale ha in genere tre o quattro strade, non migliaia. Questa osservazione guida la scelta di come rappresentare il grafo in memoria e di quale algoritmo usare.
Riconoscere un grafo in un problema
Nel mio lavoro il passo più utile è spesso il primo: tradurre il problema. Qualche esempio:
| Problema | Vertici | Archi |
|---|---|---|
| Ordine di installazione dei pacchetti | Pacchetti | «A richiede B» (orientato) |
| Orario degli esami senza sovrapposizioni | Esami | «hanno studenti in comune» |
| Navigatore satellitare | Incroci | Tratti di strada (pesati) |
| Analisi di un'intrusione nei log | Host e account | Connessioni e accessi osservati |
Una volta fatta la traduzione, si possono usare decenni di algoritmi già studiati, invece di inventare una soluzione ad hoc.
In sintesi
- Un grafo è formato da vertici e archi; descrive solo chi è collegato a chi.
- Grado, cammino, ciclo e connessione sono i concetti di base su cui si costruisce tutto il resto.
- Orientato, pesato, bipartito, albero e DAG sono le varianti più frequenti nei problemi reali.
- La maggior parte dei grafi reali è sparsa, e questo influenza rappresentazione e algoritmi.
- Riconoscere il grafo nascosto in un problema è spesso metà della soluzione.
