Théorie des graphes : Exercice graphe tramway casa
Télécharger PDFExercice 1 : Théorie des graphes appliquée au tramway de Casablanca
L’inauguration du nouveau tramway de Casablanca était prévue le 1er juillet 2019. On suppose qu’au cours de l’année 2018, la Communauté Urbaine de Casablanca a lancé un appel d’offres pour des travaux prévus en 2019. Suite à cet appel d’offres, neuf entreprises désignées par les lettres A, B, C, D, E, F, G, H et K ont été retenues.
Le tableau suivant indique les antériorités pour les différents travaux à effectuer ainsi que leur durée, exprimée en semaines.
| Code des entreprises | Antériorités | Durée (en semaines) | |||
|---|---|---|---|---|---|
| A | 5 | B | 4 | ||
| C | A | 6 | D | B | 3 |
| E | B - C | 2 | |||
| F | C | 4 | |||
| H | D - E | 8 | |||
| D | B | 3 | |||
| K | E - F | 5 | |||
| N | H - K | 4 |
1. Déterminer le niveau des onze sommets du graphe G.
2. Construire le graphe G en ordonnant les sommets par niveau croissant.
3. (a) Calculer, en appliquant l’algorithme de Ford, les dates de début au plus tôt pour chaque entreprise.
(b) Déterminer le chemin de poids maximal entre le début (d) et la fin (f) et en déduire le chemin critique.
4. L’entreprise A a commencé à travailler le mardi 1er janvier 2019. Si tout se passe bien, l’inauguration pourra-t-elle avoir lieu comme prévu ?
5. L’entreprise E, suite à un incident imprévu, a mis trois semaines pour effectuer son travail. L’inauguration a-t-elle pu avoir lieu le lundi 1er juillet 2019 ?
FAQ
- Qu’est-ce qu’un chemin critique dans un projet ?
C’est le chemin le plus long en termes de durée, déterminant le délai minimal total pour achever le projet. - Comment interpréter les antériorités dans un graphe ?
Les antériorités indiquent les tâches qui doivent être terminées avant qu’une autre tâche ne puisse commencer. - Pourquoi l’algorithme de Ford est-il utilisé ici ?
Il permet de calculer les dates au plus tôt et au plus tard pour chaque activité dans un projet.