Menu Chiudi

Topologia e teoria dei grafi

Questo laboratorio è stato sviluppato per il liceo matematico ed è nato da una conversazione con la professoressa Lucilla Galterio. L’argomento è presentato nell’articolo Il problema del postino.

Materiale a supporto

  • Il fascicolo Quattro passi in centro (in formato PDF di circa 15.8MB) in cui si affronta il problema dei ponti di Königsberg e il teorema di Eulero.
  • Il fascicolo Un grafo connesso (in formato PDF di circa 9.3MB) in cui si determina una procedura per decidere se un grafo è connesso.
  • Il fascicolo Un problema di consegne (in formato PDF di circa 11.5MB) in cui si esamina il Problema del postino cinese.

Questo percorso affronta Il Problema del postino cinese. Fu proposto dal matematico Meigu Guan (nato a Shangai, da cui l’aggettivo cinese) nel 1962. In termini formali il problema chiede di individuare in un grafo un cammino ciclico (un circuito) di lunghezza minima che attraversi tutti gli archi del grafo.In pratica, dato un grafo si tratta di percorrere tutti gli archi in modo da tornare al termine della passeggiata al punto di partenza ma questo cammino deve essere il più breve possibile, quello di lunghezza minima. Proprio il percorso migliore per recapitare la posta!

Il problema è banale in un grafo euleriano (un grafo in cui esiste un percorso che attraversa tutti gli archi una e una sola volta) ma in grafi che non possiedono questa proprietà il problema diventa una questione davvero interessante.

Dalle chiacchierate con il gruppo del liceo matematico sono nati tre laboratori che possono essere proposti in successione o affrontati separatamente, in un solo anno o in più anni di corso.

Il piano di lavoro del percorso
Il piano di lavoro del percorso: si parte dal problema dei ponti di Königsberg e il teorema di Eulero che in parte lo risolve, si studia una procedura per decidere se un generico grafo è connesso per passare poi alla ricerca della via più breve tra due nodi in un grafo per finire con la costruzione di un circuito euleriano anche in grafi che non sono euleriani: e il gioco è fatto!

Prerequisiti

In pratica non sono necessarie conoscenze e/o competenze per affrontare il primo di questi laboratori – Quattro passi in centro – che fornisce tutto quello che serve per gli altri due.

È bene precisare che si può trascurare il secondo laboratorio, Un grafo connesso, per passare direttamente, dopo Quattro passi in centro, a Un problema di consegne, il laboratorio conclusivo, in cui si ragiona sulla possibilità di un efficiente metodo per la consegna della posta. Infatti, per gli esempi e gli esercizi proposti, la decisione sulla connessione di un grafo si può affrontare in modo empirico.

Obiettivi

I tre laboratori sono abbastanza diversi tra loro dal punto di vista degli obiettivi. Nel primo, Quattro passi in centro, lo scopo è principalmente quello di introdurre, in modo molto semplice e graduale, qualche informazione sui grafi e guidare alla (ri)scoperta del teorema di Eulero.

  • costruire un modello per i problemi di teoria dei grafi;
  • risolvere (usando il modello realizzato) alcuni problemi classici di teoria dei grafi.

Nel secondo, Un grafo connesso, si punta molto sulla formalizzazione di una procedura in un linguaggio naturale ma il meno ambiguo possibile (si può estendere il laboratorio implementando la procedura realizzata con un generatore di codice come Blockly).

  • formalizzare una procedura per decidere, in modo sistematico e non empirico, se un grafo è connesso.

Il terzo laboratorio, Un problema di consegne, è sicuramente il più interessante di tutti: il problema è molto semplice da comprendere ma la strategia risolutiva richiede competenza, fantasia, organizzazione e tante diverse procedure apprese lungo la strada.

  • apprendere un algoritmo per determinare il cammino più breve tra due nodi di un grafo;
  • imparare a costruire un circuito euleriano in un grafo (se possibile);
  • pensare a un metodo per costruire un circuito euleriano in un grafo non euleriano (in un grafo dove questo circuito proprio non c’è).