La teoria dei sei gradi di separazione - STEP #19

Un mondo interamente connesso è da sempre spunto per pensieri utopici: l'idea che ognuno di noi sia in qualche modo collegabile a qualunque altro individuo è, al tempo stesso, affascinante e spaventosa. Questa concezione ci offre un nuovo punto di vista per osservare il mondo, ci dà una visione d'insieme e non possiamo fare a meno di pensare che in fondo il mondo non è così grande come pensiamo. A proposito di ciò, ci viene in aiuto la teoria dei sei gradi di separazione, secondo la quale ognuno può essere legato ad un altro attraverso una catena di conoscenze che passa tra cinque individui.

La prima formulazione della teoria non ha in realtà origine scientifica o statistica, ma si ritrova piuttosto in un racconto, intitolato "Catene", scritto nel 1929 dall'autore ungherese Frigyes Karinthy; questo concetto fu ripreso dal sociologo Duncan Watts nel libro "Six degrees: the science of a connected age". 

Questa ipotesi, che afferma che qualsiasi abitante della Terra è connesso con tutti gli altri da un massimo di sei relazioni personali, conclude dicendo che potremmo dunque arrivare a qualsiasi persona del pianeta tramite non più di cinque intermediari.

La teoria si basa sul fatto che il numero di persone conosciute cresce esponenzialmente quando cresce il numero di relazioni della catena: si basa dunque sui numeri.

Fonti:
https://it.wikipedia.org/wiki/Sei_gradi_di_separazione
https://people.unica.it/mlorinczi/files/2018/05/Karinthy-1929.pdf

Google Maps e la teoria dei grafi

Google Maps si basa su un algoritmo molto semplice ma incredibilmente efficace: l'algoritmo di Dijkstra. Esso prende il nome dal suo inventore, Edsger Dijkstra, uno dei fondatori pionieri dell'informatica moderna. 

Ecco come ebbe l'intuizione: era una mattina del 1956 e Dijkstra, che allora lavorava come programmatore al Centrum Wiskunde & Informatica (CWI) di Amsterdam, stava passeggiando con la sua fidanzata per fare un po' di shopping. Quando stanchi di camminare si sedettero a un tavolino di un caffè, lo scienziato olandese ebbe un'illuminazione: in soli 20 minuti, davanti a una tazza di caffè, progettò l'algoritmo che lo avrebbe fatto entrare nella storia dell'informatica.

Egli si servì di un grafo per descrivere la mappa della città: gli archi rappresentano le strade mentre i nodi sono gli incroci, ossia tutti i punti in cui è possibile scegliere quale strada prendere.

Grazie a questo modello, dato un punto di partenza e un punto di arrivo, all'interno del grafo stesso, l'algoritmo trova il "cammino minimo" che collega i due punti, ossia la sequenza di archi che minimizza il tempo stimato di percorrenza.

Fonte:

https://www.vice.com/it/article/4xn8vp/l-algoritmo-di-google-maps

Leonhard Euler - STEP #16

Leonhard Euler, conosciuto dalle nostre parti con il semplice cognome italianizzato Eulero, nacque a Basilea in Svizzera il 15Aprile del 1707. Il padre era un pastore protestante ed era amico di Johann Bernoulli, già all'epoca uno dei più famosi matematici di tutta Europa, e che avrebbe avuto una notevole influenza sulla formazione scientifica di Eulero. Egli infatti, seguì lezioni di matematica da Bernoulli, che era rimasto molto colpito dalle grandi capacità del suo allievo. Eulero pose le basi per la teoria dei grafi, ovvero la disciplina che si occupa del loro studio, ed è pertanto una figura emblematica nella storia e nello sviluppo di questi ultimi. Il primo testo che prende in considerazione i grafi come entità matematiche è proprio una pubblicazione di Eulero sui "Sette ponti di Konigsberg". Nel 1736 il matematico risolse il problema dei ponti di Konigsberg  mediante un grafo: si dimostrò essere un mezzo tramite cui trattare i problemi in maniera più schematica e di conseguenza più semplice. 

Fonti:
https://it.wikipedia.org/wiki/Eulero#Teoria_dei_grafi_e_topologia
https://www.matematicamente.it/storia/Lenzi-Ponti_Eulero.pdf

I ponti di Konigsberg

La teoria dei grafi, l'impalcatura matematica dietro la scienza delle reti, affonda le proprie radici nel lontano 1735 a Konigsberg, capitale della Prussia orientale, una fiorente città mercantile del suo tempo con una particolare geometria. Il commercio sostenuto dalla sua flotta permise ai funzionari della città di costruire sette ponti attraverso il fiume Pregel che circondava la città. Cinque di questi collegavano alla terraferma l'elegante isola di Kneiphof, intrappolata tra i due rami del Pregel. Questa peculiare disposizione ha dato vita a un quiz contemporaneo: si può attraversare tutti e sette i ponti senza passare due volte sullo stesso? Nonostante molti tentativi, nessuno riuscì a trovare un simile percorso. Il problema rimase irrisolto fino al 1735, quando Leonhard Euler, un matematico svizzero, offrì una rigorosa dimostrazione matematica della non esistenza di tale percorso.

Egli decise di schematizzare il problema rappresentandolo mediante un grafo: i nodi rappresentavano i lembi di terra mentre gli archi raffiguravano i ponti. Quindi Eulero fece una semplice osservazione: se c'è un percorso che attraversa tutti i ponti, ma mai lo stesso ponte due volte, vuol dire che i nodi con un numero dispari di collegamenti devono essere il punto iniziale o finale di questo percorso. Infatti, se si arriva a un nodo con un numero dispari di archi, è possibile che non si disponga di alcun collegamento ancora inutilizzato per poterlo lasciare. Il grafico di Konigsberg aveva quattro nodi con un numero dispari di collegamenti, quindi nessun percorso poteva soddisfare il problema.

Fu la prima volta in cui un grafo venne utilizzato per risolvere un problema matematico.

Fonti:http://www.treccani.it/enciclopedia/ponti-di-konigsberg-problema-dei_%28Enciclopedia-della-Matematica%29/
https://www.matematicamente.it/storia/Lenzi-Ponti_Eulero.pdf

Graficamente parlando

Personalmente vedo i grafi come mezzi, strumenti, per "parlare" graficamente.

Spesso è possibile rendere più semplici alcuni concetti grazie al loro legame con altri concetti.

Ecco un esempio, il primo post di questo blog spiegato attraverso una mappa concettuale: