Introduction à l’algorithmique

Analyse de la méthode avec préflot

Pour montrer que l’algorithme de préflot générique se termine effectivement, nous allons borner le nombre d’opérations qu’il effectue. Chacun des trois types d’opération, à savoir ré-étiquetage, poussage saturant et poussage non saturant, est borné séparément. En connaissant ces bornes, il devient aisé de construire un algorithme qui s’exécute en O(S2A). Avant de plonger dans l’analyse, commençons toutefois par démontrer un lemme important.

Lemme
Soit G =( S,A) un réseau de transport de source s et de puits t et soit f un préflot de G. Alors, pour un sommet débordant quelconque u, il existe un chemin élémentaire de u vers s dans le réseau résiduel Gf. Démonstration: u étant un sommet débordant, posons U ={v : il existe un chemin élémentaire de u vers v dans Gf} et supposons, en raisonnant par l’absurde, que s∈U. SoitU = S−U. Nous affirmons que, pour chaque couple de sommets v ∈ U et w ∈ U, f(w,v) 0. Pourquoi ? Si f(w,v) > 0, alors f(v,w) < 0, ce qui implique en retour que cf(v,w)=c(v,w)−f(v,w) > 0. Il existe donc un arc (v,w) ∈ Af, et donc il existe un chemin élémentaire de la forme u v→w dans Gf,ce qui invalide notre choix de w. On doit donc avoir f(U,U)
0, puisque chaque terme de cette sommation implicite est négatif ou nul.
 • Flot maximum
D’où e(U)=f(S,U) (d’après l’équation (26.9)) = f(U,U)+f(U,U) (d’après le lemme 26.1, partie (3)) = f(U,U) (d’après le lemme 26.1, partie (1)) 0 . Les excédents sont positifs ou nuls pour tous les sommets de S−{ s} ; comme nousavons fait l’hypothèse que U ⊆S−{ s}, on doit avoir e(v) = 0 pour tous les sommetsv ∈ U. En particulier, e(u) = 0, ce qui contredit l’hypothèse selon laquelle u déborde.