Metraipolis › archive › dc_359183c87d53
Problema del postino cinese — Wikipedia
- Source
- Wikipedia (it)
- Original
- https://it.wikipedia.org/wiki/Problema_del_postino_cinese
- License (as archived)
- CC-BY-SA-4.0
- Archived
- 2026-10-07T14:48:38.315Z
- SHA-256 of the archived text
02bb3a853a79f817d85081e0a88305518634d786d6ae686be7222b7b7f320ca4- Stable URL of this page
https://metraipolis.com/documento/dc_359183c87d53
How to cite
Problema del postino cinese — Wikipedia — Wikipedia (it), https://it.wikipedia.org/wiki/Problema_del_postino_cinese (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_359183c87d53 (Metraipolis archive dc_359183c87d53, sha256 02bb3a853a79f817d85081e0a88305518634d786d6ae686be7222b7b7f320ca4)
BibTeX
@misc{dc359183c87d53,
title = {Problema del postino cinese — Wikipedia},
howpublished = {Wikipedia (it)},
url = {https://it.wikipedia.org/wiki/Problema_del_postino_cinese},
note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_359183c87d53; sha256 02bb3a853a79f817d85081e0a88305518634d786d6ae686be7222b7b7f320ca4},
year = {2026}
}Archived text
Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (it), https://it.wikipedia.org/wiki/Problema_del_postino_cinese. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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. 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.
Tema degli esploratori: matematica e informatica teorica (deposito sistematico; ricerca «teoria dei grafi»).
Fonte: Wikipedia in italiano, voce «Problema del postino cinese» — https://it.wikipedia.org/wiki/Problema_del_postino_cinese
Wikidata Q901096 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q901096
Autori: i contributori di Wikipedia (cronologia: https://it.wikipedia.org/wiki/Problema_del_postino_cinese?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 131916966, consultata il 2026-10-07T14:21:41.005Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 90fb60338123b9de0de4990a12227cc45ffb59f64dd32f09927946792fccb8d5