La matematica dei social network
Una introduzione alla teoria dei grafi
Premio Peano 2012 per il miglior libro di lettura matematica
Cosa hanno in comune i circuiti elettrici, il sistema stradale o ferroviario, i sette ponti della città di Königsberg, gli antichi labirinti e Internet? Viviamo in un mondo interconnesso e questo libro ci spiega perché.
- Collana: ScienzaFACILE
- ISBN: 9788822068286
- Anno: 2012
- Mese: marzo
- Formato: 14 x 21 cm
- Pagine: 304
- Note: illustrato
- Tag: Scienza Matematica Informatica Internet Social Network
Come si può calcolare il percorso più breve tra due città? È possibile colorare una cartina geografica usando solo quattro colori? Con due gruppi, uno di n ragazzi e l’altro di m ragazze, e una relazione di «attrazione» tra i gruppi di sesso opposto, qual è la maniera più efficiente per formare delle coppie? La disciplina matematica che studia questo tipo di strutture si chiama teoria dei grafi e fornisce soluzioni a numerosi problemi pratici e teorici. Partendo da alcuni rompicapi matematici, Peter Higgins ci aiuta a esplorare le strutture nascoste che sono alla base di alcuni tra i fenomeni più complessi del mondo attuale. Si passerà dal Sudoku circolare al classico problema del postino cinese (che ha eluso tanti matematici), dall’organizzazione della sorveglianza di una galleria d’arte al trasporto di mogli e mariti gelosi, per arrivare ai social network e infine alla struttura e ai meccanismi alla base della vita. Uno dei migliori saggi introduttivi alla teoria delle reti e dei grafi che spiega in modo chiaro quali sono i problemi fondamentali connessi a questa disciplina affrontando alcuni argomenti classici della matematica combinatoria.
Introduzione - 1. Reti, alberi e bugie - Alberi - Isomeri chimici - I bugiardi che mentono e le loro bugie - 2. Gli alberi e il gioco della logica - I giochi logici più comuni - Quadrati esotici e Sudoku - 3. La natura delle reti - Il fenomeno del «mondo piccolo» - I ponti di Königsberg - Il lemma delle strette di mano e le sue conseguenze - Cicli che vi portano in giro - Il problema del party - 4. Colorazione e planarità - Il problema dei quattro colori - Come i lati possono rovinare la planarità - Conigli dal cilindro - 5. Come attraversare una rete - Il metodo di Eulero-Fleury - Il problema del postino cinese - 6. Sistemi a senso unico - Reti che ricordano dove si è stati - Le reti come macchine - Automi che hanno qualcosa da dire - Reticoli - 7. Spanning network - Dirigere il traffico - L’avido commesso viaggiatore - Trovare l’itinerario più breve - La controversia: P = NP? - 8. Seguendo il flusso - La capacità di una rete e il problema di trovare il ragazzo giusto - Matrimoni e altri problemi - Harem, flussi massimi e altro - 9. Le nuove applicazioni delle reti - Instant Insanity - Spartirsi il vino - Problemi di gelosia - Dedali e labirinti - Alberi e codici - Ricombinare le catene dell’RNA - 10. Per intenditori - Riferimenti - Approfondimenti - Indice analitico
Il problema del party
Con le prossime due domande ritorneremo al tema delle reti di amicizie e conoscenze, ma inizieremo con l’esaminare le proprietà possedute da queste, anche su piccolissima scala. La domanda, posta da Ramsey, sembra ingenua e banale, tuttavia rappresenta la punta di un enorme iceberg matematico, che è la Teoria di Ramsey. Il problema è questo: di quante persone c’è bisogno in un party affinché si possa esser certi che ci saranno almeno tre persone che si conoscono tra loro oppure tre persone che non si conoscono l’una con l’altra?
La risposta deve essere più di cinque, a causa della seguente disposizione ai tavoli. Immaginate cinque persone sedute a cenare in modo che ogni persona conosca le due persone che gli sono affianco, ma che non conosca gli altri due. Questo è senz’altro possibile: se sistemiamo i cinque individui attorno al tavolo e facciamo in modo che i due conoscenti si tengano per mano, otteniamo come rete delle loro conoscenze un semplice ciclo a cinque (figura 3.9).
Questa rete non contiene alcun triangolo, poiché nessun insieme di tre persone si conosce reciprocamente, ma non esiste nemmeno un triangolo formato da sconosciuti: per esempio, consideriamo A (per questioni di simmetria non importa su chi ci concentriamo); gli ospiti che A non conosce sono C e D che invece sono amici.
Possiamo rappresentare la rete di sconosciuti ma quello che otteniamo a prima vista sembra un po’ aggrovigliato: infatti la rete degli sconosciuti assume le sembianze un po’ sinistre di un pentacolo. Tuttavia, in questo caso, queste due reti sono in realtà la stessa cosa: se elenchiamo i nodi della rete a destra nella figura 3.9, nell’ordine abbiamo A --> C --> E --> B --> D --> A, e vediamo che anche questo pentacolo è semplicemente un ciclo a cinque, identico all’originale – in particolare non possiede alcun triangolo con tre nodi connessi reciprocamente tra loro.
In generale, la rete che otteniamo quando prendiamo lo stesso insieme di nodi, cancelliamo tutti i lati e poi colleghiamo le coppie di nodi che prima non erano connesse, si chiama rete complementare (un concetto che ha ragion d’essere quando si parla delle reti che non possiedono né anelli né lati multipli che uniscono coppie di nodi). Il ciclo a cinque è un esempio di una rete autocomplementare, poiché il complemento è ancora una rete a cinque, come si può vedere dopo averla esaminata con attenzione.
La risposta al problema di Ramsey è, quindi, almeno 6, e se provate a cimentarvi abbastanza a lungo con reti che rappresentano sei o più persone vi convincerete che 6 è proprio la risposta giusta – ma come possiamo esserne sicuri?
La difficoltà è che, considerando sei persone, ci sono tante possibili combinazioni che possono descrivere i reciproci rapporti di conoscenza. Il nostro ragionamento deve essere in grado di affrontare queste possibilità tutte in una volta. Se procediamo nella maniera sbagliata, ci perderemmo subito in una marea di casi. Una linea di ragionamento semplice ed efficace è comunque disponibile ma serve prima una breve ma sottile considerazione.
Consideriamo un insieme di sei persone qualsiasi presenti all’incontro e concentriamoci su una di esse, che chiamiamo A (figura 3.10). Delle restanti cinque, o A ne conosce almeno tre, o altrimenti, ce ne sono almeno tre che non conosce (questo è l’unico punto nel nostro ragionamento in cui utilizziamo il fatto che ci sono almeno sei persone presenti). Supponiamo per ora che A ne conosca tre. Allora o queste tre persone non si sono mai incontrate prima, per cui abbiamo trovato un terzetto di persone che non si conoscono tra loro, oppure almeno due di loro, chiamiamoli B e C, si conoscono. Ma allora A, B e C formano un terzetto di conoscenti. Il ragionamento è adesso fondamentalmente completo poiché il caso alternativo in cui A non conosce nessuno tra B, C o D è lo stesso – o BCD è un trio di persone che si conoscono reciprocamente tra loro, altrimenti due di loro, insieme ad A, formano un triangolo di sconosciuti.
Possiamo concludere allora che ogni volta che sei o più persone si incontrano, o c’è un «triangolo» di persone che si conoscono tra loro oppure un triangolo di perfetti sconosciuti (o forse entrambi i casi).
Abbiamo mostrato che 6 è il minimo numero di nodi che una rete semplice deve possedere per garantire che la rete stessa o la sua complementare contenga un triangolo. Questo genere di risultato susciterà sempre la stessa reazione in chi ha una formazione matematica in quanto la generalizzazione sembra una possibilità concreta. L’interrogativo che sorge spontaneo è: quanto deve essere grande una rete per essere certi che essa o la sua complementare contengano una cricca di quattro nodi reciprocamente connessi? E, più in generale, quanto grande deve essere una rete per garantire che una cricca di una data dimensione k sia presente nella rete (o nella sua complementare)?
Queste sono domande ottime ma molto difficili – infatti nessuno conosce la risposta nell’ultimo caso, nemmeno per k = 5.
Tuttavia, sappiamo con certezza che esiste una risposta, sebbene tutt’altro che ovvia. Dopo tutto, è plausibile che si possa organizzare un party con un numero di invitati maggiore di un qualunque numero assegnato in cui non ci sia alcun gruppo di quattro amici e nessun quartetto di perfetti sconosciuti. Tuttavia è noto che una volta che si hanno diciotto o più persone, ciò diviene impossibile – diciamo così che il quarto numero di Ramsey è 18. Ciò che il matematico ed economista inglese F.P. Ramsey (1903-1930) ha dimostrato negli anni ’30 è che i numeri di Ramsey esistono sempre – ossia che per ogni numero k esiste un numero minimo n (la grandezza di n dipende da k) tale che in ogni party con n o più persone c’è una cricca di k conoscenti oppure una k-cricca di persone che non si conoscono. Tuttavia, il valore preciso di questi numeri di Ramsey resta in generale un mistero, ma questi esistono – Ramsey lo ha provato e potrete trovare la dimostrazione nel capitolo finale*.
La domanda seguente relativa alle reti è anche maggiormente gradita quando si tratta di party.
Per esempio in un paesino di 400 anime, almeno due abitanti festeggiano il compleanno nello stesso giorno poiché ci sono più persone che possibili compleanni. Possiamo addirittura dire di più: considerando anche il 29 febbraio, ci saranno almeno 400 - 366 = 34 persone in paese che festeggeranno il compleanno nello stesso giorno di qualche altro concittadino, poiché il numero di individui per cui questo è falso non può essere maggiore di 366, che è il numero di tutte le date di compleanno possibili. Nessuno può avere idea di chi siano queste 34 persone (e naturalmente potrebbero essercene anche di più) ma esiste la certezza matematica che ci siano!
Devo confessare che ci siamo già imbattuti in alcune varianti del Principio della buca delle lettere nel ragionamento sul problema di Ramsey e anche prima quando abbiamo mostrato che la struttura del grafo della rete relativa al problema di acqua, luce e gas non è planare. Qui abbiamo fatto la semplice considerazione che se tracciamo tre lati che collegano i punti di un ciclo, allora almeno due di essi devono trovarsi all’interno o all’esterno del ciclo: ciò corrisponde a infilare tre lettere in due buche. Nel ragionamento relativo al problema di Ramsey ricorderete che ci siamo concentrati su A, una delle sei persone, e abbiamo diviso gli altri cinque invitati in due tipi, quelli che conoscono A e quelli che non lo conoscono. Nel fare ciò stiamo in realtà mettendo cinque oggetti in due scatole e concludiamo che una scatola ne deve contenere almeno tre. Il principio generale che si sta applicando in questo caso è il seguente: se riponiamo più di m x n oggetti in m scatole, allora almeno una scatola ne deve avere più di n. Nel problema di Ramsey m = n = 2, per cui m x n = 4 e stiamo collocando le cinque persone in due categorie, per cui almeno tre di loro sono dello stesso tipo. Non c’è nulla di complicato in tutto ciò, ma ho attirato la vostra attenzione sul principio della buca delle lettere solo per enfatizzare quanto spesso questo trucchetto salta fuori in ragionamenti del genere.
Ci sono molti impieghi ingegnosi del suddetto principio concepiti per provare alcuni risultati sorprendenti su delle cose che accadono inevitabilmente in grandi collezioni di oggetti. Un banale esempio si ha considerando l’insieme di tutti i numeri interi da 1 fino all’n-simo numero pari, ossia 1, 2, ..., 2n. Se tra questi prendiamo un qualunque insieme di n + 1 numeri, almeno due di essi non avranno nessun fattore comune. Questo si ricava immediatamente dal fatto che due numeri della collezione devono essere consecutivi. Infatti è chiaramente impossibile che le differenze tra tutte le coppie siano tutte maggiori di 1, poiché altrimenti il numero più grande dell’insieme sarebbe almeno uguale a 1 + 2n (cioè, per avere almeno 2 lettere in n buche servono per lo meno 2n lettere). Per esempio, in qualunque insieme di sei numeri presi tra 1, 2, ..., 10, due di essi devono essere necessariamente consecutivi. Ogni fattore del primo di questi due numeri «contigui» darà resto 1 quando viene diviso per il secondo, e quindi ci sono due numeri che non hanno alcun fattore comune (diverso da 1). Ciò non è tanto inatteso, sebbene dovremmo aggiungere che questa osservazione non può spingersi oltre, poiché è facile trovare un insieme di n numeri in questa serie, tutti con 2 come fattore comune, vale a dire tutti i numeri pari, 2, 4, ..., 2n.
Un’osservazione più sorprendente su questo insieme di n + 1 numeri è quella che uno di essi deve essere sempre multiplo di uno degli altri e si può provare per mezzo di un’applicazione molto più acuta del principio della buca delle lettere*.
Questa idea della buca delle lettere emerge anche nella questione relativa al party, come spiegherò adesso. Supponiamo che al party ci siano n persone, con n maggiore di 2, poiché altrimenti non si avrebbe nessun party. Il numero massimo di amici che può avere uno dei partecipanti alla festa è n – 1: per esempio, la ragazza che organizza la festa potrebbe aver invitato soltanto i suoi amici. Il numero minimo è 0. Questo può sembrare triste, ma è possibile: alla festa potrebbe esserci un «imbucato».
Tenete a mente che ogni invitato possiede un numero amicale, ossia il numero di amici presenti al party, e questo numero deve essere compreso tra 0 e n – 1 incluso.
Addesso supponete, contrariamente a quello che ci aspettiamo, che non sia possibile trovare due invitati che abbiano lo stesso numero di amici, il che significa che il numero amicale di ognuno è diverso da quello di tutti gli altri. Non è facile; tuttavia, sembra comunque plausibile: ci sono n numeri diversi distribuiti tra le n persone, il che significa che ognuno dei possibili numeri amicali 0, 1, 2, ..., n - 1 viene preso solo una volta. Ecco però che accade un colpo di scena che rende il tutto impossibile! Una certa persona P ottiene lo 0 (nessun amico), mentre un altro, chiamiamolo Q, ottiene il massimo, n – 1. Questo significa tuttavia che Q, alla festa, considera tutti degli amici, incluso P che altrimenti sarebbe senza amici. Ma, se P e Q sono amici, allora in definitiva P non può avere 0 come numero amicale. Allora, partendo dall’assunzione che ognuno avesse un numero diverso di amici, abbiamo trovato una vera e propria contraddizione, e quindi ciò non può accadere. Pertanto, al party ci sono ogni volta almeno due persone che hanno lo stesso numero di amici, e questo vale per qualunque gruppo di persone, sempre e dovunque.
Naturalmente, tutto ciò ci sta dicendo veramente qualcosa sulle reti, almeno per quelle reti che possono rappresentare i rapporti di conoscenza a un party, e questi risultati sono effettivamente abbastanza generali. Non ci sono vere e proprie limitazioni alle «reti dei party», ad eccezione del numero di lati tra ogni coppia di nodi che può essere 0 o 1 – non sono consentiti lati multipli come abbiamo visto nei ponti di Königsberg, e nessun lato può ritornare nel nodo da dove è partito, formando così un anello. Questo tipo di reti, che vieta la presenza di lati multipli e anelli, a volte viene chiamato rete semplice. Il ragionamento riguardo al party in realtà ci sta dicendo che in una qualunque rete semplice devono esserci sempre due nodi dello stesso grado.
Quanto detto sinora esaurisce per il momento la nostra serie di problemi. Il capitolo seguente introduce una domanda semplice a cui si può rispondere in modo elementare sebbene sembra che non abbia alcuna soluzione banale.
| 08 ottobre 2012 | Oggi Scienza |
Articolo acquistabile con 18app e Carta del Docente
