Graphes et ordonnancement
Sommaire
Module 6 de l'unité U21. Les graphes modélisent les réseaux et les dépendances ; l'ordonnancement planifie un projet et identifie ce qui ne peut pas prendre de retard.
1. Vocabulaire
Graphe = sommets reliés par des arêtes (non orienté) ou des arcs (orienté).
| Terme | Définition |
|---|---|
| Ordre | Nombre de sommets du graphe |
| Degré d'un sommet | Nombre d'arêtes qui lui sont incidentes |
| Chaîne / chemin | Suite de sommets consécutivement reliés (chemin si orienté) |
| Cycle / circuit | Chaîne ou chemin qui revient à son point de départ |
| Graphe connexe | Il existe une chaîne entre toute paire de sommets |
| Graphe pondéré | Chaque arête porte un poids (distance, coût, durée, débit) |
| Graphe complet | Tous les sommets sont reliés deux à deux |
| Arbre | Graphe connexe sans cycle : n sommets et n − 1 arêtes |
La somme des degrés d'un graphe vaut toujours le double du nombre d'arêtes, puisque chaque arête est comptée à ses deux extrémités.
2. Représenter un graphe
Matrice d'adjacence
Matrice carrée M où mij = 1 s'il existe un arc de i vers j, 0 sinon (ou le poids, pour un graphe pondéré).
| de \ vers | A | B | C | D |
|---|---|---|---|---|
| A | 0 | 1 | 1 | 0 |
| B | 0 | 0 | 1 | 0 |
| C | 0 | 0 | 0 | 1 |
| D | 0 | 0 | 0 | 0 |
Propriété remarquable : le coefficient (i, j) de Mk donne le nombre de chemins de longueur k de i vers j. C'est l'application directe du produit matriciel.
Pour un graphe non orienté, la matrice est symétrique.
Liste d'adjacence
graphe = {
'A': ['B', 'C'],
'B': ['C'],
'C': ['D'],
'D': []
}Choix entre les deux : la matrice occupe n² cases quel que soit le nombre d'arêtes, la liste seulement ce qui existe. Sur un graphe creux (peu d'arêtes, comme un réseau routier), la liste est bien plus économique ; la matrice reste préférable pour tester rapidement l'existence d'un arc.
3. Parcours
| Parcours | Structure | Usage |
|---|---|---|
| En largeur (BFS) | File (FIFO) | Plus court chemin en nombre d'arêtes, propagation de proche en proche |
| En profondeur (DFS) | Pile (LIFO) ou récursion | Détection de cycles, composantes connexes, tri topologique |
Dans les deux cas, il faut marquer les sommets déjà visités : sans cela, un cycle provoque une boucle infinie.
4. Plus court chemin : Dijkstra
L'algorithme de Dijkstra trouve le plus court chemin d'un sommet vers tous les autres, dans un graphe pondéré à poids positifs.
- Attribuer une distance 0 au sommet de départ, +∞ à tous les autres.
- Choisir le sommet non traité de distance minimale et le marquer comme définitif.
- Pour chacun de ses voisins, si distance(courant) + poids < distance(voisin), mettre à jour la distance et mémoriser le prédécesseur.
- Répéter jusqu'à ce que tous les sommets soient traités.
Exemple de tableau d'exécution, départ en A :
| Étape | A | B | C | D | E | Sommet fixé |
|---|---|---|---|---|---|---|
| 0 | 0 | ∞ | ∞ | ∞ | ∞ | A |
| 1 | — | 4 (A) | 2 (A) | ∞ | ∞ | C |
| 2 | — | 3 (C) | — | 6 (C) | ∞ | B |
| 3 | — | — | — | 5 (B) | 9 (B) | D |
| 4 | — | — | — | — | 8 (D) | E |
On remonte ensuite les prédécesseurs pour reconstituer le chemin : E ← D ← B ← C ← A, de longueur 8.
C'est l'algorithme au cœur du protocole de routage OSPF : chaque routeur construit la carte du réseau puis applique Dijkstra pour déterminer le meilleur chemin vers chaque destination. Le lien avec la fiche Interconnexion et routage est direct.
5. Ordonnancement de projet
Un projet se décompose en tâches, chacune avec une durée et des antériorités (tâches qui doivent être terminées avant). On construit un graphe orienté sans circuit, puis on calcule les dates.
| Tâche | Durée (j) | Antériorités |
|---|---|---|
| A — Cahier des charges | 3 | — |
| B — Achat matériel | 5 | A |
| C — Câblage | 4 | A |
| D — Installation serveurs | 6 | B, C |
| E — Configuration réseau | 2 | C |
| F — Recette | 3 | D, E |
Dates au plus tôt (parcours avant)
Date au plus tôt d'une tâche = maximum des (date au plus tôt + durée) de ses prédécesseurs.
| Tâche | Calcul | Au plus tôt | Fin |
|---|---|---|---|
| A | — | 0 | 3 |
| B | fin de A | 3 | 8 |
| C | fin de A | 3 | 7 |
| D | max(8, 7) | 8 | 14 |
| E | fin de C | 7 | 9 |
| F | max(14, 9) | 14 | 17 |
La durée totale du projet est donc de 17 jours.
Dates au plus tard (parcours arrière)
On part de la fin du projet et l'on remonte : date au plus tard = minimum des (date au plus tard des successeurs − durée de la tâche).
| Tâche | Calcul | Au plus tard |
|---|---|---|
| F | 17 − 3 | 14 |
| E | 14 − 2 | 12 |
| D | 14 − 6 | 8 |
| C | min(8 − 4, 12 − 2) | 4 |
| B | 8 − 5 | 3 |
| A | min(3, 4) − 3 | 0 |
6. Marges et chemin critique
La marge totale d'une tâche est l'écart entre sa date au plus tard et sa date au plus tôt : c'est le retard qu'elle peut prendre sans décaler la fin du projet.
| Tâche | Au plus tôt | Au plus tard | Marge | Critique ? |
|---|---|---|---|---|
| A | 0 | 0 | 0 | oui |
| B | 3 | 3 | 0 | oui |
| C | 3 | 4 | 1 | non |
| D | 8 | 8 | 0 | oui |
| E | 7 | 12 | 5 | non |
| F | 14 | 14 | 0 | oui |
Chemin critique = la suite des tâches de marge nulle. Ici A → B → D → F, de durée 3 + 5 + 6 + 3 = 17 jours.
- Tout retard sur une tâche critique retarde le projet entier, jour pour jour.
- La tâche E dispose de 5 jours de marge : elle peut glisser sans conséquence.
- Pour raccourcir le projet, il faut agir sur le chemin critique — accélérer C ou E ne changerait rien.
Les deux méthodes classiques sont MPM (tâches aux sommets, la présentation ci-dessus) et PERT (tâches sur les arcs). Le résultat est identique ; seule la représentation diffère. Le diagramme de Gantt visualise ensuite le planning dans le temps.
À retenir
- Degré = nombre d'arêtes incidentes — somme des degrés = 2 × nb d'arêtes
- Arbre = connexe sans cycle → n sommets, n − 1 arêtes
- Coefficient (i,j) de Mk = nombre de chemins de longueur k
- Matrice = n² cases | liste d'adjacence = seulement les arêtes existantes
- BFS = file, plus court chemin en nombre d'arêtes | DFS = pile, cycles et composantes
- Dijkstra = plus court chemin pondéré, poids positifs → base d'OSPF
- Au plus tôt = max des prédécesseurs (parcours avant)
- Au plus tard = min des successeurs (parcours arrière)
- Marge = au plus tard − au plus tôt
- Chemin critique = tâches de marge nulle → tout retard décale le projet