Problema del postino cinese

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.