Probleme – Kruskal : la propriété de la coupe, le code, et un piège d'OCaml

1. La propriété de la coupe. Soit $(S,V\setminus S)$ une partition des sommets en deux parties non vides, et $e$ une arête de poids minimal parmi celles ayant une extrémité de chaque côté. Soit $T$ un arbre couvrant minimal. Si $e\in T$, c'est fini. Sinon, $T\cup \{e\}$ contient un unique cycle ; ce cycle traverse la coupe un nombre pair de fois, donc au moins deux, donc il contient une autre arête $f$ traversant la coupe. Par minimalité de $e$, $p(e)\le p(f)$. Alors $T^{\prime }=T\cup \{e\}\setminus \{f\}$ est encore un arbre couvrant — on a cassé le seul cycle — et

$$p(T^{\prime })=p(T)+p(e)-p(f)\le p(T).$$

Comme $T$ est minimal, $p(T^{\prime })=p(T)$ : $T^{\prime }$ est un arbre couvrant minimal contenant $e$.

2. La correction de Kruskal en découle en une ligne. Quand Kruskal examine une arête $e=\{u,v\}$ et décide de la prendre, $u$ et $v$ sont dans deux classes différentes. Prenons pour $S$ la classe de $u$. Aucune arête déjà examinée ne traverse cette coupe (une telle arête aurait fusionné les deux classes), donc toutes les arêtes traversantes ont un poids $\ge p(e)$ puisque le tri est croissant : $e$ est bien de poids minimal sur la coupe. La propriété de la coupe s'applique. Une récurrence sur le nombre d'arêtes prises conclut : à chaque instant, l'ensemble construit est inclus dans un arbre couvrant minimal.

C'est la même preuve que celle du chapitre, dite autrement — et sous cette forme elle sert aussi pour l'algorithme de Prim, qui fait exactement le même choix sur une autre coupe.

3. Le code complet.

(* Arbre couvrant de poids minimal.
   Entrees  : n sommets numerotes de 0 a n-1, une liste d'aretes (u, v, poids).
   Sortie   : Some (aretes, poids total) si le graphe est connexe, None sinon.
   Complexite : O(m log m) pour le tri, puis m operations quasi constantes. *)
let kruskal n aretes =
  let triees = List.sort (fun (_,_,p1) (_,_,p2) -> compare p1 p2) aretes in
  let u = creer n in
  let prises = ref [] and total = ref 0 and k = ref 0 in
  (* INVARIANT : prises est inclus dans un arbre couvrant minimal, k = |prises|,
     et les classes de u sont les composantes du graphe (V, prises). *)
  List.iter (fun (a, b, p) ->
    if !k < n - 1 && unir u a b then begin
      prises := (a, b, p) :: !prises; total := !total + p; incr k
    end) triees;
  if !k = n - 1 then Some (List.rev !prises, !total) else None

Terminaison : la liste triée est finie. Complexité : $O(m\log m)$ pour le tri, puis $m$ appels à unir, quasi constants ; le tri domine. Détection de non-connexité : à la sortie, si le nombre d'arêtes prises est $<n-1$, c'est qu'il restait plusieurs classes. Sur le graphe à sept sommets du chapitre, le code rend $39$ ; sur le graphe à quatre sommets et deux arêtes $\{0,1\}$ et $\{2,3\}$, il rend None.

4. Le piège du List.filter. Le chapitre écrit :

List.filter (fun (u, v, _) ->
  if trouver uf u = trouver uf v then false
  else begin unir uf u v; true end) triees

Le prédicat n'est pas une fonction : c'est une procédure, qui modifie uf au passage. L'algorithme n'est donc correct que si List.filter applique le prédicat aux éléments dans l'ordre de la liste — sinon les arêtes seraient examinées dans le désordre, et le tri ne servirait à rien.

Or le manuel d'OCaml ne le garantit pas. Il dit seulement : « filter f l returns all the elements of the list l that satisfy the predicate f. The order of the elements in the input list is preserved » — c'est l'ordre du résultat qui est promis, pas celui des appels. Pour List.map, la documentation ne promet même pas cela. Une mesure sous OCaml 5.4.1 montre que List.filter applique bien le prédicat de gauche à droite ; mais c'est une observation, pas un contrat, et une version future pourrait la démentir sans rien casser d'autre.

Le rappel est utile : dans une expression comme (f 1) + (f 2), OCaml évalue de droite à gauche (mesuré : f 2 d'abord). L'ordre d'évaluation n'est pas spécifié dans le langage, et le supposer est une source de fautes silencieuses.

La correction est celle du code de la question 3 : un List.iter, dont la documentation garantit l'ordre (« applies f in turn to a1; ...; an »), et qui dit franchement qu'on fait des effets de bord. Un effet de bord ne se cache pas dans un prédicat : on le met là où le lecteur l'attend.