Oggi parliamo di teoria dei grafi, una branca della geometria nata per caso (o per merito) e che oggi è al centro dell'attenzione per le sue applicazioni nella logistica, nella società e nella teoria dei giochi.
Nel Settecento nella città allora prussiana di Königsberg (oggi la russa Kaliningrad) gli abitanti si dilettavano a cercare di “passare i ponti”, cioè trovare un modo per percorrere tutti e sette i ponti della città esattamente una volta sola.
I sette ponti di Königsberg
I ponti erano disposti in questo modo: l’isola “dell’Osteria”, circondata dal fiume Pregel, era connessa alla terraferma con due ponti per sponda, e con un solo ponte all’isola “della Cattedrale”, a sua volta connessa alla terraferma con un ponte per sponda.
Una sfida impossibile?(!)
Guardando una mappa dei ponti di allora, potete osservare che mai riuscireste ad attraversarne più di sei prima di raggiungere il settimo. Già ai tempi c’era chi aveva pensato che la sfida fosse impossibile, ma senza alcuna prova matematica. Nel 1736 Leonhard Euler, il più importante matematico del ‘700, creò, per dimostrare l’irrisolvibilità del problema, la teoria dei grafi.
Che cos'è un grafo?
Un grafo è costituito da un insieme di punti detti vertici collegati tra loro da linee detti spigoli. Conta come grafo, per esempio, due vertici con uno spigolo che li collega.
Passiamo adesso a generare un grafo euleriano, cioè un grafo in cui si possono percorrere tutti gli spigoli una sola volta; usando la definizione tracciamo gli spigoli man mano che li percorriamo e vediamo cosa deduciamo.
Partendo dai due vertici con uno spigolo tra loro, e se si continua a tracciare un grafo disegnando un percorso, raggiungendo un vertice, questi avrà ora grado dispari (perché è connesso a un numero dispari di spigoli), ma allontanandoci da quello stesso vertice, quest’ultimo avrà allora grado pari. Questo succede fino a quando non si ritorna al vertice di partenza, che abbiamo lasciato con un numero dispari di spigoli da esso fuoriuscenti e che al nostro ritorno assumerà grado pari, come tutti gli altri vertici. Si è creato un cammino euleriano chiuso, con tutti i vertici di grado pari. Se decidessimo di non tornare al punto di partenza, lo lasceremmo di grado dispari, come per il vertice in cui ci fermiamo. Con esattamente due vertici di grado dispari, invece, si ha un cammino euleriano aperto.
Il potenziale della nuova teoria
I sette ponti di Königsberg non seguono nessuno dei due schemi, perché presentano quattro vertici di grado dispari, ed è quindi impossibile percorrerli tutti una sola volta.
Da sfida cittadina la teoria dei grafi è diventata un simbolo della società contemporanea, spesso citata in relazione alle reti di amicizie sui social media. La teoria dei sei gradi di separazione è basata proprio su reti di relazioni sociali talmente diramate che, si suppone, bastano sei intermediari per arrivare a ogni persona nel mondo. Un grafo può essere anche una rete logistica, le configurazioni di una scacchiera e, perché no, di un cubo di Rubik.
Pensare al cubo di Rubik come un grafo
Per mappare con un grafo le configurazioni del cubo di Rubik si possono considerare come spigoli le mosse che permettono di passare da una configurazione all’altra. Un problema diffuso sin dagli albori del cubo è “Dopo quante mosse arrivo dalla posizione risolutiva a qualsiasi altra configurazione del cubo?” Questo numero passò alla storia come il “numero di Dio”, e in tanti si sono posti il problema di calcolarlo. Un computer potrebbe, in teoria, calcolare questo valore disegnando il grafo delle configurazioni e misurando le distanze, ma è un processo così lento e faticoso che numerosi matematici hanno provato a porre un numero minimo e uno massimo di mosse. Ci sono riusciti solo dopo molto tempo, giungendo alla conclusione che bastano venti mosse per risolvere qualsiasi cubo di Rubik.
“Sono sicuro che è più facile imparare la matematica che non il baseball.”
Dario Sanfilippo
Redazione SSC UniCT
E dunque la Scuola Superiore di Catania?
La formazione d’eccellenza è uno degli asset principali della Scuola Superiore di Catania. Gli allievi, in parallelo alle lezioni all’università, seguono in loco i corsi specialistici, che si distinguono per qualità e prestigio, tenuti anche da personalità internazionali e adattati ai propri interessi di ricerca, per avvicinarli precocemente a essa.
Opportunità
Il tutor è un professore o ricercatore dell’Università di Catania o di un’istituzione con essa convenzionata che segue individualmente ciascun allievo.
È scelto da ciascun allievo in funzione di cosa vuole approfondire per le sue future attività di ricerca. È compito del tutor fornire un approccio metodico alla ricerca stessa, erogando egli stesso o facendo erogare da personalità contattate i corsi specialistici. #UnlockMath
Vuoi saperne di più?
