Menu Chiudi

Un problema di consegne

Un problema di consegne

O meglio, il problema del postino cinese

Le slide della presentazione del percorso didattico si possono trovare nella pagina Download o scaricare direttamente seguendo questo collegamento.

Il problema del postino è stato proposto dal matematico cinese Mei-Ku Kwan nel 1960 e successivamente rinominato, in suo onore, il problema del postino cinese nel 1962. È un problema classico di topologia e di teoria dei grafi, il cui algoritmo risolutivo è piuttosto complesso ma la cui formulazione è davvero semplice:

si tratta di ostruire un circuito di lunghezza minima che attraversi tutti gli archi di un grafo

È il problema che hanno corrieri e postini, ma anche i raccoglitori di rifiuti: passare per ogni strada di competenza una sola volta percorrendole tutte, in modo da ritornare al punto di partenza una volta finito il giro, nel modo più economico possibile. Il problema è banale in un grafo euleriano perchè grafi di questo genere hanno un circuito, un percorso chiuso, che passa per ogni arco una e una sola volta.

In grafi non-euleriani, dove non è possibile costruire un circuito del tipo descritto, il problema del postino cinese, diventa una questione davvero interessante. Dopo una conversazione con la professoressa Malusa (Dipartimento di matematica, Università La Sapienza di Roma) ne abbiamo tirato fuori due laboratori che possono essere proposti in successione, anche suddividendoli in quattro/cinque sessioni, o affrontati separatamente.

Una sintetica mappa concettuale che riepiloga e raccoglie tutti i laboratori che ruotano attorno al problema del postino cinese. Va letta in senso orario a partire dall’alto, da I ponti di Königsberg.

Il laboratorio

Le attività illustrate qui di seguito sono ispirate al laboratorio Percorsi, strategie e geometrie in gioco del Giardino di Archimede di Firenze ma soprattutto al libro Alla ricerca della via più breve di Peter Gritzmann e Rene Brandenberg edito da Springer.

In pratica, nell’ordine, si propone agli studenti:

  1. Di affrontare il problema dei ponti di Königsberg – il primo risultato di topologia – con l’obiettivo di ri-scoprire il teorema di Euler (vedi anche http://researchinaction.it/2019/01/21/i-ponti-di-konigsberg/ su questo stesso blog). Il fascicolo guida per questa prima parte si può trovare seguendo questo collegamento.
  2. Di costruire una procedura per decidere se un grafo è connesso per completare quanto fatto nel passo precedente, infatti il teorema di Euler si applica solo ai grafi connessi. Obiettivo di questo laboratorio, in prima istanza, è quello di formalizzare l’algoritmo in linguaggio naturale abbastanza rigoroso da non risultare ambiguo e da poter essere applicato anche solo con carta e penna, obiettivo ulteriore l’implementazione della procedura con Blockly (c’è un piccolo laboratorio virtuale su questo sito in cui sperimentare questo generatore di codice applicandolo alla teoria dei grafi).
  3. Affrontare il problema di determinare un il cammino più breve in un grafo. Di nuovo, con l’obiettivo di formalizzare l’algoritmo in linguaggio naturale, ma non ambiguo e, forse, di implementare la procedura usando Blockly.
  4. Costruire un algoritmo per individuare un cammino/circuito euleriano in un grafo e applicarlo ad alcuni grafi di esempio, magari arrivando fino a implementare la procedura usando Blockly.
  5. Trasformare un grafo non euleriano aggiungendo cammini a vuoto, nel modo più economico possibile, in euleriano: la soluzione del problema del postino cinese! In questo caso l’obiettivo è quello di applicare la procedura per la soluzione di alcuni problemi di esempio, non si richiede la formalizzazione, né l’implementazione (gli algoritmi di accoppiamento o di trasporto ottimo necessari per concludere l’ultimo passaggio del processo sono molto complessi).

Il percorso didattico è stato presentato l’otto marzo 2019 nell’ambito del seminario La matematica di Figalli, Isituto G. Castelnuovo, Università La Sapienza di Roma. Le slide della presentazione si possono trovare nella pagina Download.

Particolarmente interessante è la modularità della soluzione finale che fa uso di ogni idea, procedura, metodo, ideato e costruito lungo il cammino: il teorema di Euler per decidere se il grafo ha già un cammino/circuito, l’algoritmo per il cammino minimo per cercare i cammini a vuoto più economici, la procedura per costruire un circuito euleriano, …

Articoli correlati