Su queste tre piantine (la prima, la seconda, la terza) sono indicati, con vari colori, alcuni itinerari turistici per Milano.

Il problema posto nei tre casi è lo stesso: è possibile, partendo da un punto qualsiasi di un itinerario, percorrerne tutti i tratti senza staccare la matita dal foglio e senza ripassare mai su strade già percorse?
Dopo qualche tentativo di soluzione, sembra naturale rispondere che alcune volte è possibile e altre no. Perché?

È abbastanza evidente che i vincoli che possono portare all'impossibilità non sono legati alla lunghezza o alla disposizione dei tratti di strada, ma piuttosto a quanti sono, e di che tipo, i punti in cui si incontrano diverse strade (se in un dato incrocio si incontrano tre strade, oppure quattro, o cinque, o sei, o anche di più). Ogni volta che arriviamo ad un incrocio, dobbiamo poi uscirne percorrendo un tratto di strada diverso da quello di entrata. Perciò, se vogliamo finire la passeggiata nello stesso punto dal quale siamo partiti, in ogni incrocio devono confluire un numero pari di strade (nel seguito, chiameremo questi punti incroci pari). Se invece punto di arrivo e di partenza sono diversi, allora in questi due punti devono confluire un numero dispari di strade: dal punto di partenza dovremo uscire una prima volta, e poi entrare e uscire un certo numero di volte, e analogamente in quello di arrivo. Questi percorsi comprenderanno quindi due incroci dispari, ma tutti gli altri incroci saranno pari. Nell'itinerario rosso ci sono quattro incroci dispari, quindi non è possibile percorrerlo senza ripetere qualche tratto di strada, neanche finendo la passeggiata in un punto diverso da quello di partenza. In quello blu ci sono due incroci dispari: se è possibile percorrerlo senza ripetizioni, dovremo necessariamente partire da uno di essi e arrivare nell'altro; nell'itinerario verde, tutti gli incroci sono pari: possiamo quindi sperare di riuscire a percorrerlo partendo da un punto qualsiasi.

In effetti non si tratta solo di una speranza, ma si può dimostrare che per itinerari come quello blu o quello verde esiste sempre una passeggiata senza ripetizioni, ed esiste anche un semplice algoritmo per trovarne una.

Problemi di questo tipo vengono schematizzati con dei grafi, che sono formati da punti (i vertici del grafo) uniti da delle linee (gli spigoli del grafo): nei nostri esempi, i vertici corrispondono agli incroci e gli spigoli ai tratti di strada. In un grafo, ciò che conta è solo il tipo di connessione (cioè quali vertici sono collegati da quali spigoli), mentre non hanno alcuna importanza la posizione dei vertici e la lunghezza degli spigoli, o se questi sono diritti o curvi. I problemi proposti all'inizio, che equivalgono a stabilire se è possibile disegnare il grafo corrispondente senza mai sollevare la matita dal foglio e segnando ogni linea una sola volta, sono pertanto di carattere topologico; in effetti, spesso si fa risalire l'origine della topologia proprio a un celebre problema, quello dei ponti di Königsberg, di cui quelle presentate qui sono delle versioni “milanesi”.

Königsberg è l'antico nome di una città prussiana attraversata da un fiume nel quale ci sono due isole, collegate tra loro e alla terraferma da alcuni ponti. All'inizio del 1700 i suoi abitanti si chiesero se fosse possibile fare una passeggiata partendo da un punto qualsiasi della città e percorrendo tutti e sette i ponti allora esistenti una sola volta. Il matematico Eulero schematizzò il problema con un grafo, in cui i quattro vertici corrispondono alle zone della città (le due isole e le due rive del fiume) e i sette spigoli ai ponti che le congiungono. Fare un giro per la città attraversando una sola volta ciascuno dei sette ponti equivale al problema precedente: la passeggiata si può schematizzare con un grafo che ha quattro vertici dispari, dunque non è possibile percorrerlo come voluto. Lo stesso grafo si ritrova nel poster della mostra matemilano.

La teoria dei grafi, di cui Eulero pose le basi, si è sviluppata soprattutto dalla metà del secolo scorso ed ha numerose applicazioni in ricerca operativa, una branca della matematica che si occupa di problemi quali razionalizzare processi industriali, ottimizzare reti di distribuzione, gestire efficacemente un'impresa…
Spesso risolvere questi problemi è molto difficile; talvolta, poi, si conoscono solo degli algoritmi per trovare una soluzione, ma non si sa decidere se questa sia la migliore possibile: la loro complessità computazionale è così elevata che ci vorrebbe un numero enorme di anni affinché un calcolatore possa trovare una risposta.