Maîtriser le vocabulaire de la théorie des graphes : sommet, arête, degré, chemin, cycle.
Distinguer graphes orientés et non orientés ; lire et construire une matrice d'adjacence.
Reconnaître les graphes particuliers : arbres, graphes eulériens, hamiltoniens, bipartis.
Appliquer l'algorithme de Dijkstra pour trouver le plus court chemin dans un graphe pondéré.
Construire un arbre couvrant minimal (algorithmes de Kruskal et Prim).
Modéliser un projet par un réseau PERT : tâches, dépendances, dates au plus tôt et au plus tard.
Identifier le chemin critique et calculer les marges totale et libre.
Construire et interpréter un diagramme de Gantt.
Situation professionnelle — Chargé de projet en construction industrielle
Contexte : Maxime est chargé de projet dans une entreprise de construction
de bâtiments industriels. Il doit piloter la réhabilitation d'un entrepôt logistique :
démolition partielle, gros œuvre, charpente, isolation, installation électrique, plomberie,
revêtements, contrôles réglementaires, puis réception du chantier.
Son client exige une livraison dans les délais contractuels sous peine de pénalités.
Maxime doit donc :
Modéliser les tâches et leurs dépendances dans un réseau PERT.
Calculer la durée minimale du projet et identifier le chemin critique
(les tâches qui, si elles prennent du retard, retardent tout le projet).
Communiquer le planning à ses équipes via un diagramme de Gantt.
Optimiser l'acheminement des matériaux sur le chantier en modélisant le réseau de routes
par un graphe pondéré.
Ce chapitre vous donne les outils mathématiques pour mener ces analyses.
1. Théorie des graphes — notions fondamentales
1.1 Définitions de base
Définition — Graphe
Un graphe \(G = (V, E)\) est un couple formé de :
• un ensemble fini \(V\) de sommets (vertices, nœuds)
• un ensemble \(E\) d'arêtes (edges), chaque arête reliant deux sommets
Un graphe est non orienté si les arêtes n'ont pas de sens (\(\{u,v\} = \{v,u\}\)).
Il est orienté (digraphe) si les arêtes ont un sens (\((u,v) \neq (v,u)\)).
Dans ce cas les arêtes s'appellent des arcs.
Un graphe est pondéré si chaque arête porte une valeur numérique (poids, coût, durée, distance).
Graphe non orienté \(G=(V,E)\) avec 4 sommets et 5 arêtesGraphe orienté (digraphe) avec 4 sommets et 5 arcs
Définition — Degré d'un sommet
Dans un graphe non orienté, le degré \(d(v)\) d'un sommet \(v\)
est le nombre d'arêtes qui lui sont incidentes (on compte deux fois une boucle).
Dans un graphe orienté :
• Degré entrant \(d^-(v)\) : nombre d'arcs arrivant en \(v\)
• Degré sortant \(d^+(v)\) : nombre d'arcs partant de \(v\)
Lemme des poignées de mains :
\[\sum_{v \in V} d(v) = 2|E|\]
En particulier, le nombre de sommets de degré impair est toujours pair.
Application — Degrés et lemme des poignées de mains
Sur un chantier, cinq zones de stockage \(A, B, C, D, E\) sont reliées par des pistes de circulation.
Le graphe non orienté correspondant a pour arêtes :
\(A\text{–}B\), \(A\text{–}C\), \(A\text{–}D\), \(B\text{–}C\), \(C\text{–}D\), \(C\text{–}E\), \(D\text{–}E\).
Déterminer le degré de chaque sommet, puis vérifier le lemme des poignées de mains.
On compte, pour chaque sommet, le nombre d'arêtes qui lui sont incidentes :
• \(A\) est relié à \(B, C, D\) : \(d(A) = 3\)
• \(B\) est relié à \(A, C\) : \(d(B) = 2\)
• \(C\) est relié à \(A, B, D, E\) : \(d(C) = 4\)
• \(D\) est relié à \(A, C, E\) : \(d(D) = 3\)
• \(E\) est relié à \(C, D\) : \(d(E) = 2\)
Somme des degrés : \(3 + 2 + 4 + 3 + 2 = 14\).
Le graphe comporte \(|E| = 7\) arêtes, donc \(2|E| = 14\). Conclusion : \(\sum_v d(v) = \mathbf{14} = 2|E|\) — le lemme est vérifié.
Les sommets de degré impair sont \(A\) et \(D\) : ils sont bien au nombre de 2 (pair).
1.2 Matrice d'adjacence
Définition — Matrice d'adjacence
Pour un graphe \(G\) à \(n\) sommets numérotés \(1, \ldots, n\),
la matrice d'adjacence \(M\) est la matrice \(n \times n\) telle que :
\[M_{ij} = \begin{cases} 1 & \text{s'il existe une arête (ou un arc) de } i \text{ vers } j \\ 0 & \text{sinon} \end{cases}\]
Pour un graphe pondéré, on remplace 1 par le poids de l'arête (et \(\infty\) si pas d'arête).
Exemple — Graphe orienté à 4 sommets :
Arcs : \(1 \to 2\), \(1 \to 3\), \(2 \to 4\), \(3 \to 4\), \(4 \to 1\).
\[M = \begin{pmatrix} 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \end{pmatrix}\]
La matrice est en général non symétrique pour un graphe orienté,
et symétrique pour un graphe non orienté.
Application — Écrire une matrice d'adjacence
Un atelier modélise la circulation des pièces entre quatre postes numérotés \(1, 2, 3, 4\)
par un graphe orienté dont les arcs sont :
\(1 \to 2\), \(2 \to 3\), \(3 \to 1\), \(3 \to 4\), \(4 \to 2\).
Écrire la matrice d'adjacence \(M\) de ce graphe. Est-elle symétrique ?
On place un 1 en ligne \(i\), colonne \(j\) lorsqu'il existe un arc \(i \to j\) :
• ligne 1 : seul arc \(1 \to 2\) → \((0\;1\;0\;0)\)
• ligne 2 : seul arc \(2 \to 3\) → \((0\;0\;1\;0)\)
• ligne 3 : arcs \(3 \to 1\) et \(3 \to 4\) → \((1\;0\;0\;1)\)
• ligne 4 : seul arc \(4 \to 2\) → \((0\;1\;0\;0)\)
\[M = \mathbf{\begin{pmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 \end{pmatrix}}\]
La matrice n'est pas symétrique : par exemple \(M_{12} = 1\) alors que \(M_{21} = 0\),
ce qui est normal pour un graphe orienté. On vérifie aussi que la somme de tous les coefficients
vaut 5, soit le nombre d'arcs.
2. Chemins, chaînes et cycles
Définitions — Chemins et chaînes
Dans un graphe non orienté :
• Une chaîne est une suite de sommets \(v_0, v_1, \ldots, v_k\)
tels que \(\{v_{i-1}, v_i\} \in E\) pour tout \(i\). La longueur est \(k\).
• Un cycle est une chaîne dont les extrémités coïncident (\(v_0 = v_k\)).
Dans un graphe orienté :
• Un chemin est une suite d'arcs consécutifs orientés dans le même sens.
• Un circuit est un chemin dont les extrémités coïncident.
Définition — Connexité
Un graphe non orienté est connexe s'il existe une chaîne entre toute paire de sommets.
Un graphe orienté est fortement connexe s'il existe un chemin orienté
dans chaque sens entre toute paire de sommets.
2.1 Parcours de graphes
Algorithme BFS — Parcours en largeur (Breadth-First Search)
Explore le graphe niveau par niveau à partir d'un sommet source \(s\).
Utilise une file (FIFO).
Pseudo-code :
BFS(G, s):
marquer s comme visité
file ← [s]
TANT QUE file non vide :
v ← défiler(file)
POUR chaque voisin u de v :
SI u non visité :
marquer u comme visité
enfiler(file, u)
Complexité : \(O(|V| + |E|)\). Applications : plus court chemin (graphe non pondéré), test de connexité.
Algorithme DFS — Parcours en profondeur (Depth-First Search)
Explore aussi loin que possible avant de revenir en arrière. Utilise une pile (LIFO)
ou la récursion.
Pseudo-code récursif :
DFS(G, v):
marquer v comme visité
POUR chaque voisin u de v :
SI u non visité :
DFS(G, u)
Applications : détection de cycles, tri topologique, composantes connexes.
3. Graphes particuliers
3.1 Arbres et forêts
Définition — Arbre
Un arbre est un graphe connexe sans cycle.
Un arbre à \(n\) sommets a exactement \(n-1\) arêtes.
Une forêt est un graphe sans cycle (union d'arbres disjoints).
Un arbre couvrant d'un graphe connexe \(G\) est un arbre contenant tous les sommets de \(G\).
3.2 Graphe eulérien
Critère — Graphe eulérien
Un graphe connexe admet un cycle eulérien (parcourant chaque arête exactement une fois
et revenant au départ) si et seulement si tous ses sommets sont de degré pair.
Il admet une chaîne eulérienne (sans revenir au départ) si et seulement si
il possède exactement deux sommets de degré impair (départ et arrivée).
Exemple historique : le problème des 7 ponts de Königsberg n'a pas de solution car
les 4 sommets du graphe sont tous de degré impair.
Application — Cycle ou chaîne eulérienne ?
Un agent de contrôle doit inspecter toutes les galeries techniques d'un bâtiment, chacune
exactement une fois. Les locaux sont \(P, Q, R, S, T\) et les galeries (arêtes) sont :
\(P\text{–}Q\), \(P\text{–}R\), \(Q\text{–}R\), \(Q\text{–}S\), \(R\text{–}S\), \(R\text{–}T\), \(S\text{–}T\).
Ce graphe admet-il un cycle eulérien ? une chaîne eulérienne ? Si oui, préciser départ et arrivée.
Il y a exactement deux sommets de degré impair : \(Q\) et \(S\).
• Pas de cycle eulérien (il faudrait que tous les degrés soient pairs).
• Il existe une chaîne eulérienne, nécessairement de \(\mathbf{Q}\) à \(\mathbf{S}\)
(ou de \(S\) à \(Q\)). Exemple de parcours : \(Q \to P \to R \to Q \to S \to R \to T \to S\) :
les 7 galeries sont empruntées une seule fois.
3.3 Graphe hamiltonien
Définition
Un cycle hamiltonien passe par chaque sommet exactement une fois
(et revient au départ). Un graphe admettant un tel cycle est hamiltonien.
Contrairement au problème eulérien, il n'existe pas de critère simple en général
(problème NP-complet).
3.4 Graphe biparti
Définition
Un graphe est biparti si ses sommets peuvent être séparés en deux ensembles disjoints
\(U\) et \(V\) tels que chaque arête relie un sommet de \(U\) à un sommet de \(V\) (aucune arête
entre deux sommets du même ensemble). Exemple : graphe d'affectation (opérateurs — machines).
4. Plus court chemin — Algorithme de Dijkstra
Algorithme de Dijkstra
Trouve le plus court chemin depuis une source \(s\) vers tous les autres sommets
dans un graphe à arêtes de poids positifs.
Principe : greedy (glouton) — à chaque étape, on choisit le sommet non encore traité
ayant la distance provisoire minimale.
Dijkstra(G, s):
dist[s] ← 0 ; dist[v] ← ∞ pour tout v ≠ s
Q ← ensemble de tous les sommets
TANT QUE Q non vide :
u ← sommet de Q avec dist[u] minimale
retirer u de Q
POUR chaque voisin v de u :
alt ← dist[u] + poids(u, v)
SI alt < dist[v] :
dist[v] ← alt
parent[v] ← u
RETOURNER dist, parent
Complexité : \(O(|V|^2)\) naïf ; \(O((|V|+|E|)\log|V|)\) avec file de priorité.
Exemple — Réseau de livraison
Un livreur part du dépôt A et doit rejoindre le client F.
Le graphe pondéré (poids = distance en km) est :
A-B : 4 • A-C : 2 • B-D : 5 • B-E : 1 • C-B : 1 • C-D : 8 • D-F : 2 • E-F : 3
Étape 5 — choisir D (dist=8)
Voisins : F(8+2=10 > 7) — pas de mise à jour
Résultat : chemin le plus court A → C → B → E → F, distance = 7 km.
Application — Plus court chemin par Dijkstra
Une base vie \(S\) doit être reliée au poste de livraison \(T\) sur un chantier.
Le graphe pondéré des voies (poids en minutes de trajet) a pour arêtes :
\(S\text{–}A : 2\), \(S\text{–}B : 5\), \(A\text{–}B : 1\), \(A\text{–}C : 7\),
\(B\text{–}C : 3\), \(B\text{–}T : 9\), \(C\text{–}T : 2\).
Appliquer l'algorithme de Dijkstra depuis \(S\) et donner le trajet le plus rapide vers \(T\).
Trajet le plus rapide : \(\mathbf{S \to A \to B \to C \to T}\),
durée \(\mathbf{8}\) minutes (\(2+1+3+2 = 8\)). Vérification : \(S\text{–}B\text{–}T = 5+9 = 14\) et
\(S\text{–}A\text{–}C\text{–}T = 2+7+2 = 11\) : les deux sont bien plus longs que 8.
Limitation
L'algorithme de Dijkstra ne fonctionne pas avec des poids négatifs.
Dans ce cas, utiliser l'algorithme de Bellman-Ford
(complexité \(O(|V| \cdot |E|)\)) qui détecte aussi les cycles absorbants négatifs.
5. Arbre couvrant minimal
Un arbre couvrant minimal (ACM, ou MST en anglais) d'un graphe connexe pondéré
est un arbre couvrant dont la somme des poids des arêtes est minimale.
Application : relier \(n\) sites avec un câble réseau au coût minimum.
5.1 Algorithme de Kruskal
Algorithme de Kruskal
Stratégie : trier les arêtes par poids croissant et les ajouter une à une,
en évitant les cycles.
Kruskal(G):
Trier les arêtes E par poids croissant
T ← ensemble vide (arbre à construire)
POUR chaque arête (u, v) dans l'ordre trié :
SI l'ajout de (u,v) à T ne crée pas de cycle :
ajouter (u,v) à T
RETOURNER T
On utilise une structure Union-Find pour détecter les cycles efficacement. Complexité : \(O(|E| \log |E|)\).
5.2 Algorithme de Prim
Algorithme de Prim
Stratégie : partir d'un sommet quelconque et à chaque étape ajouter l'arête de poids minimal
reliant un sommet déjà dans l'arbre à un sommet extérieur.
Prim(G, r):
T ← {r} (sommet de départ)
TANT QUE T ne contient pas tous les sommets :
(u, v) ← arête de poids minimal avec u ∈ T et v ∉ T
ajouter v à T et l'arête (u,v) à l'ACM
Complexité : \(O(|E| \log |V|)\) avec file de priorité.
Exemple — Réseau de câblage de 5 sites :
Arêtes : A-B:4, A-C:2, B-C:5, B-D:10, C-D:3, C-E:8, D-E:7
Définition — Réseau PERT
La méthode PERT (Program Evaluation and Review Technique) représente un projet
comme un graphe orienté sans circuit où :
• Les arcs représentent les tâches (avec leur durée).
• Les nœuds représentent des étapes (débuts/fins de tâches).
• Une arête fictive (durée 0) peut représenter une contrainte d'antériorité sans tâche réelle.
On distingue le nœud initial (début du projet) et le nœud final (fin du projet).
6.2 Dates au plus tôt et au plus tard
Calcul des dates
Date au plus tôt (T⁺) d'une étape \(i\) :
la date la plus tôt à laquelle cette étape peut être atteinte.
\[T^+_i = \max_{j \in \text{prédécesseurs}} \bigl(T^+_j + d_{ji}\bigr)\]
On calcule par propagation vers l'avant (du nœud initial au nœud final),
en prenant le maximum des chemins arrivant à \(i\).
Date au plus tard (T⁻) d'une étape \(i\) :
la date la plus tard à laquelle cette étape peut être atteinte sans retarder le projet.
\[T^-_i = \min_{j \in \text{successeurs}} \bigl(T^-_j - d_{ij}\bigr)\]
On calcule par propagation vers l'arrière (du nœud final au nœud initial),
en prenant le minimum des chemins partant de \(i\).
Application — Dates au plus tôt d'un petit projet
Un chef de chantier planifie une intervention de cinq tâches :
Tâche
Durée (j)
Antérieures
A
4
—
B
3
—
C
5
A
D
2
A, B
E
4
C, D
Calculer la date de début au plus tôt de chaque tâche, puis la durée minimale du projet.
Propagation vers l'avant : on prend à chaque fois le maximum des fins au plus tôt
des tâches antérieures.
• \(A\) : sans antériorité → début 0, fin \(0+4 = 4\).
• \(B\) : sans antériorité → début 0, fin \(0+3 = 3\).
• \(C\) : après \(A\) → début 4, fin \(4+5 = 9\).
• \(D\) : après \(A\) et \(B\) → début \(\max(4\,;3) = 4\), fin \(4+2 = 6\).
• \(E\) : après \(C\) et \(D\) → début \(\max(9\,;6) = 9\), fin \(9+4 = 13\).
Débuts au plus tôt : \(A : 0\), \(B : 0\), \(C : 4\), \(D : \mathbf{4}\), \(E : \mathbf{9}\). Durée minimale du projet : \(\mathbf{13 \text{ jours}}\)
(chemin le plus long \(A \to C \to E\) : \(4+5+4 = 13\)).
6.3 Marge totale et marge libre
Définition — Marges d'une tâche \(ij\) de durée \(d_{ij}\)
Marge totale : \(MT_{ij} = T^-_j - T^+_i - d_{ij}\)
Retard maximum possible sur la tâche sans retarder la fin du projet.
Marge libre : \(ML_{ij} = T^+_j - T^+_i - d_{ij}\)
Retard maximum possible sans retarder le début au plus tôt des tâches suivantes.
6.4 Chemin critique
Définition — Chemin critique
Le chemin critique est le chemin le plus long (en durée) du réseau PERT,
du nœud initial au nœud final. Il donne la durée minimale du projet.
Une tâche est critique si et seulement si :
\[MT_{ij} = 0 \quad \Leftrightarrow \quad T^+_i = T^-_i \text{ et } T^+_j = T^-_j \text{ et } T^+_j = T^+_i + d_{ij}\]
Tout retard sur une tâche critique entraîne un retard de même durée sur la fin du projet.
Application — Marge totale et chemin critique
Un projet de réaménagement comporte cinq tâches :
Tâche
Durée (j)
Antérieures
A
3
—
B
5
—
C
4
A
D
6
B
E
2
C, D
Calculer la marge totale de la tâche \(C\), puis donner le chemin critique du projet.
1. Propagation vers l'avant (dates au plus tôt) :
\(A\) : 0 → 3 ; \(B\) : 0 → 5 ; \(C\) : 3 → 7 ; \(D\) : 5 → 11 ;
\(E\) : \(\max(7\,;11) = 11\) → 13.
Durée du projet : 13 jours.
2. Propagation vers l'arrière (dates au plus tard) :
Fin de projet : 13. \(E\) doit finir au plus tard à 13, donc commencer au plus tard à \(13-2 = 11\).
\(C\) et \(D\) doivent donc finir au plus tard à 11 : \(C\) commence au plus tard à \(11-4 = 7\),
\(D\) à \(11-6 = 5\).
\(A\) doit finir au plus tard à 7 ; \(B\) doit finir au plus tard à 5.
3. Marges totales :
\(MT_C = 11 - 3 - 4 = \mathbf{4 \text{ jours}}\) : la tâche \(C\) peut être retardée
(ou allongée) de 4 jours sans retarder le projet.
\(MT_A = 7 - 0 - 3 = 4\) ; \(MT_B = 5 - 0 - 5 = 0\) ; \(MT_D = 11 - 5 - 6 = 0\) ;
\(MT_E = 13 - 11 - 2 = 0\).
4. Chemin critique (tâches de marge nulle) :
\[\mathbf{B \to D \to E}\]
Vérification : \(5 + 6 + 2 = 13\) jours, soit exactement la durée du projet ✔
7. Application industrielle — Réseau PERT complet
Projet : Réhabilitation d'un entrepôt industriel. Le tableau ci-dessous
liste les 16 tâches, leurs durées (en jours) et leurs tâches antérieures.
Tâche
Description
Durée (j)
Antérieures
T⁺ début
T⁻ début
T⁺ fin
T⁻ fin
MT
A
Préparation du chantier
3
—
0
0
3
3
0
B
Démolition partielle
5
A
3
3
8
8
0
C
Évacuation des gravats
2
B
8
8
10
10
0
D
Fondations (gros œuvre)
8
C
10
10
18
18
0
E
Maçonnerie des murs
6
D
18
18
24
24
0
F
Charpente métallique
7
E
24
24
31
31
0
G
Couverture et toiture
5
F
31
31
36
36
0
H
Isolation thermique
4
G
36
36
40
40
0
I
Installation électrique (tableau)
3
E
24
38
27
41
14
J
Câblage électrique
5
I, G
36
41
41
46
5
K
Plomberie (alimentation)
4
G
36
36
40
40
0
L
Menuiserie et cloisons
6
H, K
40
40
46
46
0
M
Revêtements sol et mur
5
J, L
46
46
51
51
0
N
Contrôle électrique (CONSUEL)
1
J
41
50
42
51
9
O
Peinture et finitions
4
M, N
51
51
55
55
0
P
Réception et contrôle final
2
N, O
55
55
57
57
0
Chemin critique du projet
Le chemin critique (marges totales nulles) est :
\[\mathbf{A \to B \to C \to D \to E \to F \to G \to H \to L \to M \to O \to P}\]
Durée minimale du projet : \(\mathbf{57 \text{ jours}}\).
Les tâches I, J, N ont des marges positives : un léger retard sur celles-ci
n'allonge pas la durée du projet, mais doit rester dans les limites de la marge.
8. Diagramme de Gantt
Définition — Diagramme de Gantt
Le diagramme de Gantt est une représentation graphique du planning d'un projet.
Chaque tâche est représentée par une barre horizontale dont :
• la position en \(x\) correspond à la date de début
• la longueur correspond à la durée
Il complète le PERT en offrant une lecture directe des plages temporelles,
des ressources mobilisées et des possibilités de décalage.
Le diagramme de Gantt ci-dessous représente les premières tâches du projet de réhabilitation
(tâches du chemin critique en rouge, tâches avec marge en bleu) :
Définition — Coloration
Une coloration d'un graphe est une affectation d'une couleur à chaque sommet
de sorte que deux sommets adjacents (reliés par une arête) aient des couleurs différentes.
Le nombre chromatique \(\chi(G)\) est le nombre minimal de couleurs nécessaires.
Applications :
• Planification d'examens : les épreuves ayant des candidats communs doivent être
placées à des créneaux différents (sommets = épreuves, arêtes = conflits, couleurs = créneaux).
• Attribution de fréquences radio : deux antennes proches ne peuvent pas utiliser
la même fréquence (sommets = antennes, arêtes = interférences potentielles).
Propriétés
Si \(G\) est biparti et connexe : \(\chi(G) = 2\).
Si \(G\) contient un triangle (clique de taille 3) : \(\chi(G) \geq 3\).
Théorème des 4 couleurs : tout graphe planaire est 4-coloriable.
Algorithme glouton : donne une coloration avec au plus \(\Delta(G) + 1\) couleurs
(\(\Delta(G)\) = degré maximal), mais pas forcément optimale.
Méthode — Calcul du chemin critique (PERT)
Lister les tâches avec durées et antériorités (tableau).
Propagation vers l'avant : calculer \(T^+_i\) de gauche à droite.
À chaque nœud, prendre le maximum des (T⁺ prédécesseur + durée arc).
Propagation vers l'arrière : calculer \(T^-_i\) de droite à gauche.
Au nœud final : \(T^- = T^+\). À chaque nœud, prendre le minimum
des (T⁻ successeur – durée arc).