Probleme – Le chemin le plus large

1. La preuve. Soit $T$ un arbre couvrant maximal — obtenu par Kruskal en triant par poids décroissant —, soit $P$ l'unique chemin de $s$ à $t$ dans $T$, et soit $b$ son goulot. Montrons qu'aucun chemin ne fait mieux.

Soit $e$ une arête de $P$ réalisant le goulot, $p(e)=b$. Retirer $e$ de $T$ coupe l'arbre en deux parties $S$ et $V\setminus S$, avec $s\in S$ et $t\notin S$ (car $e$ est sur le chemin de $s$ à $t$). Toute arête $f$ traversant cette coupe vérifie $p(f)\le p(e)$ : sinon, $T\cup \{f\}\setminus \{e\}$ serait un arbre couvrant de poids strictement supérieur, ce qui contredit la maximalité de $T$. C'est la propriété de la coupe, retournée.

Or tout chemin de $s$ à $t$ dans le graphe doit traverser cette coupe au moins une fois, donc emprunter une arête de poids $\le b$. Son goulot est donc $\le b$. Le chemin $P$ est optimal.

2. L'algorithme.

(* Chemin de goulot maximal entre s et t.
   Entrees : n sommets, liste d'aretes (u, v, poids), graphe connexe.
   Sortie  : le goulot maximal. Complexite : O(m log m). *)
let goulot_maximal n aretes s t =
  (* 1. arbre couvrant MAXIMAL : Kruskal, tri DECROISSANT *)
  let triees = List.sort (fun (_,_,a) (_,_,b) -> compare b a) aretes in
  let u = creer n and arbre = Array.make n [] in
  List.iter (fun (a, b, p) ->
    if unir u a b then begin
      arbre.(a) <- (b, p) :: arbre.(a);
      arbre.(b) <- (a, p) :: arbre.(b)
    end) triees;
  (* 2. l'unique chemin de s a t dans l'arbre, par parcours en profondeur *)
  let vu = Array.make n false in
  let rec descendre x mini =
    if x = t then Some mini
    else begin
      vu.(x) <- true;
      List.fold_left (fun acc (y, p) ->
        match acc with
        | Some _ -> acc
        | None -> if vu.(y) then None else descendre y (min mini p)
      ) None arbre.(x)
    end
  in
  descendre s max_int

Complexité : $O(m\log m)$ pour le tri, puis un parcours en $\Theta (n)$ dans un arbre de $n-1$ arêtes. Et le même arbre répond à toutes les paires : le construire une fois coûte $O(m\log m)$, puis chaque requête coûte $\Theta (n)$. C'est l'argument décisif quand on a beaucoup de paires à traiter.

3. La vérification. Sur le graphe à cinq sommets

$$01:3,12:5,02:2,23:7,13:4,34:6,24:1,$$

l'arbre couvrant maximal calculé est $\{23:7,34:6,12:5,01:3\}$, de poids $21$. On compare, pour les dix paires de sommets, le goulot dans cet arbre au goulot optimal calculé par énumération de tous les chemins simples :

Accord sur les dix paires.

Remarquer $2$-$4$. L'arête directe $24$ pèse $1$ ; le chemin optimal l'évite et passe par $3$, de goulot $\min (7,6)=6$. Le chemin le plus large n'est ni le plus court ni le moins cher : c'est un troisième problème, et il se trouve que l'arbre couvrant le résout aussi.