Prototype

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.

Si le propriétaire décide de tout faire lui-même, dans quel ordre doit-il procéder ?
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 ?
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).
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

Rendered by QuickLaTeX.com