Parcours d’arbres

Prototype


Version de

Exemples de problèmes formalisables par des graphes

Choix d’un itinéraire
\label{itineraire} Sachant que la gare de Poitiers est inutilisable, et connaissant la durée des trajets suivants :  {% \scriptsize \begin{tabular}{rclcl} Bordeaux & $\rightarrow$ & Nantes & & 4 h \\ Bordeaux & $\rightarrow$ & Marseille & & 9 h \\ Bordeaux & $\rightarrow$ & Lyon & & 12 h \\ Nantes & $\rightarrow$ & Paris-Mtparn. & & 2 h\\ Nantes & $\rightarrow$ & Lyon & & 7 h \\ Paris-Mtparn. & $\rightarrow$ & Paris-Lyon & & 1 h \\ Paris-Lyon & $\rightarrow$ & Grenoble & & 4 h 30\\ Marseille & $\rightarrow$ & Lyon & & 2 h 30 \\ Marseille & $\rightarrow$ & Grenoble & & 4 h 30\\ Lyon & $\rightarrow$ & Grenoble & & 1 h 15\\ \end{tabular} } comment faire pour aller le plus rapidement possible de Bordeaux à Grenoble ? Les données du problème sont faciles à représenter par un graphe dont les arêtes sont étiquetées par les durées des trajets :

Rendered by QuickLaTeX.com

Il s’agit de déterminer, dans ce graphe, le plus court chemin (ou l’un des plus courts chemins, s’il existe plusieurs solutions) entre Bordeaux et Grenoble.

Le problème du voyageur de commerce

Un voyageur de commerce habitant Bordeaux doit effectuer une tournée passant par Lyon, Nantes et Paris :

Rendered by QuickLaTeX.com

Dans quel ordre devrait-il effectuer ses déplacements de façon à minimiser le trajet parcouru ? C’est le problème classique du voyageur de commerce (TSP : Traveling Salesman Problem): il s’agit de déterminer dans le graphe un circuit élémentaire passant par chaque sommet (circuit hamiltonien), de façon à ce que la somme des distances d’un sommet à un autre soit minimale, les distances étant données par le tableau
Bordeaux Lyon Nantes Paris
Bordeaux 780 320 580
Lyon 780 700 460
Nantes 320 700 380
Paris 580 460 380
  Le problème pourrait être résolu en examinant tous les ordonnancements possibles des sommets au départ de Bordeaux ; si l’on part d’un graphe à n sommets, cela donne n\! possibilités, ce qui conduit à un algorithme irréalisable, en pratique.

Planification de travaux

Pour rénover une maison, il est prévu de refaire l’installation électrique (3 jours), de réaménager (5 jours) et de carreler (2 jours) la salle de bains, de refaire le parquet de la salle de séjour (6 jours) et de repeindre les chambres (3 jours), la peinture et le carrelage ne devant être faits qu’après réfection de l’installation électrique.
  1. Si le propriétaire décide de tout faire lui-même, dans quel ordre doit-il procéder ?
  2. Si la rénovation est faite par une entreprise et que chacune des tâches est accomplie par un employé différent, quelle est la durée minimale des travaux ?
  3. On peut représenter les différentes tâches à effectuer par les sommets d’un graphe dont les arcs correspondent aux contraintes de précédence :\bigskip% \includegraphics{Figures/travaux1.eps}Il s’agit de numéroter les sommets du graphe de façon à respecter les relations de précédence (les successeurs d’un sommet doivent avoir des numéros supérieurs à celui de ce sommet).
  4. On peut représenter les différentes étapes de la rénovation sur un graphe dont les arcs sont étiquetés par la durée minimale séparant deux étapes

  5. Rendered by QuickLaTeX.com

    Il s’agit de déterminer la durée du plus long chemin du début à la fin des travaux.
Parcours d’arbres