Fiche résumé – Graphes et ordonnancement

Chapitre 24 | BTS | Mathématiques

Dernière mise à jour : 21 juin 2026

L'essentiel :

Un graphe \(G=(V,E)\) : sommets et arêtes (ou arcs si orienté) ; lemme des poignées de mains \(\sum_v d(v)=2|E|\).
Dijkstra donne le plus court chemin (poids \(\geq0\)) ; Kruskal/Prim donnent l'arbre couvrant minimal.
PERT : dates au plus tôt \(T^+\) (propagation avant, MAX), au plus tard \(T^-\) (propagation arrière, MIN).
Le chemin critique est le chemin le plus long : ses tâches ont une marge totale nulle ; sa longueur = durée minimale du projet.

Définitions clés

Définition

Degré \(d(v)\) : nombre d'arêtes incidentes à \(v\). En orienté : degré entrant \(d^-\), sortant \(d^+\).

Définition

Arbre : graphe connexe sans cycle ; un arbre à \(n\) sommets a exactement \(n-1\) arêtes. Arbre couvrant minimal : arbre couvrant de somme de poids minimale.

Définition

Marge totale d'une tâche \(ij\) : \(MT_{ij}=T^-_j-T^+_i-d_{ij}\). Marge libre : \(ML_{ij}=T^+_j-T^+_i-d_{ij}\).

Graphe non orienté : 4 sommets, 5 arêtes

Formules et critères à connaître

Degrés et matrice d'adjacence \[\sum_{v\in V}d(v)=2|E|\qquad M_{ij}=\begin{cases}1&\text{arête (ou arc) de }i\text{ vers }j\\0&\text{sinon}\end{cases}\]

Pour un graphe pondéré, on remplace \(1\) par le poids (et \(\infty\) s'il n'y a pas d'arête).

Dates PERT \[T^+_i=\max_{j\,\text{préd.}}\bigl(T^+_j+d_{ji}\bigr)\qquad T^-_i=\min_{j\,\text{succ.}}\bigl(T^-_j-d_{ij}\bigr)\]

Tâche critique \(\Leftrightarrow MT_{ij}=0\). Durée du projet = \(T^+\) du nœud final.

Critères et propriétés

Cycle eulérien (chaque arête une fois, retour au départ) ⇔ tous les degrés pairs ; chaîne eulérienne ⇔ exactement 2 sommets de degré impair.
Graphe biparti connexe : nombre chromatique \(\chi(G)=2\). Tout graphe planaire est 4-coloriable.
Dijkstra ne marche pas avec des poids négatifs (utiliser Bellman-Ford).

Algorithmes sur les graphes

Algorithme	Objectif	Complexité
BFS (largeur)	parcours, plus court chemin non pondéré	\(O(\|V\|+\|E\|)\)
DFS (profondeur)	cycles, composantes connexes, tri topologique	\(O(\|V\|+\|E\|)\)
Dijkstra	plus court chemin, poids \(\geq0\)	\(O((\|V\|+\|E\|)\log\|V\|)\)
Kruskal	arbre couvrant minimal (arêtes triées)	\(O(\|E\|\log\|E\|)\)
Prim	arbre couvrant minimal (à partir d'un sommet)	\(O(\|E\|\log\|V\|)\)

Méthodes

Méthode Calculer le chemin critique (PERT)

Lister les tâches avec durées et antériorités.
Propagation avant : \(T^+\) de gauche à droite, prendre le MAX des (\(T^+\) prédécesseur + durée).
Propagation arrière : au nœud final \(T^-=T^+\), puis MIN des (\(T^-\) successeur − durée).
Calculer les marges \(MT=T^-_j-T^+_i-d_{ij}\).
Chemin critique = tâches de marge nulle ; durée = \(T^+\) final.

Erreurs fréquentes

Attention

❌ Prendre le minimum lors du calcul des dates au plus tôt \(T^+\).

✅ \(T^+\) se calcule avec le MAX (vers l'avant) ; le MIN sert pour \(T^-\) (vers l'arrière).

❌ Appliquer Dijkstra avec des poids négatifs.

✅ Dijkstra exige des poids positifs ; sinon utiliser Bellman-Ford.

❌ Confondre eulérien (parcourt chaque arête) et hamiltonien (passe par chaque sommet).

✅ Critère simple pour eulérien (degrés pairs) ; pas de critère simple pour hamiltonien.