Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Problème du postier chinois
Résumé
vignette|Le graphe des arêtes du cube n'est pas eulérien (sommets de degré 3), mais peut l'être rendu en dédoublant quatre de ses douze arêtes, ce qui ajoute un degré à chaque sommet et fournit un parcours de postier.
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.
vignette|Ce support de table figure un parcours de postier non minimal (6 arêtes dédoublées).
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.
Le meilleur résultat qu'on puisse espérer est de trouver un chemin passant exactement une fois par chaque arête, c'est-à-dire un cycle eulérien. Un tel chemin existe si et seulement si chaque sommet du graphe est de degré pair.
Dans le cas contraire, un chemin optimal passe au moins deux fois par une arête. Il est plus simple de considérer l'approche alternative du problème : plutôt que de permettre d'emprunter plusieurs fois la même arête, on duplique les arêtes du graphe par lesquelles on souhaite passer plusieurs fois. Le but est alors de compléter le graphe pour le rendre eulérien, en minimisant la longueur totale des arêtes ajoutées. On obtient une solution du problème initial en cherchant un circuit eulérien dans le graphe complété. On rappelle pour la suite que dans toute composante connexe d'un graphe, la somme des degrés des sommets est le double du nombre d'arêtes, donc est paire.
Pour comprendre la solution générale, il est utile de commencer par le cas où exactement deux sommets u et v sont de degré impair.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.