Graphes et ordonnancement
🔴 ExpertLes énoncés sont gratuits, et les 2 premiers corrigés sont offerts. Les autres corrigés détaillés sont réservés aux abonnés.
- 1
Un livreur part du dépôt D pour rejoindre le client G. Les distances des tronçons, en km, sont : D–A (6), D–B (2), B–A (3), A–C (4), B–C (9), B–E (7), C–E (2), C–F (6), E–F (3), E–G (8), F–G (2).
Le tronçon B–E est fermé pour travaux : quel est le nouveau trajet le plus court de D à G, et sa longueur ?Voir le corrigéoffert
a) D : 0. B = 2 ; depuis B : A à 5 (mieux que 6), C à 11, E à 9. On fixe A = 5 ; depuis A : C à 9 (mieux que 11). On fixe C = 9 et E = 9 ; depuis C : F à 15 ; depuis E : F à 12, G à 17. On fixe F = 12 ; depuis F : G à 14.
Distances : A 5, B 2, C 9, E 9, F 12, G 14.
b) Le trajet le plus court est D–B–E–F–G, de longueur 14 km.
c) Sans B–E, E ne s'atteint plus que par C : E = . Alors F = et G = .
Le nouveau trajet le plus court est D–B–A–C–E–F–G, de longueur 16 km. - 2
La rénovation d'un appartement comporte les tâches suivantes (durées en semaines) : A démolition (2, aucune antériorité) ; B plomberie (3, après A) ; C électricité (2, après A) ; D plâtrerie (4, après B et C) ; E peinture (2, après D) ; F sols (3, après D) ; G nettoyage (1, après E et F).
La peinture (E) prend 2 semaines de retard : quelle est la nouvelle durée du chantier ?Voir le corrigéoffert
a) A en 0 ; B et C en 2 ; D en ; E et F en 9 ; G en . Durée minimale : 13 semaines.
b) G au plus tard en 12 ; E en 10 ; F en 9 ; D en ; B en 2 ; C en 3 ; A en 0.
Marges : A 0, B 0, C 1, D 0, E 1, F 0, G 0. Chemin critique : A–B–D–F–G.
c) E finit à la semaine : G commence en et finit en 14.
Le retard dépasse d'une semaine la marge de E : le chantier dure 14 semaines. - 3
Un réseau relie 6 serveurs par 8 câbles. Les degrés de cinq des serveurs sont 1, 2, 2, 3 et 3 ; on note x le degré du sixième.
Le serveur de degré x est-il relié directement à tous les autres ? Justifie.🔒 Corrigé réservé aux abonnésS'abonner → - 4
Un projet comporte les tâches : A (3 jours, aucune antériorité), B (2 jours, après A), C (4 jours, après A), D (3 jours, après B), E (1 jour, après C et D). Sa durée minimale est de 9 jours.
Le chef de projet ne peut raccourcir qu'une seule tâche, de 2 jours au plus. Quelle tâche doit-il choisir pour obtenir la durée la plus courte, et quelle durée obtient-il ?🔒 Corrigé réservé aux abonnésS'abonner → - 5
Un coursier va de S à T. Chaque tronçon est donné avec sa longueur et sa durée : S–A (10 km ; 8 min), S–B (6 km ; 12 min), A–B (3 km ; 2 min), A–T (12 km ; 9 min), B–T (9 km ; 15 min).
Chaque trajet coûte 0,50 € par km et 0,40 € par minute. Quel trajet de S à T revient le moins cher, et combien coûte-t-il ?🔒 Corrigé réservé aux abonnésS'abonner → - 6
Un projet comporte les tâches : A (4 jours, aucune antériorité), B (6 jours, aucune antériorité), C (3 jours, après A), D (2 jours, après B), E (5 jours, après C et D).
Les tâches A et C prennent chacune 1 jour de retard : quelle est la nouvelle durée du projet ?🔒 Corrigé réservé aux abonnésS'abonner → - 7
Une région compte 6 villes A, B, C, D, E, F. Les routes existantes relient A et B, B et C, C et A, D et E.
Combien de routes faut-il construire au minimum pour qu'on puisse aller de n'importe quelle ville à n'importe quelle autre ?🔒 Corrigé réservé aux abonnésS'abonner → - 8
Un graphe pondéré a pour arêtes : S–A (3), S–B (5), A–B (1), A–P (6), B–P (4), P–T (2), B–T (5).
Le livreur doit obligatoirement passer par P : quelle est la longueur du trajet le plus court de S à T passant par P ?🔒 Corrigé réservé aux abonnésS'abonner → - 9
L'organisation d'un concert comporte les tâches : A (2 jours, aucune antériorité), B (3 jours, aucune antériorité), C (4 jours, après A), D (2 jours, après B), E (3 jours, après C et D).
On ajoute une tâche F de 4 jours, qui doit suivre B et précéder E. Quels sont la nouvelle durée minimale et le nouveau chemin critique ?🔒 Corrigé réservé aux abonnésS'abonner → - 10
Dans un réseau informatique, les temps de transmission entre routeurs, en millisecondes, sont : R1–R2 (4), R1–R3 (1), R3–R2 (2), R2–R4 (5), R3–R4 (8), R3–R5 (10), R4–R5 (2), R4–R6 (6), R5–R6 (3).
Si la liaison R4–R5 tombe en panne, quel est le temps minimal de transmission de R1 à R6 ?🔒 Corrigé réservé aux abonnésS'abonner →
Comment ça s'est passé ?
Retrouve tout dans Mon suivi.