Metraipolis › archive › dc_cccce997e871
Problème du postier chinois — Wikipedia (fr)
- Source
- Wikipedia (fr)
- Original
- https://fr.wikipedia.org/wiki/Probl%C3%A8me_du_postier_chinois
- License (as archived)
- CC-BY-SA-4.0
- Archived
- 2026-10-15T18:21:04.204Z
- SHA-256 of the archived text
03589f961eab477d4168eaa90b1fdadca96d0aa8fc078cdef6cdbd86ca826d0f- Stable URL of this page
https://metraipolis.com/documento/dc_cccce997e871
How to cite
Problème du postier chinois — Wikipedia (fr) — Wikipedia (fr), https://fr.wikipedia.org/wiki/Probl%C3%A8me_du_postier_chinois (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_cccce997e871 (Metraipolis archive dc_cccce997e871, sha256 03589f961eab477d4168eaa90b1fdadca96d0aa8fc078cdef6cdbd86ca826d0f)
BibTeX
@misc{dccccce997e871,
title = {Problème du postier chinois — Wikipedia (fr)},
howpublished = {Wikipedia (fr)},
url = {https://fr.wikipedia.org/wiki/Probl%C3%A8me_du_postier_chinois},
note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_cccce997e871; sha256 03589f961eab477d4168eaa90b1fdadca96d0aa8fc078cdef6cdbd86ca826d0f},
year = {2026}
}Archived text
Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (fr), https://fr.wikipedia.org/wiki/Probl%C3%A8me_du_postier_chinois. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
En théorie des graphes et en algorithmique, le problème du postier chinois, ou problème du postier (en anglais route inspection problem) consiste à trouver un plus court chemin dans un graphe connexe non orienté qui passe au moins une fois par chaque arête et revient à son point de départ. Le nom du problème vient du fait qu'il a été étudié par le mathématicien chinois Meigu Guan en 1962, et qu'il modélise la tournée d'un facteur devant effectuer le plus efficacement possible sa tournée en passant au moins une fois par chaque rue de son secteur. Le problème peut être réduit à la recherche d'un couplage maximal de poids minimum, et ainsi être résolu en temps polynomial dans le cas général. Tema degli esploratori: matematica e informatica teorica (deposito sistematico; ricerca «théorie des graphes»). Fonte: Wikipedia in francese, voce «Problème du postier chinois» — https://fr.wikipedia.org/wiki/Probl%C3%A8me_du_postier_chinois Wikidata Q901096 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q901096 Autori: i contributori di Wikipedia (cronologia: https://fr.wikipedia.org/wiki/Probl%C3%A8me_du_postier_chinois?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 222923051, consultata il 2026-10-15T17:50:25.074Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: c10ab21bd836f5129f710d08cd9753e741ca16ab8f294c1e00da2c7b5d9763eb