Chapitre 136 minIntermédiaire
Aide-mémoire : graphes et ordonnancement
Par Josselyn C., prof de BTS SIO. Mis à jour le .
À la fin de ce chapitre, tu sauras
- retrouver en un coup d'œil une définition, une formule ou une méthode ;
- éviter les erreurs qui coûtent le plus de points.
Cet aide-mémoire rassemble les définitions, les formules et les méthodes du module « Graphes et ordonnancement » de l'E3 du BTS SIO, chapitre par chapitre, avec les erreurs qui coûtent le plus de points. Il sert à réviser la veille de l'épreuve ou à retrouver une formule en cours d'exercice ; chaque ligne renvoie au chapitre qui l'explique.
Le vocabulaire des graphes
| Notion | Définition | Chapitre |
|---|---|---|
| Graphe orienté | des sommets et des arcs ; un arc (x, y) va de x vers y | 1 |
| Successeur, prédécesseur | dans l'arc (x, y), y est successeur de x, x prédécesseur de y | 1 |
| Boucle | arc (x, x) | 1 |
| Source, puits | sommet sans prédécesseur ; sommet sans successeur | 1 |
| Chemin, longueur | suite de sommets reliés par des arcs ; longueur = nombre d'arcs | 2 |
| Circuit | chemin qui revient à son origine (une boucle est un circuit de longueur 1) | 2 |
| Chemin hamiltonien | passe une fois et une seule par chaque sommet : n − 1 arcs | 2 |
| Fermeture transitive | arc (x, y) dès qu'il existe un chemin de x vers y | 4 |
| Niveau (graphe sans circuit) | longueur du plus long chemin qui arrive au sommet ; niveau 0 = sources | 5 |
| Arborescence | une racine sans prédécesseur, tout autre sommet a un seul prédécesseur et est atteint depuis la racine | 5 |
| Graphe valué, valeur d'un chemin | chaque arc porte un nombre ; valeur = somme des valeurs des arcs | 6 |
Les matrices
- Matrice d'adjacence : coefficient (i, j) = 1 s'il y a un arc du sommet i vers le sommet j, 0 sinon. Ligne = origine, colonne = extrémité. Ligne de x : ses successeurs ; colonne de x : ses prédécesseurs ; diagonale : les boucles ; nombre de 1 : le nombre d'arcs.
- Puissance entière : (Mᵖ)ᵢⱼ = nombre de chemins de longueur p de i vers j ; (Mᵖ)ᵢᵢ = nombre de circuits de longueur p passant par i.
- Calcul booléen : 1 ⊕ 1 = 1 ; 1 ⊗ 1 = 1 ; le reste comme d'habitude.
- Puissance booléenne : (M^[p])ᵢⱼ = 1 s'il existe un chemin de longueur p de i vers j. On l'obtient en remplaçant par 1 les coefficients non nuls de Mᵖ.
- Fermeture transitive : M̂ = M ⊕ M^[2] ⊕ … ⊕ M^[n] (n sommets) ; on peut s'arrêter dès qu'une puissance n'ajoute rien.
- Roy-Warshall : pour k = 1 à n, chaque ligne i qui a un 1 en colonne k devient ligne i ⊕ ligne k.
- Lire M̂ : arcs à ajouter = 1 de M̂ absents de M ; un 1 sur la diagonale = sommet sur un circuit ; diagonale nulle = graphe sans circuit.
Les méthodes sur les graphes
| Question | Méthode |
|---|---|
| Trouver un chemin hamiltonien | une source commence, un puits finit (deux sources ou deux puits : impossible) ; avancer de successeur en successeur ; sans circuit : un sommet par niveau |
| Déterminer les niveaux | niveau 0 = sans prédécesseur ; on raye les sommets classés ; un sommet entre au niveau suivant quand tous ses prédécesseurs sont classés ; blocage = circuit |
| Plus court chemin en longueur | marquer en couches (0, 1, 2…) ou chercher le plus petit p tel que (M^[p])ᵢⱼ = 1 |
| Chemin optimal en valeur, sans circuit | niveau par niveau, marque = min (ou max) sur les prédécesseurs de (marque + valeur de l'arc), puis remonter |
| Chemin minimal, avec circuits, valeurs ≥ 0 | Dijkstra : fixer le sommet non fixé de plus petite marque, mettre à jour ses successeurs non fixés, remonter les « vient de » |
| Principe d'optimalité | tout sous-chemin d'un chemin optimal est optimal |
L'ordonnancement
| Étape | Formule ou règle | Chapitre |
|---|---|---|
| Graphe MPM | une tâche = un sommet, + Début et Fin ; arc de x vers ses suivantes, valeur d(x) | 8 |
| Date au plus tôt | t(Début) = 0 ; t(x) = max [ t(p) + d(p) ] sur les antérieures, de gauche à droite | 8 |
| Durée minimale | t(Fin) | 8 |
| Date au plus tard | T(Fin) = t(Fin) ; T(x) = min [ T(s) ] − d(x) sur les suivantes, de droite à gauche | 8 |
| Tâche critique, chemin critique | t = T ; chemin de Début à Fin formé de tâches critiques, de valeur maximale | 8 |
| Marge totale | MT = T − t | 9 |
| Marge libre | ML = min [ t(s) ] − t(x) − d(x) | 9 |
| Marge certaine | MC = max [ 0 ; min [ t(s) ] − max [ T(p) + d(p) ] − d(x) ] | 9 |
| Ordre des marges | 0 ≤ MC ≤ ML ≤ MT | 9 |
| PERT (tâche de l'étape i à l'étape j) | début au plus tard Tⱼ − d ; MT = Tⱼ − tᵢ − d ; ML = tⱼ − tᵢ − d ; MC = max [ 0 ; tⱼ − Tᵢ − d ] | 10 |
| Effet d'un retard r | r ≤ ML : aucun ; ML < r ≤ MT : suivantes décalées, fin inchangée ; r > MT : fin retardée de r − MT | 9 |
| Contrainte non modélisée | placer au plus tôt sur le Gantt, repérer le conflit, décaler les tâches qui ont de la marge, calculer le retard éventuel | 10 |
Les erreurs qui coûtent le plus de points
- Inverser lignes et colonnes de la matrice d'adjacence : la convention est ligne = origine.
- Confondre longueur et valeur d'un chemin, ou longueur et nombre de sommets : (A, B, C) a pour longueur 2.
- Calculer Mᵖ coefficient par coefficient (en élevant chaque 0 ou 1 à la puissance p) au lieu de faire un vrai produit de matrices.
- Oublier que 1 ⊕ 1 = 1 dans une somme ou un produit booléen.
- Classer un sommet dans un niveau alors qu'un de ses prédécesseurs n'est pas encore classé.
- Prendre le minimum pour les dates au plus tôt ou le maximum pour les dates au plus tard : au plus tôt, max vers la droite ; au plus tard, min vers la gauche.
- Soustraire la durée de la tâche suivante au lieu de la durée de la tâche elle-même pour T(x).
- Additionner les marges totales de tâches successives : elles sont partagées.
- Appliquer Dijkstra avec une valeur négative, ou modifier un sommet déjà fixé.
- Conclure sans le contexte : chaque résultat doit être traduit dans les mots de l'énoncé.