Problema del postino cinese

Questa voce sull'argomento matematica dell'informazione e della comunicazione è solo un abbozzo.

Contribuisci a migliorarla secondo le convenzioni di Wikipedia.

Il problema del postino cinese è un problema della teoria dei grafi formulato dal matematico cinese Mei-Ku Kwan (o Kuan) nel 1962. Consiste nella creazione di un cammino ciclico di lunghezza minima in un grafo non orientato che ne attraversi tutti i suoi archi.

Il nome del problema ("postino cinese") fu coniato da Alan Goldman del NIST.^[1]

In un grafo euleriano, la soluzione è rappresentata da un cammino euleriano, e la lunghezza del cammino più corto equivale al numero degli archi presenti.

Se un grafo non è euleriano deve contenere vertici di grado dispari. Per via del lemma della stretta di mano, devono esserci un numero pari di questo tipo di vertici. Si noti che si devono visitare archi che escono da questi vertici di grado dispari per risolvere il problema. La soluzione consiste nel rendere il grafo euleriano, raddoppiando gli archi che connettono coppie di vertici di grado dispari. Si scelgano coppie tali per cui la distanza complessiva coperta da tutti i percorsi che connettono questi vertici sia la minore possibile; ora che il grafo è euleriano, la soluzione del problema del postino cinese è quindi un suo percorso euleriano.

• Cammino euleriano
• Problema dei ponti di Königsberg
• Problema del commesso viaggiatore

• Wikimedia Commons contiene immagini o altri file su problema del postino cinese

• (EN) Chinese postman problem, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.
• (EN) Eric W. Weisstein, Problema del postino cinese, su MathWorld, Wolfram Research.

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica