"Inizia dall'inizio", disse il Re con gravità, "e vai fino a che non arrivi alla fine; quindi fermati"
Lewis Carroll da Alice nel Paese delle Meraviglie
La teoria dei grafi inizia con la risoluzione di un problema di geometria reale. Il geniale matematico svizzero
Eulero, infatti, propose in un famoso articolo
(1) la soluzione di un rompicapo basato sulla città di Konigsberg e i suoi sette ponti:
(via David Galvin - pdf)
la cittadina prussiana è tagliata dal fiume Pregel al cui centro si trovano due isole raggiungibili attraverso sette ponti; è dunque possibile trovare un percorso chiuso (punto di inizio e punto di fine coincidono) in grado di attraversare tutti i sette ponti una e una sola volta?
All'interno dell'articolo
(1), arricchito anche di precise illustrazioni, Eulero sviluppa le basi di quella che sarà la meglio nota teoria dei grafi, e che può essere così riassunta:
Un
grafo, o
reticolo, è una figura bidimensionale caratterizzata da due elementi: i
nodi, ovvero dei punti di passaggio obbligatori, e gli
archi, ovvero le linee che congiungono i nodi. I primi si distinguono tra
nodo pari, ovvero un punto in cui converge un numero pari di archi, e
nodo dispari, ovvero un punto in cui converge un numero dispari di archi. Un
reticolo euleriano è, quindi, un reticolo contenente nodi pari o al più due nodi dispari. Un reticolo euleriano è completamente percorribile (e può essere disegnato) senza mai staccare la penna dal foglio, partendo da un dato nodo e finendo alla fine su di esso. Si distinguono, poi, due generi di reticoli euleriani: quello
chiuso e quello
aperto, dove per chiuso si intende un reticolo che inizia e finisce sullo stesso nodo, mentre uno aperto che inizia e finisce su un nodo differente. Si avrà un reticolo chiuso quando tutti i nodi sono pari, si avrà un cammino aperto quando ci saranno due nodi dispari, uno come partenza della nostra camminata lungo il reticolo e l'altro come conclusione. Eulero dimostrò che nel caso di Konigsberg il reticolo era (e
continua ad esserlo ancora oggi, nonostante l'aggiornamento dei ponti) né aperto né chiuso, rispondendo quindi negativamente alla domanda iniziale
(4).
Il problema dei servizi, che mi venne posto qualche anno fa, è anch'esso uno di quei problemi o rompicapi che può essere analizzato utilizzando la teoria dei grafi; questo un suo possibile enunciato:
Bisogna collegare, su una superficie planare, tre case ai tre servizi essenziali di acqua, luce e gas senza che i tubi di collegamento si intersechino tra loro.
Apparentemente questo problema è di facile risoluzione e presenta tutta una serie di rompicapi equivalenti (il più truculento è quello detto della vendetta Corsa), ma la sua prima risoluzione, così come ci è stata tramandata, su carta stampata risale al 1917 e porta la firma di
Henry Ernest Dudeney, sulle pagine del suo
Amusements in Mathematics. Il rompicapo, però, sembra fosse noto ben prima di Dudeney: secondo
Sam Loyd jr., il padre lo aveva scoperto già nel 1900, ma non lo aveva inventato lui, come anche molti storici della matematica sostengono
(3).
In effetti un problema topologicamente simile ci è stato tramandato direttamente dall'antica Persia:
Un califfo era così turbato dal gran numero di pretendenti, che decise di istituire un concorso per stabilire chi era più qualificato a sposare la figlia. Nel turno di qualificazione, agli aspiranti veniva mostrato un disegno di due urne, ciascuna con tre maniglie numerate 1, 2, e 3 da cima a fondo. Gli veniva quindi richiesto di unire 1 con 1, 2 con 2, e 3 con 3 utilizzando curve che non si intersecano tra loro o che attraversano le urne. Questo compito non era così difficile, ma figlia di un califfo non può essere vinta così facilmente. Il padre, quindi, ha insistito affinché ogni corteggiatore che ha superato il primo turno debba competere anche in una finale. Anche questa volta venivano disegnate le stesse urne, ma i numeri sulle maniglie della seconda urna erano in ordine inverso(3).
In questo caso il problema della figlia del califfo (o almeno la parte relativa alle finali) risulta equivalente al problema dei servizi, anche nella soluzione, visto che si narra in giro che la figlia del califfo morì zitella. Infatti, pur nella sua apparente semplicità, il rompicapo risulta irrisolvibile. Infatti se si collegano due case con tutti e tre i servizi, si arriva a constatare quasi con un certo imbarazzo che la stessa cosa non la si può fare con la terza casa. A meno di non...
barare, proprio come fece Dudeney
(3):