Grafi e alberi: la struttura su cui poggiano la ricerca e le reti neurali

Vertici e archi, gradi, matrice di adiacenza, cammini e componenti, BFS e Dijkstra, alberi, albero ricoprente minimo e grafo computazionale di un neurone — tutto su un solo grafo con sette città.

14 minuti Matěj Žalmánek 2026-10-15

Serie Basi di IA Parte 8 di 52

1. Mappa dell’intelligenza artificiale: che cos’è ciascuna cosa e come si incastra tutto
2. Breve storia dell’intelligenza artificiale: da Turing ai modelli linguistici
3. Dati, modello, addestramento, inferenza: i concetti di base su un unico esempio
4. Come leggere la notazione matematica: simboli, indici, sommatorie e quantificatori
5. Insiemi e relazioni: i mattoncini con cui si costruiscono le definizioni nell’IA
6. Funzioni e applicazioni: perché ogni modello di IA è una funzione
7. Logica e dimostrazioni: le regole con cui si ragiona nell’IA
8. Grafi e alberi: la struttura su cui poggiano la ricerca e le reti neurali
9. Algebra lineare per l’apprendimento automatico: vettori, matrici e perché l’IA soprattutto moltiplica
10. Derivate, gradiente e regola della catena: come un modello capisce in quale direzione imparare
11. Discesa del gradiente: come impara un modello
12. Che cos’è la probabilità: dal lancio di un dado agli assiomi di Kolmogorov
13. Probabilità condizionata e teorema di Bayes: come cambiare una stima quando scopri qualcosa di nuovo
14. Variabile aleatoria e funzione di ripartizione: una sola funzione che dice tutto sulla distribuzione
15. Funzione di densità e funzione di massa: perché una variabile continua ha probabilità zero in un punto
16. Valore atteso, varianza e covarianza: dove si trova una distribuzione, quanto è larga e che cosa è legato a che cosa
17. Panoramica delle distribuzioni di probabilità: Bernoulli, binomiale, Poisson, uniforme, normale ed esponenziale
18. Legge dei grandi numeri e teorema del limite centrale: perché le medie si comportano in modo così prevedibile
19. Statistica e stima dei parametri: massima verosimiglianza, MAP e intervalli di confidenza
20. Teoria dell’informazione: entropia, entropia incrociata e divergenza KL — da dove vengono le funzioni di perdita
21. Ricerca nello spazio degli stati: BFS, DFS, UCS e A* con animazioni
22. Giochi e avversari: minimax, potatura alfa-beta e Monte Carlo tree search
23. Soddisfacimento di vincoli: backtracking, propagazione dei vincoli e AC-3 su un sudoku e una mappa delle regioni ceche
24. Logica e sistemi basati sulla conoscenza: concatenazione in avanti e all’indietro, risoluzione e sistemi esperti
25. Pianificazione: STRIPS, il mondo dei blocchi, euristiche dal rilassamento e pianificazione negli agenti IA
26. Ricerca locale e ricottura simulata: un commesso viaggiatore tra i capoluoghi di regione cechi
27. Algoritmi genetici: popolazione, incrocio, mutazione e selezione su uno zaino per l’escursione
28. Strategie evolutive e programmazione genetica: dalla regola di un quinto alla legge di Keplero
29. Ottimizzazione con colonie di formiche: come una traccia di feromone trova un percorso breve
30. Ottimizzazione a sciame di particelle: inerzia, esperienza propria ed esperienza dello sciame
31. Neuroevoluzione: evoluzione dei pesi e della forma delle reti neurali e l’algoritmo NEAT
32. Insiemi fuzzy e funzioni di appartenenza: come scrivere «un po’ caldo»
33. Logica fuzzy e probabilità: perché «un po’ caldo» non significa «probabilmente caldo»
34. Logica fuzzy: t-norme, implicazioni e regole SE–ALLORA
35. Controllo fuzzy: Mamdani e Sugeno, dal ventilatore al pendolo inverso su un carrello
36. Clustering fuzzy: l’algoritmo fuzzy c-means e i punti tra i cluster
37. Sistemi neuro-fuzzy (ANFIS): regole fuzzy che imparano dai dati
38. Catene di Markov: matrice di transizione, distribuzione stazionaria e PageRank
39. Modelli di Markov nascosti: l’algoritmo di Viterbi e il casinò disonesto
40. Reti bayesiane: perché l’erba è bagnata e che cosa significa per l’irrigatore
41. Filtro di Kalman: come stimare da misure imprecise dove si trova un’auto e a che velocità va
42. Tipi di apprendimento automatico: supervisionato, non supervisionato, semi-supervisionato e altri
43. Prompt, contesto e RAG: come dare a un modello le informazioni giuste
44. Autoencoder variazionali (VAE): immagini nuove da uno spazio latente continuo
45. Reti generative avversarie (GAN): il falsario contro il detective
46. Modelli di diffusione: come il rumore puro diventa un’immagine
47. Processi decisionali di Markov: stati, azioni, ricompense ed equazioni di Bellman
48. Q-learning e DQN: imparare il valore delle azioni, dalla tabella alla rete neurale
49. Policy gradient e PPO: imparare direttamente la politica
50. Come funziona un agente IA: un modello linguistico in un ciclo con strumenti
51. Programmare con agenti IA: incarico, test e controllo
52. Valutazione e sicurezza dei sistemi di IA: come misurare e come sorvegliare

