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.
Note modifica
- ^ "Chinese Postman Problem", su nist.gov.
Voci correlate modifica
Altri progetti modifica
Wikimedia Commons contiene immagini o altri file su problema del postino cinese
Collegamenti esterni modifica
- (EN) Chinese postman problem, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.
- (EN) Eric W. Weisstein, Problema del postino cinese, su MathWorld, Wolfram Research.
