Probleme – Regrouper par arbre couvrant

1. La preuve, en deux temps. Soit $T$ un arbre couvrant minimal du graphe complet des distances, et soit $\mathcal{C}$ la répartition obtenue en retirant de $T$ ses $k-1$ arêtes les plus lourdes — elle a bien $k$ groupes, puisque retirer une arête d'un arbre le coupe en deux. Notons $d^{\ast }$ le poids de la plus légère des arêtes retirées.

Premier temps : l'espacement de $\mathcal{C}$ vaut exactement $d^{\ast }$. Il est $\le d^{\ast }$, puisque l'arête retirée de poids $d^{\ast }$ joint deux points de groupes différents. Pour l'autre sens, on raisonne sur l'exécution de Kruskal, qui construit $T$ en prenant les arêtes par poids croissant : $\mathcal{C}$ est l'état de la structure unir & trouver au moment où il ne reste que $k$ classes, et toutes les arêtes prises jusque-là pèsent $\le d^{\ast }$. Supposons deux points $p$ et $q$ de groupes différents avec $d(p,q)<d^{\ast }$. Kruskal aurait examiné $\{p,q\}$ avant d'atteindre $d^{\ast }$, donc à un instant où $p$ et $q$ étaient déjà dans des classes distinctes — les classes ne font que fusionner. Il l'aurait donc prise, et $p$ et $q$ se retrouveraient dans le même groupe. Contradiction.

Second temps : aucune répartition ne fait mieux. Soit ${\mathcal{C}}^{\prime }$ une autre répartition en $k$ groupes. Comme ${\mathcal{C}}^{\prime }\ne \mathcal{C}$ et que les deux ont $k$ groupes, il existe deux points $p$ et $q$ dans le même groupe de $\mathcal{C}$ et dans deux groupes différents de ${\mathcal{C}}^{\prime }$. Le chemin de $p$ à $q$ dans $T$ reste entièrement dans un groupe de $\mathcal{C}$, donc toutes ses arêtes pèsent $\le d^{\ast }$. Ce chemin part d'un groupe de ${\mathcal{C}}^{\prime }$ et arrive dans un autre : il contient donc une arête $\{a,b\}$ dont les extrémités sont dans deux groupes différents de ${\mathcal{C}}^{\prime }$. L'espacement de ${\mathcal{C}}^{\prime }$ est majoré par le poids de cette arête, donc par $d^{\ast }$.

2. L'algorithme, et c'est Kruskal arrêté plus tôt.

(* Repartition de n points en k groupes d'espacement maximal.
   Entrees : n >= k >= 1, une liste d'aretes (i, j, distance).
   Sortie  : la structure unir & trouver dont les classes sont les groupes,
             et l'espacement obtenu.
   Complexite : O(m log m), m = n(n-1)/2 pour un nuage de points. *)
let regrouper n k aretes =
  let triees = List.sort (fun (_,_,a) (_,_,b) -> compare a b) aretes in
  let u = creer n and espacement = ref infinity in
  List.iter (fun (a, b, d) ->
    if u.classes > k then ignore (unir u a b)
    else if !espacement = infinity && trouver u a <> trouver u b then
      espacement := d                (* la 1re arete NON prise : l'espacement *)
  ) triees;
  (u, !espacement)

Le lien avec Kruskal est une identité, pas une analogie : c'est exactement Kruskal, arrêté quand il ne reste plus que $k$ classes au lieu de $1$. Il prend donc les $n-k$ arêtes les plus légères de l'arbre couvrant minimal, ce qui revient à en retirer les $k-1$ plus lourdes. Et l'espacement est la première arête écartée pour cause de groupes distincts après l'arrêt.

3. La vérification. Huit points du plan :

$$(0,0),(1,0),(0,1),(10,10),(11,10),(10,11),(30,0),(31,0).$$

L'arbre couvrant minimal des $28$ distances a pour arêtes triées, en poids :

$$1,01,01,01,01,013,45421,471.$$

Pour $k=3$, on retire les deux plus lourdes, $21,471$ et $13,454$. Les groupes obtenus sont $\{0,1,2\}$, $\{3,4,5\}$, $\{6,7\}$ — les trois amas —, et l'espacement vaut $13,454$. Une énumération exhaustive des $966$ répartitions de huit points en trois groupes non vides confirme : $13,454$ est le maximum, et il est atteint par cette répartition.

Ce que le problème enseigne. La minimisation d'un poids total (l'arbre couvrant minimal) et la maximisation d'une distance minimale (l'espacement) semblent sans rapport ; c'est la structure de l'arbre couvrant qui les relie. C'est le même retournement qu'au problème « Le chemin le plus large », où l'arbre couvrant maximal résolvait un problème de goulot. L'arbre couvrant en dit plus que son poids.