13 chapitres3 h 30 minIntermédiaire
Mathématiques — Graphes et ordonnancement
Cours de graphes du BTS SIO (E3) : matrice d'adjacence, fermeture transitive, niveaux, Dijkstra, ordonnancement MPM et PERT, marges, exercices corrigés.
Par Josselyn C., prof de BTS SIO. Mis à jour le .
L'essentiel
Un graphe, c'est un ensemble de points (les sommets) reliés par des flèches (les arcs) : des routeurs reliés par des liens, des pages web reliées par des liens hypertexte, des tâches reliées par des contraintes d'ordre. La théorie des graphes donne des méthodes pour répondre à des questions concrètes : peut-on aller de tel sommet à tel autre ? Par combien de chemins ? Quel est le plus court ? Dans quel ordre faire les tâches d'un projet pour le finir au plus tôt ? « Graphes et ordonnancement » est un module du programme de l'épreuve E3 « Mathématiques pour l'informatique » du BTS SIO, commun aux options SLAM et SISR.
À la fin de ce cours, tu sauras :
- représenter un graphe orienté par un dessin, un tableau des successeurs ou des prédécesseurs et une matrice d'adjacence, et passer de l'un à l'autre ;
- reconnaître un chemin, un circuit, une boucle et un chemin hamiltonien ;
- compter les chemins de longueur p avec les puissances de la matrice d'adjacence, et calculer une fermeture transitive ;
- déterminer les niveaux d'un graphe sans circuit et le dessiner ordonné par niveaux ;
- trouver un chemin optimal en longueur et en valeur, en particulier avec l'algorithme de Dijkstra ;
- ordonnancer un projet avec la méthode MPM ou PERT : dates au plus tôt et au plus tard, chemin critique, marges totale, libre et certaine, diagramme de Gantt ;
- traiter un exercice de graphes ou d'ordonnancement de l'E3, de la question de cours à l'interprétation.
Ce que dit le programme. Le module « Graphes et ordonnancement » du programme de mathématiques des BTS (arrêté du 4 juin 2013, publié au Bulletin officiel n° 27 du 4 juillet 2013), repris par le référentiel du BTS SIO, a deux parties. Les graphes : graphe fini simple orienté et ses représentations, chemins, circuits, boucles, chemin hamiltonien, puissances entières et booléennes de la matrice d'adjacence, fermeture transitive, niveaux d'un graphe sans circuit, arborescence, chemin optimal en longueur et en valeur (chapitres 1 à 7). L'ordonnancement : méthode MPM ou méthode PERT, dates au plus tôt et au plus tard, tâches et chemins critiques, marges totale, libre et certaine, et la prise en compte d'une contrainte que le graphe ne modélise pas (chapitres 8 à 10). Le programme précise l'esprit : des situations concrètes très élémentaires, sans théorie générale, et des algorithmes que tu mets en œuvre à la main. Les graphes non orientés, les chaînes et cycles eulériens, la coloration et les arbres couvrants n'y figurent pas ; ils sont réunis au chapitre 11 comme complément.
Prérequis. Le calcul matriciel, surtout le produit de deux matrices, et le calcul booléen du cours de logique et d'algèbre de Boole (1 + 1 = 1). Le chapitre 4 rejoint la notion de relation transitive vue en théorie des ensembles. Les morceaux de Python supposent les bases du cours d'algorithmique.
Les notations. Les sommets sont notés par des lettres majuscules (A, B, C…). Un arc de A vers B s'écrit (A, B) ou A → B. Comme la lettre A désigne souvent un sommet, ce cours note S l'ensemble des sommets et U l'ensemble des arcs. Les successeurs d'un sommet x forment l'ensemble Γ⁺(x), ses prédécesseurs l'ensemble Γ⁻(x). Pour les matrices, M² est le produit ordinaire M × M, M^[2] le produit booléen, et M̂ (« M chapeau ») la matrice de la fermeture transitive. En ordonnancement, t(x) est la date de début au plus tôt de la tâche x, T(x) sa date de début au plus tard et d(x) sa durée.
Comment travailler. Un exercice de graphes se fait crayon en main : redessine chaque graphe, refais chaque tableau, recalcule chaque coefficient avant de lire la suite. Chaque chapitre se termine par des exercices dont la réponse est masquée ; cherche d'abord, ouvre ensuite. Pour vérifier un produit de matrices, la calculatrice en mode matrice ou trois lignes de Python suffisent, et le chapitre 3 te montre comment.
| Ton objectif | Chapitres à travailler en priorité |
|---|---|
| Découvrir les graphes | 1 et 2 |
| Réussir les questions de matrices d'adjacence de l'E3 | 1, 3 et 4, puis 12 |
| Comprendre les niveaux et les graphes sans circuit | 5, utile ensuite pour l'ordonnancement |
| Chercher un plus court chemin (routage, trajets) | 6 et 7 |
| Planifier un projet : MPM, PERT, Gantt | 8, 9 et 10 |
| Réviser la veille de l'épreuve | 12 et 13 |
Sommaire
Graphes et MPM
0 chapitre sur 13
- Chapitre 1 : Graphe orienté : sommets, arcs et représentations19 min
- Chapitre 2 : Chemins, circuits et chemin hamiltonien13 min
- Chapitre 3 : Puissances de la matrice d'adjacence et chemins de longueur p20 min
- Chapitre 4 : Fermeture transitive : sommes booléennes et algorithme de Roy-Warshall18 min
- Chapitre 5 : Niveaux d'un graphe sans circuit et arborescence16 min
- Chapitre 6 : Graphe valué et chemin optimal en longueur et en valeur14 min
- Chapitre 7 : Algorithme de Dijkstra : le plus court chemin pas à pas16 min
- Chapitre 8 : Ordonnancement : la méthode MPM et le chemin critique20 min
- Chapitre 9 : Marge totale, marge libre et marge certaine15 min
- Chapitre 10 : Méthode PERT, diagramme de Gantt et contraintes non modélisées18 min
- Chapitre 11 : Pour aller plus loin : graphes non orientés, Euler, coloration, arbres couvrants10 min
- Chapitre 12 : Exercices corrigés de graphes et d'ordonnancement type E322 min
- Chapitre 13 : Aide-mémoire : graphes et ordonnancement6 min
Questions fréquentes
C'est quoi un graphe orienté ?
Un graphe orienté est un ensemble de sommets reliés par des arcs, c'est-à-dire des flèches qui vont d'un sommet vers un autre : l'arc (A, B) va de A vers B, et il est différent de l'arc (B, A). On s'en sert pour modéliser des relations à sens unique : liens entre pages web, dépendances entre logiciels, contraintes d'ordre entre les tâches d'un projet. Au BTS SIO, on le représente par un dessin, un tableau des successeurs ou une matrice d'adjacence (graphe orienté et représentations).
Comment écrire la matrice d'adjacence d'un graphe ?
Range les sommets dans l'ordre imposé (souvent alphabétique), puis écris une ligne et une colonne par sommet. Le coefficient de la ligne x et de la colonne y vaut 1 s'il existe un arc de x vers y, et 0 sinon : la ligne d'un sommet donne ses successeurs, sa colonne ses prédécesseurs, et un 1 sur la diagonale signale une boucle. Le nombre de 1 est égal au nombre d'arcs, ce qui permet de vérifier la matrice (la matrice d'adjacence).
Comment trouver le nombre de chemins de longueur p entre deux sommets ?
Calcule la puissance Mᵖ de la matrice d'adjacence (le produit M × M × … × M, avec la calculatrice en mode matrice si besoin) : le coefficient de la ligne i et de la colonne j est le nombre de chemins de longueur p de i vers j. Avec la puissance booléenne M^[p], calculée avec 1 + 1 = 1, tu sais seulement s'il en existe au moins un. Pour écrire ces chemins, prolonge-les arc par arc avec le tableau des successeurs (puissances de la matrice d'adjacence).
Comment calculer la fermeture transitive d'un graphe ?
La fermeture transitive ajoute un arc de x vers y chaque fois qu'il existe un chemin de x vers y. Sa matrice est la somme booléenne M ⊕ M^[2] ⊕ … ⊕ M^[n], où n est le nombre de sommets, et on peut s'arrêter dès qu'une puissance n'ajoute plus aucun 1. L'algorithme de Roy-Warshall va plus vite : pour chaque sommet k, chaque ligne qui a un 1 dans la colonne k reçoit la ligne k par une somme booléenne (fermeture transitive).
C'est quoi un chemin hamiltonien ?
C'est un chemin qui passe une fois et une seule par chaque sommet du graphe ; dans un graphe à n sommets, il a donc n − 1 arcs. Pour en trouver un, commence par la source s'il y en a une et finis par le puits, puis avance de successeur en successeur sans repasser par un sommet ; deux sources ou deux puits rendent la recherche impossible. Dans un graphe sans circuit, il en existe un si et seulement si chaque niveau contient un seul sommet (chemin hamiltonien).
Comment déterminer les niveaux d'un graphe ?
Le graphe doit être sans circuit. Les sommets sans prédécesseur forment le niveau 0 ; on les raye des listes de prédécesseurs, et les sommets qui n'ont plus de prédécesseur non classé forment le niveau 1, et ainsi de suite. Un sommet est toujours au niveau qui suit le plus grand niveau de ses prédécesseurs ; si plus aucun sommet n'est libre avant la fin, le graphe a un circuit (niveaux d'un graphe).
Comment fonctionne l'algorithme de Dijkstra ?
Il calcule les plus courts chemins depuis un sommet de départ dans un graphe valué dont les valeurs sont positives ou nulles. Le départ a la marque 0, les autres ∞ ; à chaque étape, on fixe le sommet non fixé de plus petite marque, puis on met à jour ses successeurs non fixés si le passage par lui est plus court, en notant d'où l'on vient. On reconstruit enfin le chemin en remontant ces « vient de » depuis l'arrivée ; c'est l'algorithme qu'utilise le routage OSPF (Dijkstra pas à pas).
Comment trouver le chemin critique avec la méthode MPM ?
Calcule les dates au plus tôt de gauche à droite (t(x) = maximum de t(p) + d(p) sur les tâches antérieures), puis les dates au plus tard de droite à gauche (T(x) = minimum des T des tâches suivantes, moins la durée de x). Les tâches critiques sont celles où t = T, et le chemin critique relie Début à Fin en ne passant que par elles. Sa durée, égale à la date au plus tôt de Fin, est la durée minimale du projet (méthode MPM).
Quelle est la différence entre marge libre et marge totale ?
La marge totale (T − t) est le retard qu'une tâche peut prendre sans retarder la fin du projet. La marge libre est le retard qu'elle peut prendre sans retarder le début au plus tôt d'aucune tâche suivante : elle vaut la plus petite date au plus tôt des suivantes, moins la date de fin au plus tôt de la tâche. La marge libre est toujours inférieure ou égale à la marge totale, et la marge certaine, qui suppose que les tâches antérieures ont fini au plus tard, est plus petite encore (les trois marges).
Les graphes tombent-ils à l'E3 du BTS SIO ?
Oui : « Graphes et ordonnancement » est un module du programme de l'épreuve E3 « Mathématiques pour l'informatique », commune aux options SLAM et SISR. Les sujets demandent de représenter un graphe, d'interpréter des puissances de sa matrice d'adjacence, de calculer une fermeture transitive ou des niveaux, de trouver un chemin hamiltonien ou optimal, ou d'ordonnancer un projet avec MPM ou PERT. Le sujet de 2026, par exemple, posait un chemin hamiltonien, une matrice d'adjacence, sa puissance troisième et une fermeture transitive (sujets type E3 corrigés).