I rompicapi di Alice: Il problema dei servizi

"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⁽¹⁾ 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⁽¹⁾, 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⁽⁴⁾.
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⁽³⁾.
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⁽³⁾.

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⁽³⁾:

Ad ogni modo il problema dei servizi è equivalente alla ricerca dei reticoli euleriani, ovvero di quelle figure planari chiuse che possono essere disegnate senza mai staccare la penna dal foglio e senza mai passare più di una volta sugli stessi nodi. Uno dei primi risultati in tal senso è fornito dal matematico polacco Kazimierz Kuratowski⁽²⁾ che dimostrò che un dato grafo è planare (e quindi il suo reticolo corrispondente è euleriano) se non contiene alcun sottografo riconducibile ai grafi $K_5$ e $K_{3,3}$, che invece non sono planari. Kuratowski utilizzò per la sua dimostrazione dei grafi riconducibili esplicitamente a delle figure geometriche nello spazio, ma le loro rappresentazioni planari potranno chiarire come questo risultato permette di dimostrare che il problema dei servizi è irresolubile⁽³⁾:

Proprio la disposizione geometrica permette una dimostrazione semplice dell'irresolubilità, escludendo una delle case: in questo modo partizioniamo il nostro spazio in due sottospazi e quindi, inevitabilmente una terza casa deve appartenere a uno dei due sottospazi costringendo un punto sulla linea di confine a dover tagliare uno dei tubi dei due servizi più esterni⁽⁵⁾.
Un altro modo di dimostrare la non risolubilità del rompicapo è passando attraverso la formula di Eulero sui solidi (di cui abbiamo visto una variazione nel caso di ...): \[F - E + V = 2\] dove $F$ è il numero di facce, $E$ il numero degli spigoli, $V$ il numero dei vertici.
Dal grafo relativo al problema dei servizi, si deduce che il numero dei vertici è 6, ovvero il numero dei nodi (le tre case e i tre servizi), mentre il numero degli spigoli è 9 (ovvero gli archi che collegano i nodi). Quindi dalla formula si scopre che il numero di facce deve essere 5. Ora, però, possiamo osservare che ciascun percorso chiuso all'interno del grafo $K_{3,3}$ può avere o 4 o 6 vertici, quindi una faccia sarà racchiusa almeno da 4 spigoli. Quindi, se le facce sono 5, il minimo numero totale di spigoli sarà 5*4/2=10⁽⁹⁾, che è in contraddizione con quanto ricavato con la formula di Eulero^{(4, 6, 7)}.
Una contraddizione analoga la si ricava se si ragiona invece in questo modo: ciascuna faccia contiene un numero di spigoli pari a $n$, quindi il numero totale di spigoli sarà dato da $E = nF/2$ (sempre per quanto scritto nella nota spigoli), quindi sostituendo nell'equazione di Eulero si ricava \[E= \frac{n (V-2)}{n-2}\] che per il grafo $K_{3,3}$ conduce a $E=8$, ancora una volta in contraddizione con il numero di spigoli che si possono contare sul grafo stesso⁽³⁾, e che guarda il caso coincide con il numero massimo di archi non intrecciati che si possono disegnare per il problema dei servizi.
Se però proviamo a risolvere il rompicapo su una geometria non planare, il problema dei servizi diventa "magicamente" risolubile. In particolare presenta una soluzione interessante, se non addirittura elegante, su una superficie toroidale^{(3, 8)}

Una variazione sui cammini (o reticoli) euleriani si trova, però, anche in altri interessanti rompicapi, come nel collegare gli elettrodomestici ciascuno alla sua presa specifica⁽⁴⁾

o nello scovare l'assassino nell'intricato giallo Il mistero di Ravensdene Park, ideato ancora una volta da Dudeney⁽⁴⁾ e pubblicato per la prima volta su The Canterbury Puzzles

o come nel rompicapo dei tre quadrati proposto da Lewis Carroll a Isabel Standen il 21 agosto del 1869:

I reticoli euleriani, poi, sono anche alla base di molti giochi classificati di logica, come Flow Free o One Touch Crayon Drawing per Android o come il gioco in flash 3D Logic.

---

(1) Leonard Euler. Solutio problematis ad geometriam situs pertinentis (pdf)
(2) Kuratowski, Casimir. "Sur le problème des courbes gauches en Topologie." Fundamenta Mathematicae 15.1 (1930): 271-283.
(3) Kullman D.E. (1979). The Utilities Problem, Mathematics Magazine, 52 (5) 299-302. DOI: 10.2307/2689782
(4) Ian Stewart (2010). La piccola bottega delle curiosità matematiche del Professor Stewart. La biblioteca delle Scienze
(5) Jim Loy: Impossible puzzle? part 2 (archive)
(6) Cut the Knot: 3 Utilities Puzzle
(7) Archimedes' Laboratory: The Water-Gas-and-Electricity Puzzle
(8) Weisstein, Eric W. "Utility Graph." From MathWorld--A Wolfram Web Resource.
(9) Si deve dividere per due per non contare due volte ciascuno spigolo: provare sul cubo

---

Vedi anche:
Il problema dei servizi su it.wiki ed en.wiki
Una divertente vignetta sui ponti di Konigsberg su Spiked Math