Graphes et ordonnancement
🟠 DifficileLes é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 graphe pondéré a pour arêtes : E–A (4), E–B (1), B–A (2), A–C (5), B–C (8), B–D (6), C–D (2), C–F (3), D–F (7).
a) Calcule de proche en proche les plus courtes distances depuis E vers chaque sommet.
b) Donne le chemin le plus court de E à F et sa longueur.Voir le corrigéoffert
a) E : 0. Voisins : A à 4, B à 1. On fixe B = 1.
Depuis B : A à 3 (mieux que 4), C à 9, D à 7. On fixe A = 3.
Depuis A : C à 8 (mieux que 9). On fixe D = 7.
Depuis D : C à 9 (pas mieux), F à 14. On fixe C = 8.
Depuis C : F à 11 (mieux que 14). On fixe F = 11.
Distances : A 3, B 1, C 8, D 7, F 11.
b) En remontant : F vient de C, C de A, A de B, B de E. Le chemin le plus court est E–B–A–C–F, de longueur 11. - 2
Un projet comporte les tâches : A (2 jours, aucune antériorité), B (4 jours, aucune antériorité), C (3 jours, après A), D (5 jours, après A et B), E (2 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, les marges et le chemin critique.Voir le corrigéoffert
a) A et B en 0. C en . D en . E en . Fin au jour : durée minimale 11 jours.
b) E au plus tard en ; C en ; D en ; A doit finir avant , donc commencer en 2 ; B doit finir avant 4, donc commencer en 0.
Marges : A 2, B 0, C 4, D 0, E 0.
Le chemin critique est B–D–E. - 3
On veut construire un réseau routier entre 7 villes, de sorte que chaque ville soit reliée directement à exactement 4 autres.
a) Calcule la somme des degrés du graphe correspondant.
b) Combien de routes faut-il construire ?🔒 Corrigé réservé aux abonnésS'abonner → - 4
On reprend le projet A (2 jours), B (4 jours), C (3 jours, après A), D (5 jours, après A et B), E (2 jours, après C et D), de durée minimale 11 jours, où A a une marge de 2 jours et D une marge nulle.
a) La tâche D prend 1 jour de retard : quelle est la nouvelle durée du projet ?
b) La tâche A prend 3 jours de retard : quelle est la nouvelle durée du projet ?🔒 Corrigé réservé aux abonnésS'abonner → - 5
Un graphe pondéré a pour arêtes : P–Q (10), P–R (3), R–S (2), S–Q (4), R–Q (8).
a) Calcule la longueur des chemins P–Q, P–R–Q et P–R–S–Q.
b) Détermine de proche en proche la plus courte distance de P à Q.🔒 Corrigé réservé aux abonnésS'abonner → - 6
Un graphe a pour sommets A, B, C, D, E, F et pour arêtes A–B, B–C, C–A, D–E et E–F.
a) Ce graphe est-il connexe ? Justifie.
b) Combien d'arêtes faut-il ajouter au minimum pour qu'il le devienne ? Donne un exemple.🔒 Corrigé réservé aux abonnésS'abonner → - 7
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).
a) Calcule les dates de début au plus tôt, la durée minimale et le chemin critique.
b) On raccourcit la tâche D d'un jour. Quelle est la nouvelle durée du projet ?🔒 Corrigé réservé aux abonnésS'abonner → - 8
Les temps de trajet, en minutes, entre les stations d'un réseau de bus sont : M–N (12), M–O (5), O–N (6), N–P (4), O–P (15), P–Q (3), N–Q (9).
a) Calcule de proche en proche les plus courts temps de trajet depuis M.
b) Donne l'itinéraire le plus rapide de M à Q et sa durée.🔒 Corrigé réservé aux abonnésS'abonner → - 9
Dans un groupe de cinq élèves A, B, C, D, E, les paires qui ont déjà travaillé ensemble sont : A et B, A et C, B et D, B et E, C et D, D et E.
a) Modélise la situation par un graphe et donne le degré de chaque sommet.
b) Vérifie le lemme des poignées de main.🔒 Corrigé réservé aux abonnésS'abonner → - 10
Un projet comporte les tâches : A (2 jours, aucune antériorité), B (3 jours, après A), C (1 jour, après A), D (4 jours, après B), E (2 jours, après C), F (1 jour, après D et E).
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.🔒 Corrigé réservé aux abonnésS'abonner →
Comment ça s'est passé ?
Retrouve tout dans Mon suivi.