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

Eulero e i ponti di Koenigsberg 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 Eu-

lero (Leonhard Euler) che risolse un importante problema di cui parle-

remo 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 nuova-

mente, 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’Ac-

a

, vedova di Pietro il Grande. E nel 1727, su

cademia di San Pietroburgo, fondata da Caterina I

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 riassun-

se 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 diven-

tato 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 Ka-

liningrad è una parte del territorio della Repubblica Russa completa-

mente 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 fa-

cevano propendere per una risposta negativa. E se non ci fosse stato il

genio di Eulero, si era nel 1735, il quesito sarebbe rimasto insoluto an-

cora per molti decenni. Eulero dimostrò che il problema non era risolu-

bile, 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’i-

sola era collegata tramite due ponti con ciascuna delle due sponde che il

fiume ha prima di suddividersi, mentre la sponda situata dopo la suddi-

visione 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

1, riprodotta da p. 2 di [E ]).

seguente Fig. 1

È chiaro che lungo i ponti della città tedesca, come in altre situazioni

analoghe, si possono compiere delle passeggiate, dei cammini caratte-

rizzati, 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 sem-

plici). Ebbene, gli abitanti di Königsberg si domandavano se fosse pos-

sibile 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

1

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 figu-

ra; 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 cia-

scun 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 confi-

gurazione e la distribuzione in rami del fiume e qualunque sia il nume-

ro 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 ag-

giustamento ed una prima generalizzazione della situazione illustrata

precedentemente si ha considerando un arcipelago e dei ponti che colle-

gano alcune delle isole. Naturalmente, ci possono essere coppie di isole

che non sono collegate direttamente da alcun ponte; inoltre non si e-

sclude 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

Ora si considerino arcipelaghi particolari, che diciamo a ponti connes-

si, nei quali due qualsiasi ponti si possano congiungere con un cam-

mino che percorra in maniera opportuna alcuni ponti d