Graphes : un nombre de chemins
Énoncé
Voici le tableau décrivant les différentes tâches pour la préparation d’une tarte à la rhubarbe meringuée.
Pour réaliser cette recette, on part du principe que certaines tâches peuvent être réalisées simultanément par plusieurs personnes.
Compléter le graphe donné ci-après pour respecter l’ordonnancement des tâches de cette recette. Indiquer au-dessus de chaque flèche le temps nécessaire à l’exécution de la tâche d’origine.
Par exemple, sur le graphe donné, la flèche allant de A vers B et pondérée par le nombre 8 indique que la tâche A dure 8 minutes et qu’elle doit se faire obligatoirement avant la tâche B.Quel est le temps minimum pour réaliser cette recette ? Expliquer.
Révéler le corrigé
Révéler le corrigé
Graphe complété
Déterminons le temps minimum pour réaliser la recette.
Déterminons d'abord le temps nécessaire pour atteindre la tâche H.
Trois chemins et leurs durées sont à envisager :
C - H : 8 min.
A - B - H : 8 + 2 = 10 min.
D - E - F - G - H : 8 + 15 + 4 + 5 = 32 min.
Puisque l'énoncé signale que certaines tâches peuvent être réalisées simultanément par plusieurs personnes, nous pouvons concevoir que ces trois chemins ont été effectués simultanément.
Donc au bout de 32 minutes, les tâches C - A - B - D - E - G - H sont exécutées.
Déterminons ensuite le temps nécessaire pour atteindre la tâche J.
Deux chemins et leurs durées sont envisageables :
H - J : 20 minutes à ajouter aux 32 minutes, soit 52 min.
I - J : 4 min.
À nouveau, nous pouvons concevoir que ces deux chemins ont été effectués simultanément.
Donc au bout de 52 minutes, les tâches sont exécutées jusqu'à la tâche J.
Déterminons également le temps nécessaire pour atteindre la tâche N.
Deux chemins et leurs durées sont possibles :
J - K - N : 1 + 10 = 11 minutes à ajouter aux 52 minutes, soit 63 min.
L - M : 5 min.
Une fois encore, nous pouvons concevoir que ces deux chemins ont été effectués simultanément.
Donc au bout de 63 minutes, les tâches sont exécutées jusqu'à la tâche N.
Nous atteindrons la fin des tâches par le chemin N - O - P dont la durée est 2 + 5 + 30 = 37 minutes à ajouter aux 63 minutes.
37 min + 63 min = 100 min.
Par conséquent, le temps minimum pour réaliser la recette est de 100 min, soit 1 h 40 min.