`\begin{figure}[!h]
\begin{center}
\includegraphics[angle=0, scale=0.5]{images/pruning}
\caption{I due percorsi $\overrightarrow{AD}$ hanno lunghezza $n+s+q*$: per questo motivo se $q1>q2$, il percorso con lunghezza $n+s+q1$ verr\`a potato}\label{prun}
\end{center}
\end{figure}`
Se si usa una didascalia breve, che va nell’elenco delle figure, si elimina il problema del comando fragile. Oltretutto, una didascalia come quella nell’elenco delle figure ci starebbe davvero male. Ti propongo:
`\begin{figure}[tb]
\centering
\includegraphics[width=0.5\textwidth]{pruning}
\caption[Un esempio di non so che cosa]{I due percorsi $\overrightarrow{AD}$ hanno lunghezza $n+s+q*$: per questo motivo, se $q1>q2$ il percorso con lunghezza $n+s+q1$ verrà tagliato.}
\label{fig:prun}
\end{figure}`
Ho fatto diverse correzioni al il tuo codice.
http://www.lorenzopantieri.net/LaTeX_files/ArteLaTeX.pdf
Paragrafo sulle figure e appendice B.
Ciao,
L.
P.S. Battuto sul tempo da Enrico! 😉