Programma completo della serie 52 di 83 argomenti pubblicati

Una mappa di città e strade, una rete di amici, lo spazio degli stati di un gioco, una rete neurale e perfino il calcolo in cui si ottiene il gradiente — tutto questo è un grafo: punti collegati da linee. I grafi sono la struttura più universale dell’informatica e nell’intelligenza artificiale li incontri a ogni passo. Gli alberi ne sono il caso particolare più semplice e più utile.

Costruiremo l’intera parte su un solo grafo con sette città dalla A alla G e strade con la loro lunghezza. Su di esso mostreremo via via i gradi, come memorizzare un grafo, i cammini minimi e l’albero ricoprente minimo.

1. Che cos’è un grafo

Definizione — grafo

Un grafo è una coppia G = (V, E), dove V è un insieme finito di vertici ed E un insieme di archi.

In un grafo non orientato un arco è un insieme di due elementi {u, v}; in uno orientato è una coppia ordinata (u, v) — una freccia da u a v. Un grafo orientato è quindi una relazione su V.

Un grafo pesato ha in più una funzione w : E → ℝ, che associa a ogni arco un peso (lunghezza, costo, tempo).

2. Grado di un vertice

Definizione — grado e lemma delle strette di mano

Il grado deg(v) di un vertice v è il numero di archi che ne escono.

Teorema (lemma delle strette di mano). In ogni grafo non orientato vale ∑_{v ∈ V} deg(v) = 2 |E|.

La somma dei gradi è 2 + 4 + 4 + 4 + 4 + 4 + 2 = 24 e gli archi sono 12 — esattamente come dice il teorema. Il grado ha un significato pratico: in un social network è il numero di amici, sul web il numero di link, e i vertici con grado alto sono spesso i più importanti.

3. Come memorizzare un grafo nel computer

Il computer non vede un’immagine, gli servono numeri. Le forme usuali sono due:

• Matrice di adiacenza — una tabella |V| × |V|; nella cella (u, v) c’è il peso dell’arco, oppure 0. La domanda “c’è un arco?” è rapida, ma la memoria cresce come |V|².
• Lista di adiacenza — per ogni vertice, l’elenco dei suoi vicini. La memoria cresce solo come |V| + |E|, il che per i grafi sparsi (social network, mappa) fa un’enorme differenza.

La matrice è simmetrica rispetto alla diagonale — è il segno di un grafo non orientato. Nell’IA la matrice di adiacenza si usa nelle reti neurali su grafi, che imparano direttamente sui grafi (molecole, social network, rete stradale).

4. Cammini, cicli e connessione

Definizione — cammino, ciclo, connessione

Un cammino da u a v è una successione di vertici a due a due distinti u = v₀, v₁, …, v_k = v, in cui due vertici consecutivi sono sempre uniti da un arco. La sua lunghezza è k (il numero di archi), in un grafo pesato la somma dei pesi.

Un ciclo è un cammino che torna al vertice di partenza (almeno tre archi).

Un grafo è connesso se tra due vertici qualsiasi esiste un cammino. Le parti connesse massimali di un grafo sono le sue componenti connesse — e “stare nella stessa componente” è un’equivalenza, quindi le componenti formano una partizione di V.

5. Cammini minimi

Il problema “come arrivare più in fretta da A a G” è la ricerca di un cammino minimo — proprio ciò che facevano gli algoritmi della parte sulla ricerca nello spazio degli stati. Ma dipende da che cosa misuriamo.

Se ci interessa il numero di archi, basta la ricerca in ampiezza: prima i vicini di A, poi i loro vicini… Il numero sopra un vertice è la distanza da A in archi:

A G portano tre archi (per esempio A–B–E–G). Ma se contiamo la lunghezza delle strade, serve l’algoritmo di Dijkstra — prosegue sempre dal vertice più vicino non ancora chiuso. Il numero sopra un vertice ora è la distanza minima in chilometri, ed è evidenziato il cammino minimo verso G:

