Glossario

Seleziona una delle parole chiave a sinistra ...

Grafi e retiI ponti di Königsberg

Momento della lettura: ~30 min

Uno dei primi matematici a pensare a grafi e reti fu Leonhard Euler (Eulero). Eulero era incuriosito da un vecchio problema riguardante la città di Königsberg vicino al Mar Baltico.

Il fiume Pregel divide Königsberg in quattro parti separate, che sono collegate da sette ponti. È possibile passeggiare per la città attraversando tutti i ponti esattamente una volta, ma non più di una volta? (Puoi iniziare e finire ovunque, non necessariamente nello stesso posto.)

Prova a trovare un percorso valido disegnando su queste mappe:

Mappa 1

Mappa 2

Mappa 3

Mappa 4

Nel caso di Königsberg sembra impossibile trovare un percorso valido, ma si riesce per alcune delle altre città. Eulero trovò una semplice regola che può essere applicata a qualsiasi città, senza fare tanti tentativi - usando la teoria dei grafi.

Innanzitutto, dobbiamo convertire le mappe delle città in grafi con bordi e vertici. Ogni isola o regione di terra è rappresentata da e ogni ponte che collega due regioni è rappresentato da corrispondente.

Ora il problema di "visitare una città attraversando ogni ponte esattamente una volta" è diventato il problema di "tracciare un grafico con una linea continua tracciando ogni spigolo esattamente una volta sola".

Sulla mappa, crea alcuni grafi diversi e poi prova a capire quali possono essere disegnati con un singolo tratto continuo.

Proprio come per le mappe della città, scopriamo che alcuni grafi sono possibili mentre altri no. Per aiutarci a capire perché, etichettiamo ogni vertice con il suo grado. Ora possiamo colorare i vertici in diversi modi e provare a rivelare uno schema:

Valore
Dimensione
Numeri primi
Pari e dispari

Questi grafi sono possibili:

2 4 3 3 4 4 2 2 4 4 2 2 2 4 4 2 2 2 4 4 2 4 4 8 2 2 4 4 4 4 2

Questi grafi non sono possibili:

2 3 2 3 4 3 2 3 2 2 2 2 2 3 5 3 3 5 3 3 6 3 3 3 3 3

Confrontando questi numeri per i grafi che sono possibili e quelli che non sono possibili, sembra che un grafico possa essere disegnato se . Questa condizione può essere spiegata se osserviamo solo un singolo vertice nel grafico:

Qui puoi vedere un singolo vertice ingrandito
Se disegnamo il grafo, abbiamo due spigoli che si incontrano nel vertice.
Se il vertice è un incrocio invece che un angolo, abbiamo quattro spigoli.
In altri casi, possiamo avere sei spigoli.
Nota che, in ogni caso, c'è sempre un numero pari di spigoli che si incontrano al vertice.
Le uniche eccezioni sono i vertici all'inizio e alla fine del percorso – questi possono avere un numero dispari di spigoli. Se il punto iniziale e finale sono gli stessi, allora tutti i vertici sono pari.

Se scorri indietro sulla mappa di Königsberg, scoprirai che ci sono più di due isole con un numero dispari di ponti. Pertanto, come scoprì Eulero, è impossibile trovare un percorso che attraversa ogni ponte esattamente una volta. La scoperta di Eulero potrebbe non sembrare particolarmente utile nella vita reale, ma i grafi sono alla base di molti altri problemi geografici, come trovare indicazioni stradali tra due località. Scopriremo molte di queste applicazioni in seguito.

Sei stato invitato ad una meravigliosa festa di compleanno con i tuoi amici. Oltre a te e al festeggiato, ci sono ${hnd} persone presenti. La sera, mentre gli ospiti si preparano a partire, tutti si stringono la mano con tutti gli altri. Quante strette di mano vengono fatte in totale? Possiamo rappresentare le strette di mano usando un grafo: ogni persona è e ogni stretta di mano è .

Ora è facile contare il numero di spigoli nel grafico. Troviamo che lì con ${hnd} persone, ci sono ${hnd*(hnd-1)/2} strette di mano.

Per i grafi di grandi dimensioni, invece di contare tutti gli spigoli, potremmo provare a trovare una semplice formula che ci dice il risultato per qualsiasi numero di ospiti. Ognuna delle ${n} persone alla festa stringe la mano a ${n-1} altre. Ciò rende ${n} × ${n-1} = ${n×(n-1)} strette di mano in totale. Per n persone, il numero di strette di mano sarebbe .

Purtroppo questa risposta non è del tutto corretta. Notare come le prime due voci nella riga superiore sono in realtà le stesse, invertite. In effetti, abbiamo contato ogni stretta di mano , per ciascuna delle due persone coinvolte. Ciò significa che il numero corretto di strette di mano per ${n} ospiti è ${n}×${n-1}2=${n*(n-1)/2}.

I grafi delle strette di mano sono speciali perché ogni vertice è collegato ad ogni altro vertice. I grafi con questa proprietà sono chiamati grafi completi. I grafi completi con 4 vertici sono spesso abbreviati come K4, i grafi completi con 5 vertici sono noti come K5 e così via. Abbiamo appena dimostrato che un grafo completo con n vertici, Kn, ha n×n12 spigoli.

Un altro giorno, sei invitato ad un evento di speed dating per ${m} ragazzi e ${f} ragazze. Ci sono molti tavolini e ogni ragazzo trascorre 5 minuti con ciascuna delle ragazze. Quanti "appuntamenti" individuali vengono svolti in totale?

In questo caso, il grafo corrispondente è costituito da due serie separate di vertici. Ogni vertice è collegato a tutti i vertici , ma nessuno dei vertici . I grafi che hanno questo layout sono chiamati grafi bipartiti.

I grafi bipartiti con due serie di dimensioni x e y sono spesso scritti come Kx,y. Hanno spigoli, il che significa che nell'esempio precedente vengono svolti ${m} × ${f} = ${m×f} appuntamenti.