Graphes et ordonnancement

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).
a) Calcule de proche en proche les plus courtes distances depuis D.
b) Donne le trajet le plus court de D à G et sa longueur.
c) Le tronçon B–E est fermé pour travaux : quel est le nouveau trajet le plus court de D à G, et sa longueur ?

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).
a) Calcule les dates de début au plus tôt et la durée minimale du chantier.
b) Calcule les dates de début au plus tard, les marges et le chemin critique.
c) La peinture (E) prend 2 semaines de retard : quelle est la nouvelle durée du chantier ?

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.
a) Exprime la somme des degrés en fonction de x.
b) Détermine x.
c) Le serveur de degré x est-il relié directement à tous les autres ? Justifie.

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.
a) Donne les marges de toutes les tâches.
b) Raccourcir la tâche C de 2 jours change-t-il la durée du projet ? Justifie.
c) 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 ?

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).
a) Détermine le trajet le plus court en distance de S à T.
b) Détermine le trajet le plus rapide de S à T.
c) 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 ?

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).
a) Calcule les dates de début au plus tôt et la durée minimale.
b) Calcule les dates de début au plus tard et les marges.
c) Les tâches A et C prennent chacune 1 jour de retard : quelle est la nouvelle durée du projet ?

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.
a) Donne le degré de chaque ville dans le graphe des routes.
b) Ce graphe est-il connexe ? Justifie.
c) Combien de routes faut-il construire au minimum pour qu'on puisse aller de n'importe quelle ville à n'importe quelle autre ?

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).
a) Détermine la plus courte distance de S à T et le chemin correspondant.
b) Détermine la plus courte distance de S à P.
c) Le livreur doit obligatoirement passer par P : quelle est la longueur du trajet le plus court de S à T passant par P ?

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).
a) Calcule la durée minimale et le chemin critique.
b) 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 ?

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).
a) Calcule de proche en proche les plus courts temps de transmission depuis R1.
b) Donne le chemin le plus rapide de R1 à R6 et sa durée.
c) Si la liaison R4–R5 tombe en panne, quel est le temps minimal de transmission de R1 à R6 ?