Problème du postier chinois

Problème du postier chinois

En théorie des graphes, le problème du postier chinois consiste à trouver un plus court chemin dans un graphe connexe non orienté qui passe au moins une fois par chaque arête du graphe 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[1], 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 de poids maximum, et ainsi être résolu en temps polynomial dans le cas général.

Méthode de résolution

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. La solution optimale consiste alors à calculer un plus court chemin de u à v (par exemple en utilisant l'algorithme de Dijkstra), et à compléter le graphe avec les arêtes de ce chemin.

Démonstration : après avoir ajouté les arêtes du plus court chemin, chaque sommet est bien de degré pair, donc le graphe est eulérien et la solution est valide. De plus, dans le graphe des arêtes ajoutées pour n'importe quelle solution valide, seuls u et v sont de degré impair. Ils ne peuvent pas être dans des composantes connexes différentes, sinon les sommes des degrés de ces composantes seraient impaires, donc u et v sont reliés par un chemin. Par conséquent, la solution proposée est bien optimale.

Dans le cas général, il y a toujours un nombre pair de sommets de degré impair. La solution optimale peut être obtenue par l'algorithme suivant[2] :

  • Former un nouveau graphe G’, constitué uniquement des sommets de degré impair dans le graphe initial G.
  • Entre deux sommets de G’, ajouter une arête dont la longueur est celle du plus court chemin entre les deux sommets dans G.
  • Trouver un couplage parfait de poids minimum dans G’, ce qu'on peut calculer avec un algorithme de complexité O(n3).
  • Pour chaque paire de sommets u et v couplés dans G’, ajouter au graphe initial G les arêtes du plus court chemin de u à v.

Voir aussi

Références

  1. Douglas B. West, Introduction to Graph Theory, 2001, Prentice-Hall.
  2. J. Edmonds and E.L. Johnson, Matching Euler tours and the Chinese postman problem, Mathematical programming, 1973.

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Problème du postier chinois de Wikipédia en français (auteurs)

Игры ⚽ Нужен реферат?

Regardez d'autres dictionnaires:

  • Problème du voyageur de commerce — Si un voyageur part du point A et que les distances entre toutes les villes sont connues, quel est le plus court chemin pour visiter tous les points et revenir au point A ? Le problème du voyageur de commerce consiste, étant donné un… …   Wikipédia en Français

  • Graphe eulérien — En théorie des graphes, on dit d un graphe non orienté qu il est « eulérien » en référence à Euler (la plupart des mathématiciens écrivent « Eulérien » à cause de l usage anglo saxon) s il a la propriété suivante : On… …   Wikipédia en Français

  • Cycle (théorie des graphes) — Pour les articles homonymes, voir Cycle. Dans un graphe non orienté, un cycle est une suite d arêtes consécutives (chaîne) dont les deux sommets extrémités sont identiques. Si la chaîne est élémentaire, c est à dire ne passe pas deux fois par un… …   Wikipédia en Français

  • Eric Cartman (personnage) — Eric Cartman Pour les articles homonymes, voir Cartman. Eric Theodore Cartman Personnage de South P …   Wikipédia en Français

  • Eric Theodore Cartman — Eric Cartman Pour les articles homonymes, voir Cartman. Eric Theodore Cartman Personnage de South P …   Wikipédia en Français

  • Éric Cartman — Eric Cartman Pour les articles homonymes, voir Cartman. Eric Theodore Cartman Personnage de South P …   Wikipédia en Français

  • Eric Cartman — Pour les articles homonymes, voir Cartman. Eric Théodore Cartman Personnage de fiction apparaissant dans …   Wikipédia en Français

  • Liste des épisodes de Sonny — Voici la liste des épisodes de la série Sonny. Saisons Épisodes Première Diffusion Dernière Diffusion 1 21 13 mai 2009 Inconnu 2 26 …   Wikipédia en Français

  • Les Aventures de Sherlock Holmes : La Nuit des sacrifiés — Sherlock Holmes La Nuit des Sacrifiés Éditeur Focus Home Interactive Développeur …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”