Era il 1995, e al cinema una quasi sconosciuta Sandra Bullock interpretava “The Net” (titolo italiano: Intrappolata nella rete), il primo film in cui Internet abbia rivestito un ruolo da protagonista. L'estate precedente, al ritorno dalle vacanze, nel mio istituto avevano installato il browser Mosaic, il nonno di Firefox, con cui si poteva provare l'ebbrezza di aprire le poche pagine disponibili con qualche immagine nel nuovo (per allora) formato jpeg, e che ci mettevano anche vari minuti a caricarsi. Tutto era cominciato però vari millenni prima con le reti da pesca o da caccia. Poi ad un certo punto qualcuno, forse lo stesso Galeno, cominciò a chiamare “rete mirabile” una formazione vascolare presente in alcuni animali, e piano piano, nei secoli, questa immagine è passata ai canali idrici, alle ferrovie, all'elettricità, ai telefoni. Oggi la rete è intorno a noi in tutti i sensi, come rete materiale, ma soprattutto come metafora d'uso comune per molte nostre organizzazioni mentali. Una rete di rapporti sociali ('a social network', da notare che “net” in inglese viene dal proto-indoeuropeo “ned” che in latino diventa “nodus”, insomma, siamo sempre lì...) che a sua volta spesso si immerge in una rete informatica, che vive fisicamente su delle reti elettriche, telefoniche, a fibra ottica. Senza parlare della rete di neuroni che ci permette di percepire queste reti di segnali. Se mettete la parola “rete” o ancora meglio “network” in Google (che è una vera rete nella rete), troverete almeno una dozzina di significati diversi. Un modo molto utile, ma non l'unico, anche se a volte tendiamo a dimenticarlo, per vedere una rete è quella di disegnarla come un grafo, ossia un insieme di oggetti legati tra loro. Gli oggetti si chiamano “vertici” o “nodi”, e i loro legami si chiamano “archi” o “lati”. Un grafo si disegna nel modo che potete facilmente immaginare, ossia fate delle palline e le unite con dei tratti di penna. I grafi e le reti sono studiati sotto tantissimi punti di vista da fisici, informatici, biologi, chimici, ma come al solito è compito della matematica cercare di capire alcune proprietà astratte che li caratterizzano.

 

Per esempio, un grafo che si può disegnare su un foglio di carta senza mai far incrociare gli archi si chiama planare. Se tutti i grafi fossero planari, allora non esisterebbero gli incroci, non dovremmo fare ponti o sottopassaggi o semafori. Ma sfortunatamente così non è. Vi sarà forse capitato di provare a risolvere il problema delle tre casette e delle tre centrali. In una certa regione vi sono una centrale idrica, una elettrica e una del gas che devono rifornire tre casette. Come possiamo connettere le case alle centrali visto che il regolamento di sicurezza stabilisce che le condutture di rifornimento non dovranno ma incrociarsi? Va bene, detto così sembra non molto realistico, per cui pensate ad un problema vero: vogliamo creare dei circuiti stampati in un microprocessore, e vogliamo che non ci siano intersezioni indesiderate che possano creare cortocircuiti. E adesso torniamo alle casette. Disegnate 6 puntini su un foglio, tre in una riga verticale a destra (le centrali) e tre a sinistra (le casette) e provate a connettere tutti i puntini a destra con tutti quelli a sinistra senza mai incrociare le linee, e per farlo potete usare qualsiasi curva che possiate tracciare senza staccare la penna dal foglio. Beh, dopo un po' che avrete provato per favore smettete, perché esiste un Teorema del 1930 del matematico polacco Kazimierz Kuratowski che dice che un grafo può essere planare se e solo se non contiene come sottografo il nostro problema delle casette oppure un altro tipo di grafo che è formato da 5 vertici che si uniscono in tutti i modi possibili (e che potete disegnare come una stella a cinque punte iscritta in un pentagono). In realtà c'è un modo più “diretto” (si fa per dire) di vedere questa impossibilità. C'è infatti un teorema che dice che per ogni grafo planare vale la formula di Eulero, ossia che se n è il numero dei nodi, m il numero dei lati e f il numero delle facce (ossia le regioni comprese tra i lati, compresa quella esterna al grafo), allora vale questa uguaglianza:

 

 

Questa formula vale anche per qualsiasi poliedro convesso, provate per esempio con un cubo (8 vertici, 12 lati, 6 facce) o una piramide (5 vertici, 8 lati, 5 facce), ed è molto importante in tutta la geometria moderna. Ma tornando al caso del grafo planare, abbiamo inoltre l'informazione che ogni lato ha intorno a sé due facce, per cui m è maggiore o uguale di 2f. Da questo si deduce che m è minore o guale a 2n-4. Ora, nel problema delle casette n=6, per cui 2n-4=8, e i lati sono 9, e questa uguaglianza non può essere soddisfatta, per cui il problema non ha soluzione. Ovvero, una soluzione c'è, altrimenti saremmo fritti con tutti i cavi e tubi che ci arrivano a casa. In realtà bisogna utilizzare il fatto che i nostri grafi sono in realtà immersi in tre dimensioni spaziali e possiamo far passare le condotte un po' sopra e un po' sotto. Questo è anche il principio su cui si basano i processori multistrato, perché ogni grafo si immerge sempre, senza intersezioni, nello spazio tridimensionale. Un modo molto elegante per vederlo è quello di mettere tutti i nodi del grafo su una retta, che potete immaginare come la costola di un libro. Questo si può sempre fare, perché il grafo è definito solo dalle relazioni che esistono tra i suoi nodi. Ora dovete sistemare i lati che connettono i nodi e che potete anche disegnare curvi. Ognuno di questi lati lo mettete su un piano diverso, che attaccate alla costola, come se fosse la pagina di un libro. Ogni lato, una pagina, e avrete il vostro grafo rappresentato in tre dimensioni senza intersezioni. Se volete provare a capire in pratica il problema dei grafi planari, esiste un gioco online che si chiama Planarity, che trovate qui, che vi propone di sistemare, muovendo I nodi, dei grafi ingarbugliati per vedere se si riescono a disegnare senza avere intersezioni. È meno facile di come possa sembrare, perché se è vero che il teorema di Kuratowski ci dice quando un grafo è planare e quando no, in pratica, come spesso capita, è tutta un'altra storia (e molto più difficile...).

di Roberto Natalini