Il cammino minimo A–B–D–E–G ha quattro archi, quindi più del cammino a tre archi trovato da BFS, ma lunghezza solo 12. Il cammino A–B–E–G misurerebbe 4 + 7 + 3 = 14. Meno passi non significa un cammino più corto — è esattamente la differenza tra BFS e UCS che abbiamo visto nel labirinto con il fango.

6. Alberi

Definizione — albero e albero radicato

Un albero è un grafo connesso senza cicli. Una foresta è un grafo senza cicli (ogni sua componente è un albero).

Teorema. Per un grafo con n vertici sono equivalenti: (1) è un albero; (2) è connesso e ha n − 1 archi; (3) non ha cicli e ha n − 1 archi; (4) tra due vertici qualsiasi esiste esattamente un cammino.

Un albero radicato ha un vertice distinto, la radice. I vicini di un vertice in direzione opposta alla radice sono i suoi figli, un vertice senza figli è una foglia e la profondità di un vertice è la lunghezza del cammino dalla radice.

Nell’IA gli alberi sono ovunque. Un albero di decisione classifica con una serie di domande dalla radice a una foglia. Gli algoritmi di ricerca costruiscono un albero di ricerca — l’albero di BFS e DFS della parte sulla ricerca è proprio questo. E un programma di scacchi calcola un albero di gioco, in cui i vertici sono posizioni e gli archi mosse.

7. Albero ricoprente minimo

Definizione — albero ricoprente e algoritmo di Kruskal

Un albero ricoprente di un grafo connesso G è un sottografo che contiene tutti i vertici di G ed è un albero. Un albero ricoprente minimo ha la minima somma dei pesi degli archi.

Algoritmo di Kruskal: ordina gli archi per peso crescente e aggiungi via via ognuno che non crea un ciclo. È un algoritmo goloso (greedy), eppure trova sempre l’ottimo.

L’albero ricoprente ha 6 archi per 7 vertici — esattamente n − 1, come dice il teorema sugli alberi — e una lunghezza totale di 18. Le sei strade rimanenti l’algoritmo le ha scartate, perché avrebbero creato un ciclo.

8. Grafi aciclici e il calcolo di una rete neurale

Definizione — DAG e ordinamento topologico

Un grafo orientato aciclico (DAG) è un grafo orientato senza cicli orientati.

Un ordinamento topologico è una disposizione dei vertici tale che ogni arco (u, v) vada da sinistra a destra — u sta prima di v. Teorema. Un grafo orientato ha un ordinamento topologico se e solo se è aciclico.

Così calcola ogni rete neurale. Ecco il calcolo di un singolo neurone ŷ = σ(w · x + b) e del suo errore L(ŷ, y) come grafo computazionale: gli input a sinistra, le operazioni come vertici, le frecce mostrano che cosa dipende da che cosa. I numeri sono l’ordine topologico:

La rete calcola in avanti nell’ordine topologico — prima il prodotto, poi la somma, la sigmoide e l’errore. E quando poi impara, percorre lo stesso grafo all’indietro: la retropropagazione dell’errore (backpropagation) attraversa i vertici nell’ordine topologico inverso e in ciascuno applica la regola della catena. Librerie come PyTorch costruiscono questo grafo da sole a ogni calcolo. Tra l’altro, anche il grafo delle dipendenze tra i moduli nel programma di questa serie è un DAG.

9. I grafi nell’intelligenza artificiale

• Lo spazio degli stati è un grafo: gli stati sono i vertici, le azioni archi con un costo. Cercare significa trovare un cammino in un grafo.
• I grafi computazionali delle reti neurali sono DAG; l’addestramento è un passaggio avanti e indietro.
• I grafi della conoscenza memorizzano fatti come archi “Praga — è la capitale di — Cechia” e i motori di ricerca ne ricavano le risposte.
• Le reti bayesiane sono DAG di dipendenze probabilistiche — ci arriveremo nel modulo sui modelli probabilistici.
• Le reti neurali su grafi imparano direttamente sui grafi: prevedono le proprietà delle molecole, il traffico o i consigli.

10. Riepilogo

• Un grafo è un insieme di vertici e archi; gli archi possono avere una direzione e un peso. La somma dei gradi è il doppio del numero di archi.
• Un grafo si memorizza con una matrice di adiacenza oppure con liste di adiacenza — molto più economiche per i grafi sparsi.
• BFS trova il cammino con meno archi, Dijkstra il più corto secondo i pesi — e non è detto che coincidano.
• Un albero è un grafo connesso senza cicli con n − 1 archi; l’albero ricoprente minimo lo trova l’algoritmo goloso di Kruskal.
• Una rete neurale è un DAG di calcolo: in avanti si calcola nell’ordine topologico, il gradiente all’indietro.

La vedi diversamente? Scrivi a support@coden-app.com.