Recherche opérationnelle & graphes

Graphes, parcours, plus courts chemins & ordonnancement

Idée. La recherche opérationnelle (RO) modélise et résout des problèmes de décision : trouver le plus court trajet, le réseau de câblage le moins coûteux, l'ordonnancement le plus rapide d'un chantier. Son langage de base est la théorie des graphes ; ses outils sont des algorithmes dont on connaît la correction et le coût.

A. Graphes : vocabulaire & représentation

Un graphe $G=(V,E)$ est un ensemble de sommets $V$ et d'arêtes $E$ (paires de sommets). Il est orienté si les arêtes (les arcs) ont un sens, non orienté sinon ; pondéré si chaque arête porte un poids (distance, coût, capacité).

Degré d'un sommet (non orienté) : nombre d'arêtes qui l'atteignent. Lemme des poignées de main :
$\sum_{v\in V}\deg(v)=2\,\lvert E\rvert$
(chaque arête compte pour $2$ ). Conséquence : le nombre de sommets de degré impair est toujours pair.
Représentations : la matrice d'adjacence $A$ ( $A_{ij}=1$ si $i\sim j$ ) — pratique pour les calculs matriciels, coûteuse en mémoire ( $\lvert V\rvert^2$ ) ; les listes d'adjacence — compactes pour un graphe creux.

Exemple. Graphe à sommets $\{0,1,2,3,4\}$ , arêtes $01,02,12,23,34$ . Degrés $(2,2,3,2,1)$ , somme $10=2\times 5=2\lvert E\rvert$ .

B. Parcours & connexité

Parcours en largeur (BFS) : explore par couches au moyen d'une file ; donne le plus court chemin en nombre d'arêtes.
Parcours en profondeur (DFS) : plonge le plus loin possible au moyen d'une pile (ou la récursion) ; sert à détecter les cycles, calculer un tri topologique, les composantes.
Connexité : un graphe est connexe si tout sommet est atteignable depuis tout autre. Sinon il se décompose en composantes connexes.
Graphe eulérien (Euler, ponts de Königsberg, 1736) : un chemin eulérien (passant une et une seule fois par chaque arête) existe ssi le graphe connexe a $0$ ou $2$ sommets de degré impair ; un circuit eulérien (fermé) ssi $0$ sommet impair.
Graphe biparti : sommets séparables en deux groupes sans arête interne. Théorème : biparti $\iff$ $2$ -coloriable $\iff$ aucun cycle de longueur impaire.

C. Graphes orientés acycliques (DAG) & tri topologique

Un DAG est un graphe orienté sans circuit. On peut alors ranger ses sommets en une liste où chaque arc $u\to v$ va d'un sommet avant vers un sommet après : c'est un tri topologique (algorithme de Kahn : retirer répétitivement un sommet de degré entrant nul). Un graphe admet un tri topologique ssi c'est un DAG — l'échec de l'algorithme détecte un cycle.

D. Plus courts chemins

Sur un graphe pondéré, trouver le chemin de poids minimal entre deux sommets :

Algorithme	Poids	Complexité	Usage
Dijkstra	$\geq 0$	$O(\lvert E\rvert\log\lvert V\rvert)$	source unique, poids positifs
Bellman-Ford	quelconques	$O(\lvert V\rvert\cdot\lvert E\rvert)$	poids négatifs, détecte un cycle négatif
Floyd-Warshall	quelconques	$O(\lvert V\rvert^3)$	toutes les paires

Dijkstra est glouton : il fixe à chaque étape le sommet non traité de plus petite distance provisoire, puis relâche ses arcs. L'hypothèse $\geq 0$ est essentielle (un sommet fixé ne peut plus être amélioré).
Bellman-Ford relâche toutes les arêtes $\lvert V\rvert-1$ fois ; une amélioration au $\lvert V\rvert$ -ième tour signale un cycle de poids négatif (où la notion de plus court chemin n'a plus de sens).
On reconstruit le chemin via le tableau des prédécesseurs.

Un graphe orienté pondéré à cinq sommets ; les arcs de l'arbre des plus courts chemins depuis la source sont mis en évidence, chaque sommet porte sa distance minimale, et le chemin optimal vers le sommet le plus éloigné est surligné. — **Arbre des plus courts chemins** issu de Dijkstra depuis la source $0$ . Les arcs **verts** (épais) forment l'arbre des plus courts chemins ; les distances minimales sont indiquées à chaque sommet. Le chemin optimal vers $4$ est $0\to2\to1\to3\to4$ (coût $7$ ) : passer par $2$ ( $d=1$ ) bat l'arc direct $0\to1\,(4)$ .

Exemple (Dijkstra). Arcs $0\to1\,(4)$ , $0\to2\,(1)$ , $2\to1\,(2)$ , $1\to3\,(1)$ , $2\to3\,(5)$ , $3\to4\,(3)$ . Distances depuis $0$ : $(0,3,1,4,7)$ ; chemin optimal vers $4$ : $0\to2\to1\to3\to4$ (coût $1+2+1+3=7$ ).

E. Arbres couvrants & ordonnancement

Arbre couvrant : sous-graphe connexe, sans cycle, touchant tous les sommets. Il a exactement $\lvert V\rvert-1$ arêtes.
Arbre couvrant minimal (ACM) : celui de poids total minimal. Deux algorithmes gloutons optimaux :
- Kruskal : trier les arêtes par poids croissant, ajouter chaque arête qui ne crée pas de cycle (test par union-find).
- Prim : faire croître l'arbre depuis un sommet en ajoutant l'arête sortante la moins chère.
Ordonnancement (PERT/CPM) : les tâches forment un DAG pondéré par les durées. La date de fin du projet est la longueur du plus long chemin ; les tâches de ce chemin (de marge nulle) forment le chemin critique. La marge d'une tâche $=$ date au plus tard $-$ date au plus tôt : seule une tâche critique, raccourcie, raccourcit le projet.

Exemple (PERT). Tâches $A,B,C,D,E$ de durées $3,2,4,1,2$ , dépendances $A\to C$ , $B\to C$ , $C\to D$ , $C\to E$ : durée du projet $9$ , chemin critique $A\to C\to E$ ( $3+4+2=9$ ), marges $(0,1,0,1,0)$ .