English
عربى
中文
Deutsch
Español
Français
हिन्दी
Hrvatski
Italiano
日本語
Português
Română
Русский
Svenska
Türkçe
Tiếng ViệtGrafi e retiGrafi nella vita quotidiana
Abbiamo visto molte diverse applicazioni della teoria dei grafi nei capitoli precedenti. Sebbene alcune di esse fossero un po' fittizie, i grafi sono alla base di molti oggetti, concetti e processi nella vita di tutti i giorni.
Internet, ad esempio, è un vasto grafo virtuale. Ogni vertice è una singola pagina Web e ogni spigolo indica che esiste un collegamento ipertestuale tra due pagine. Nota che i collegamenti vanno solo in una direzione, quindi questo grafo è
Alcuni siti Web, come Wikipedia o Facebook, hanno molti collegamenti in entrata, mentre molti siti più piccoli possono avere pochissimi collegamenti in entrata. Questo è il concetto di base che Google utilizza per ordinare i risultati della ricerca.
I siti Web con più collegamenti in entrata tendono ad essere di qualità superiore e dovrebbero essere visualizzati per prima nei risultati di una ricerca. Ad esempio, quando si cerca "Londra", i siti di informazione turistica ufficiali vengono mostrati prima dei piccoli negozi di Londra o dei blog di persone che vivono a Londra. Questa semplice idea della teoria dei grafi, l'Algoritmo PageRank, ha reso Google significativamente migliore rispetto ad altri primi motori di ricerca.
Internet è la più grande rete mai creata dall'umanità. Questa immagine mostra una proporzione molto piccola di tutti i server connessi a Internet:
Mentre siti Web e collegamenti ipertestuali formano un grafo virtuale, esiste anche la rete fisica di computer, server, router, linee telefoniche e cavi.
Ogni volta che si effettua una telefonata o si carica un sito Web, gli operatori di rete devono trovare un modo per collegare il mittente e il destinatario, senza superare la capacità di ogni singolo cavo o connessione. La teoria dei grafi e la probabilità garantiscono un servizio affidabile, ad esempio trovando un'alternativa quando una certa connessione è occupata.
I grafi svolgono anche un ruolo importante nel trasporto e nella navigazione. Tutte le reti di voli, treni e metropolitane formano grafi che possono essere utilizzati per la creazione di orari efficienti. Uno dei grafi più riconoscibili è la mappa della metropolitana di Londra:
Anche tutte le strade e le autostrade formano una grande rete, che viene utilizzata dai servizi di navigazione come Google Maps durante l'elaborazione del percorso più breve tra due punti.
In futuro, Sistemi di trasporto intelligenti ridurranno la congestione e gli incidenti indirizzando le auto in modo più efficiente, utilizzando i dati sulla posizione raccolti dagli smartphone e dalle autovetture autonome. Ciò potrebbe risparmiare milioni di ore perse ogni anno a causa del traffico, ridurre significativamente l'inquinamento e consentire ai servizi di emergenza di viaggiare più velocemente.
Questa immagine mostra la rete di voli di compagnie aeree commerciali nel nord Europa.
Esistono innumerevoli grafi nella scienza, nell'ingegneria e nella vita quotidiana:
I legami tra gli atomi nelle molecole e nei cristalli formano un grafo.
La diffusione di malattie ed epidemie può essere modellata usando una rete.
In biologia, gli alberi evolutivi che mostrano gli antenati delle specie formano un grafo.
I diversi componenti dei circuiti elettrici e chip di computer formano una rete.
La struttura grammaticale delle lingue può essere modellata utilizzando dei grafi, ad esempio per creare algoritmi di traduzione.
I grafi hanno anche molte applicazioni in probabilità, teoria dei giochi e matematica finanziaria.
Social Network
Infine, pensiamo ad un esempio particolarmente buono di grafi che usiamo nella vita di tutti i giorni: i social media. Qui, i vertici rappresentano
Quando disegniamo grafi per social media, potremmo vedere alcuni gruppi di amici comuni, che per esempio hanno frequentato nella stessa scuola o vivono nella stessa città. Possiamo anche determinare la centralità delle persone, che dipende da quanto un vertice è ben collegato: questa può essere una misura della popolarità di una persona sui social media.
Nel 2014, Facebook aveva 1,4 miliardi di utenti attivi e un totale di oltre 200 miliardi di amicizie. La metà di tutti gli utenti di Facebook ha più di 200 amici e poiché la maggior parte dei nostri amici ha un numero simile di amici, potremmo facilmente avere decine di migliaia di amici di amici.
Una domanda interessante sarebbe ora: se scegli due utenti casuali su Facebook, quanti "spigoli di amicizia" dovresti seguire per passare dall'uno all'altro? Ad esempio, la distanza tra amici è
Nel 2016, Facebook ha condotto uno studio per determinare come i suoi utenti sono collegati tra loro. Hanno scoperto che, in media, ogni utente è connesso a chiunque altro su Facebook tramite un massimo di 3,57 altre persone. E questo include celebrità, politici o persino membri della famiglia reale!
In altre parole, se scegli uno dei miliardi di utenti di Facebook in tutto il mondo probabilmente avrà un amico di un amico che conosce un amico di uno dei tuoi amici. Diciamo che ci sono 3,57 gradi di separazione.
Visualizzazione geografica di tutte le amicizie di Facebook nel 2010.
Nel 1929, quando l'autore ungherese
Nel 1967,
Oggi ognuno di noi fa parte di innumerevoli grafi invisibili, che sono alla base delle nostre interazioni sociali, di viaggi, Internet e tecnologia, scienza e molto altro ancora.