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.8 corrigés détaillés pas à pas restent à débloquer
Chacun reprend l'énoncé, montre le calcul étape par étape et dit où se trouve le piège.
Le pack de révision, gratuit
L'essentiel des dix premiers chapitres du programme, en PDF : ce qu'il faut retenir et les questions qui vérifient que c'est acquis. Puis 5 e-mails sur 14 jours, et c'est tout.
- 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é détailléVoir ce qu'il contient → - 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é détailléVoir ce qu'il contient → - 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é détailléVoir ce qu'il contient → - 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é détailléVoir ce qu'il contient → - 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é détailléVoir ce qu'il contient → - 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é détailléVoir ce qu'il contient → - 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é détailléVoir ce qu'il contient → - 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.
Comment ça s'est passé ?
Retrouve tout dans Mon suivi.
Le pack de révision, gratuit
L'essentiel des dix premiers chapitres du programme, en PDF : ce qu'il faut retenir et les questions qui vérifient que c'est acquis. Puis 5 e-mails sur 14 jours, et c'est tout.
Partager avec ma classe
Les énoncés de cette page sont gratuits et s'ouvrent sans compte : l'adresse peut être donnée telle quelle, au tableau ou dans l'espace numérique de travail.