Cambia lingua

Englishعربى中文DeutschEspañolFrançaisहिन्दीHrvatskiItaliano日本語PortuguêsRomânăРусскийSvenskaTürkçeTiếng Việt

Accedi a Mathigon

o

Nuovo account     Resetta la password     

Grafi e reti
Introduzione
I ponti di Königsberg
Strette di mano e appuntamenti
Grafi planari
Colorazione delle mappe
Il problema del commesso viaggiatore
Problemi di pianificazione
Grafi nella vita quotidiana

Condividere

Ripristina avanzamento

Questo cancellerà i tuoi progressi e i dati della chat per tutti i capitoli di questo corso e non può essere annullato!

Glossario

Seleziona una delle parole chiave a sinistra ...

Grafi e retiI ponti di Königsberg

Momento della lettura: ~20 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.

Archie