Graphes et ordonnancement
Fiche élève
Les énoncés du chapitre, à imprimer ou à travailler à l'écran. Sans compte !
Pour aller plus loin
Réservé aux abonnés : la fiche interactive, le corrigé et la fiche prof.
Fiche interactive
Cours + 1 atelier manipulable + exos auto-corrigés.
Corrigé
La correction détaillée, avec les rappels utiles.
Fiche prof
La version enseignant, pour préparer et animer.
Juste besoin de ce chapitre ? Débloquez-le pour 2,99 € : paiement unique, accès à vie (fiche interactive, corrigé, fiche prof et corrigés des exercices).
Avec un code de parrainage, c'est −20 % sur cette première commande.
Le chapitre en bref
Ce que tu vas savoir faire
- Décrire un graphe : sommets, arêtes, degré d'un sommet.
- Utiliser le lemme des poignées de main : la somme des degrés vaut le double du nombre d'arêtes.
- Déterminer un plus court chemin dans un petit graphe pondéré, par étiquetage de proche en proche.
- Représenter un projet par un graphe de précédence à partir d'un tableau de tâches et d'antériorités.
- Calculer les dates de début au plus tôt et au plus tard, la durée minimale du projet et les marges.
- Identifier le chemin critique et analyser l'effet d'un retard.
Le plan du chapitre
- 1Sommets, arêtes et degrés
- 2Chaînes et plus court chemin
- 3Organiser un projet : le graphe de précédence
- 4Dates, marges et chemin critique
À retenir
- Graphe : des sommets reliés par des arêtes. Degré d'un sommet = nombre d'arêtes qui en partent.
- Lemme des poignées de main : somme des degrés = 2 × nombre d'arêtes. Une somme impaire rend le graphe impossible.
- Plus court chemin : étiquettes de proche en proche, en gardant toujours le minimum. Le chemin le plus court n'est pas celui qui a le moins d'arêtes.
- Graphe de précédence : une flèche d'une tâche vers celles qui doivent l'attendre ; on range les tâches par niveaux.
- Début au plus tôt : maximum des fins des tâches antérieures (de gauche à droite).
- Début au plus tard : minimum des débuts au plus tard des tâches suivantes, moins la durée (de droite à gauche).
Les questions éclair
Qu'est-ce que le degré d'un sommet ?
Le nombre d'arêtes qui partent de ce sommet.
Que dit le lemme des poignées de main ?
La somme des degrés est égale au double du nombre d'arêtes : elle est donc toujours paire.
Comment calcule-t-on une date de début au plus tôt ?
C'est le maximum des dates de fin au plus tôt des tâches antérieures.
Qu'est-ce que la marge d'une tâche ?
Date au plus tard − date au plus tôt : le retard qu'elle peut subir sans retarder le projet.
Qu'est-ce que le chemin critique ?
L'ensemble des tâches de marge nulle : tout retard sur l'une d'elles retarde tout le projet.
Le sais-tu ?
La méthode du chemin critique est née en 1958, presque simultanément dans deux projets géants. La marine américaine l'utilisa sous le nom de PERT pour coordonner les milliers de sous-traitants du missile Polaris, et gagna, dit-on, deux ans sur le calendrier prévu. Au même moment, l'entreprise chimique DuPont mettait au point la méthode CPM pour planifier la maintenance de ses usines. Plus de soixante ans plus tard, les logiciels de gestion de projet utilisés pour construire un stade, lancer un satellite ou préparer des Jeux olympiques reposent toujours sur ces mêmes calculs de dates au plus tôt et au plus tard.