Algorithmique des graphes

Les graphes modélisent réseaux, dépendances, cartes et états d'un système. Le programme MP2I attend la maîtrise des représentations, des deux parcours fondamentaux et des algorithmes classiques de plus courts chemins et d'arbres couvrants, chacun avec son hypothèse, sa complexité et sa justification.

Un graphe $G=(S,A)$ a $n=|S|$ sommets et $m=|A|$ arêtes (non orienté : paires $\{u,v\}$) ou arcs (orienté : couples $(u,v)$). Degré d'un sommet : nombre d'arêtes incidentes ; $\sum \mathrm{deg}=2m$. Un chemin est une suite de sommets consécutivement adjacents, un cycle un chemin fermé. Un graphe non orienté est connexe si deux sommets quelconques sont reliés ; un graphe orienté est fortement connexe si tout couple est relié dans les deux sens. Un arbre est un graphe connexe sans cycle, ce qui équivaut à connexe avec $n-1$ arêtes.

En OCaml, un graphe pondéré se code en `(int * int) list array` ; en C, en tableau de listes chaînées ou en matrice. Propriété utile : $(M^k)[u][v]$ compte les chemins de longueur $k$ de $u$ à $v$.

Depuis une source $s$, on utilise une file et un marquage : on enfile $s$ ; tant que la file n'est pas vide, on défile $u$ et on enfile chaque voisin non marqué, en le marquant à la découverte. Les sommets sortent par distance croissante, et $d(v)=d(u)+1$ donne les plus courtes distances en nombre d'arêtes. Complexité O(n + m).

Applications : plus courts chemins non pondérés (grilles, labyrinthes), test de bipartition par coloration alternée des niveaux, composantes connexes.

On visite un sommet puis récursivement chacun de ses voisins non visités (version itérative : pile). Complexité O(n + m). Le DFS fournit des dates de début et de fin et une classification des arcs qui permettent :