Composantes fortement connexes et couplages
Cours · informatique (MP2I/MPI), chapitre 24 · MP2I et MPI · le début du chapitre, la suite sur Adloun
24.1 Deux problèmes, deux surprises
Ce chapitre traite deux questions de graphes que le programme place en deuxième année, et chacune réserve une surprise.
La première : décomposer un graphe orienté en composantes fortement connexes. On s'attend à un algorithme compliqué ; il tient en deux parcours en profondeur. Et le programme demande d'en tirer une conséquence inattendue : « on fait le lien entre composantes fortement connexes et le problème 2-sat » — un problème de logique résolu par un algorithme de graphes, en temps linéaire.
La seconde : trouver un couplage maximal dans un graphe biparti. La surprise est qu'un glouton n'y suffit pas, et que le remède consiste à défaire des choix déjà faits — la première fois du livre.
24.2 Composantes fortement connexes
Dans un graphe orienté, la relation « et sont mutuellement accessibles » est une relation d'équivalence. Ses classes sont les composantes fortement connexes.
En contractant chaque composante en un seul sommet, on obtient un graphe orienté sans cycle — le graphe quotient.
Démonstration
Un cycle entre plusieurs composantes rendrait tous leurs sommets mutuellement accessibles : elles n'en formeraient qu'une, ce qui contredit leur maximalité.
Le graphe quotient étant acyclique, il se trie topologiquement (chapitre chap:parcours). On obtient ainsi un ordre de traitement des composantes — ce qui permet de résoudre par programmation dynamique des problèmes qu'un cycle rendait circulaires. La décomposition en composantes fortement connexes est donc la manière standard de rendre acyclique un graphe qui ne l'est pas.
24.2.1 L'algorithme de Kosaraju
Méthode : Deux parcours, et un graphe retourné
- Faire un parcours en profondeur de et empiler chaque sommet quand on a fini de le traiter — c'est exactement le tri topologique du chapitre chap:parcours.
- Construire , le graphe transposé : tous les arcs retournés.
- Parcourir en repartant des sommets dans l'ordre de la pile. Chaque parcours atteint exactement une composante.
(* Renvoie un tableau comp tel que comp.(u) est le numéro de la composante
fortement connexe de u. Complexité : Theta(n + m). *)
let kosaraju g =
let n = Array.length g in
(* 1. ordre de fin de traitement *)
let vu = Array.make n false and ordre = ref [] in
let rec descendre u =
vu.(u) <- true;
List.iter (fun v -> if not vu.(v) then descendre v) g.(u);
ordre := u :: !ordre
in
for s = 0 to n - 1 do if not vu.(s) then descendre s done;
(* 2. le graphe transposé *)
let gt = Array.make n [] in
Array.iteri (fun u l -> List.iter (fun v -> gt.(v) <- u :: gt.(v)) l) g;
(* 3. parcours de gt dans cet ordre *)
let comp = Array.make n (-1) and k = ref 0 in
let rec marquer u =
comp.(u) <- !k;
List.iter (fun v -> if comp.(v) = -1 then marquer v) gt.(u)
in
List.iter (fun u -> if comp.(u) = -1 then begin marquer u; incr k end) !ordre;
compC'est la clé de l'algorithme, et elle est simple : et ont exactement les mêmes composantes fortement connexes — la relation « mutuellement accessibles » est symétrique, donc insensible au retournement.
En revanche, les arcs entre composantes sont retournés. Le quotient de est donc le quotient de à l'envers. En partant du sommet dont le traitement s'est terminé en dernier — qui appartient à une composante source de —, on se trouve dans une composante puits de : le parcours ne peut plus en sortir, et ramasse donc exactement cette composante.