Eulero e i ponti di Koenigsberg: la nascita della teoria dei grafi

Eulero e i ponti di Königsberg

D. Lenzi

Leonardo Eulero e i ponti di Königsberg

La nascita della teoria dei grafi

di

Domenico Lenzi

In corso di stampa su Lettera Matematica Pristem 1

Eulero_ponti D. Lenzi

La nascita della teoria dei grafi si può far risalire alla prima metà del XVIII secolo. Non che precedentemente non si fosse mai ragionato in termini di grafi; solo che una presa di coscienza dell’importanza di tale teoria come disciplina matematica si ebbe in quel periodo grazie ad Eulero (Leonhard Euler) che risolse un importante problema di cui parleremo più avanti. Comunque, come Eulero fa presente all’inizio di [E], il primo studioso che parlò di questo genere di matematica fu Leibniz (1646-1716). Però la ricerca in teoria dei grafi restò limitata agli studi di Eulero per circa un secolo, e solo dopo la prima metà del XIX secolo gli studi relativi a questa importantissima disciplina ripresero nuovamente, specialmente in Inghilterra, grazie a molti problemi scientifici che furono formulati usando la teoria dei grafi.

Eulero nacque a Basilea, in Svizzera, nel 1707 e fu allievo di Johann Bernoulli (1667-1748) (da molti considerato l’inventore del Calcolo delle variazioni) che a sua volta generò Nicolaus (1695-1726) e Daniel Bernoulli (1700-1782), dando origine a una ineguagliabile dinastia di scienziati.

Figlio d’arte, infatti suo padre aveva studiato matematica sotto la guida di Jakob Bernoulli (1654-1705), fratello di Johann, si può dire che Eulero abbia dato contributi eccellenti in ogni settore della matematica conosciuta al suo tempo. A dire il vero il padre di Eulero, che era un sacerdote protestante, aveva sperato a lungo che il giovane seguisse le sue orme, ma invano; infatti Leonardo preferì dedicarsi alla matematica, anche se studiò in modo approfondito molte altre discipline scientifiche, come medicina, astronomia, fisica e altre ancora.

Intanto Nicolaus e Daniel Bernoulli erano diventati professori di matematica presso l’Accademia di San Pietroburgo, fondata da Caterina I, vedova di Pietro il Grande. E nel 1727, su raccomandazione di Daniel Bernoulli (Nicolaus era morto qualche mese prima), Eulero fu chiamato come membro dell’Accademia per la sezione di medicina e fisiologia; però nel 1733 egli divenne responsabile della sezione matematica, dopo che Daniel Bernoulli ebbe lasciato l’Accademia per una cattedra di matematica a Basilea.

Eulero restò a San Pietroburgo fino al 1741, anno in cui accettò un invito di Federico il grande per l’Accademia di Berlino, dove rimase per venticinque anni. Ma ad un certo punto i rapporti con Federico – che preferiva gli studi filosofici – divennero difficili e nel 1766 Eulero riassunse il suo vecchio incarico presso l’Accademia di San Pietroburgo, sotto il regno di Caterina II, vedova di Pietro III.

Eulero durante la sua vita pubblicò più di 500 libri e articoli, nonostante nel 1766 fosse diventato completamente cieco; inoltre lasciò moltissimi manoscritti, che hanno portato il numero delle sue pubblicazioni intorno a quota 900. Egli morì improvvisamente nel 1783, all’età di settantasei anni. D. Lenzi

www.matematicamente.it 2

Eulero_ponti D. Lenzi

1. Il problema dei ponti di Königsberg

Si narra che gli abitanti di Königsberg – una città della Prussia orientale nota per aver dato i natali a Immanuel Kant e che oggi col nome di Kaliningrad è una parte del territorio della Repubblica Russa completamente circondata da quella che ormai si va delineando come la nuova Comunità Europea – avessero un problema semplice da enunciare, che però non si riusciva a risolvere, anche se i numerosi tentativi operati facevano propendere per una risposta negativa. E se non ci fosse stato il genio di Eulero, si era nel 1735, il quesito sarebbe rimasto insoluto ancora per molti decenni. Eulero dimostrò che il problema non era risolubile, fornendo una condizione necessaria di risolubilità per problemi di quel genere. Il risultato fu presentato all’Accademia di San Pietroburgo nell’agosto del 1736 e pubblicato in [E].

Ed ecco il problema dei ponti di Königsberg. La città è attraversata dal fiume Pregolya, e un suo quartiere sorge su di un’isola (chiamata der Kneiphof) oltre la quale il fiume si spezza in due rami. A quei tempi l’isola era collegata tramite due ponti con ciascuna delle due sponde che il fiume ha prima di suddividersi, mentre la sponda situata dopo la suddivisione del fiume era collegata con un ponte sia con l’isola sia con le sponde citate precedentemente, per un totale di sette ponti (si veda la seguente Fig. 1, riprodotta da p. 2 di [E]).

È chiaro che lungo i ponti della città tedesca, come in altre situazioni analoghe, si possono compiere delle passeggiate, dei cammini caratterizzati, ovviamente, dal fatto che in essi i ponti vengono percorsi l’uno dopo l’altro, facendo seguire ad ogni ponte un altro collegato ad esso tramite l’isola o tramite una sponda. Passeggiate nelle quali un ponte non venga percorso più di una volta sono detti semplici (cammini semplici). Ebbene, gli abitanti di Königsberg si domandavano se fosse possibile compiere un cammino semplice lungo i ponti della città in modo tale da percorrerli tutti.

www.matematicamente.it 3

Eulero_ponti D. Lenzi

Fig. 1

Vediamo cosa Eulero scrive a p. 129 di [E] (oppure si veda [E], p. 2) a proposito del problema di Königsberg:

A Königsberg in Prussia c’è un’isola A, chiamata der Kneiphof, e il fiume che la circonda si divide in due rami, come si può vedere in figura; i rami di questo fiume sono muniti di sette ponti a, b, c, d, e, f, g.

Circa questi ponti veniva posta questa domanda, si chiedeva se fosse possibile costruire un percorso in modo da transitare attraverso ciascun ponte una e una sola volta. E mi fu detto che alcuni negavano ed altri dubitavano che ciò si potesse fare, ma nessuno lo dava per certo.

Da ciò io ho tratto questo problema generale: qualunque sia la configurazione e la distribuzione in rami del fiume e qualunque sia il numero dei ponti, si può scoprire se è possibile passare per ogni ponte una ed una sola volta?

È chiaro che anche le sponde del fiume avrebbero potuto essere delle isole, senza che di fatto il problema risultasse alterato. Inoltre, invece di un fiume, si sarebbe potuto avere a che fare con un mare. Quindi un aggiustamento ed una prima generalizzazione della situazione illustrata precedentemente si ha considerando un arcipelago e dei ponti che collegano alcune delle isole. Naturalmente, ci possono essere coppie di isole che non sono collegate direttamente da alcun ponte; inoltre non si esclude che ci possano essere anche dei ponti panoramici, che partono da un’isola e arrivano su quell’isola stessa.

www.matematicamente.it 4

Eulero_ponti D. Lenzi

2. Un utile “strumento” didattico